Constrained multigrid optimization techniques for solving continuous dynamic disequilibrium network design problems

This thesis investigates a general continuous dynamic disequilibrium network design model adapted from Friesz et al. [14]. Dynamic network design problems describe how to optimally enhance network capacity over time when the improvement budget is limited, given time-varying origin-destination travel demand functions. Although this model will be presented in the context of automobile traffic, it is relevant to any network design problem for which there is a central authority trying to maximize some measure of public utility while the users of the network are empowered to make their own routing decisions. In addition, our model is the first to employ elastic, nonseparable origin-destination travel demand functions. Path flow and perceived travel cost dynamics are derived from the static version of Wardrop's First Principal of user equilibrium, the accepted standard behavioral paradigm for networks where users are independent decision makers. A constrained multigrid optimization algorithm adapted from Nash [8] will be presented and used to solve several numerical examples. This multigrid approach uses nonlinear programming techniques to solve varying time discretizations of the given continuous-time mathematical program. Proof of descent and convergence for the constrained multigrid algorithm is presented and the relationships between the corresponding discretized models are analyzed.