A Mathematical Model and Descent Algorithm for Bilevel Traffic Management
- 1 August 2002
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Transportation Science
- Vol. 36 (3) , 271-291
Abstract
We provide a new mathematical model for strategic traffic management, formulated and analyzed as a mathematical program with equilibrium constraints (MPEC). The model includes two types of control (upper-level) variables, which may be used to describe such traffic management actions as traffic signal setting, network design, and congestion pricing. The lower-level problem of the MPEC describes a traffic equilibrium model in the sense of Wardrop, in which the control variables enter as parameters in the travel costs. We consider a (small) variety of model settings, including fixed or elastic demands, the possible presence of side constraints in the traffic equilibrium system, and representations of traffic flows and management actions in both link-route and link-node space. For this model, we also propose and analyze a descent algorithm. The algorithm utilizes a new reformulation of the MPEC into a constrained, locally Lipschitz minimization problem in the product space of controls and traffic flows. The reformulation is based on the Minty (1967) parameterization of the graph of the normal cone operator for the traffic flow polyhedron. Two immediate advantages of making use of this reformulation are that the resulting descent algorithm can be operated and established to be convergent without requiring that the travel cost mapping is monotone, and without having to ever solve the lower-level equilibrium problem. We provide example realizations of the algorithm, establish their convergence, and interpret their workings in terms of the traffic network.Keywords
This publication has 49 references indexed in Scilit:
- A reduction method for local sensitivity analyses of network equilibrium arc flowsTransportation Research Part B: Methodological, 2000
- Side constrained traffic equilibrium models— analysis, computation and applicationsTransportation Research Part B: Methodological, 1999
- An augmented lagrangean dual algorithm for link capacity side constrained traffic assignment problemsTransportation Research Part B: Methodological, 1995
- Bilevel programming in traffic planning: Models, methods and challengeJournal of Global Optimization, 1995
- Exact local solution of the continuous network design problem via stochastic user equilibrium assignmentTransportation Research Part B: Methodological, 1994
- A class of nonmonotone stabilization methods in unconstrained optimizationNumerische Mathematik, 1991
- An explicit solution to the multi-level programming problemComputers & Operations Research, 1982
- Some developments in equilibrium traffic assignmentTransportation Research Part B: Methodological, 1980
- Continuous equilibrium network design modelsTransportation Research Part B: Methodological, 1979
- ROAD PAPER. SOME THEORETICAL ASPECTS OF ROAD TRAFFIC RESEARCH.Proceedings of the Institution of Civil Engineers, 1952