×

zbMATH — the first resource for mathematics

A general MPCC model and its solution algorithm for continuous network design problem. (English) Zbl 1180.90028
Summary: This paper formulates the continuous network design problem as a mathematical program with complementarity constraints (MPCC), with the upper level a nonlinear programming problem and the lower level a nonlinear complementarity problem. Unlike in most previous studies, the proposed framework is more general, in which both symmetric and asymmetric user equilibria can be captured. By applying the complementarity slackness condition of the lower-level problem, the original bilevel formulation can be converted into a single-level and smooth nonlinear programming problem. In order to solve the problem, a relaxation scheme is applied by progressively restricting the complementarity condition, which has been proven to be a rigorous approach under certain conditions. The model and solution algorithm are tested for well-known network design problems and promising results are shown.

MSC:
90B10 Deterministic network models in operations research
Software:
MacMPEC
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Leblanc, L.J.; Boyce, D., A bilevel programming algorithm for exact solution of the network design problem with user-optimal flows, Transportation research, 20B, 259-265, (1986)
[2] Luo, Z.Q.; Pang, J.S.; Ralph, D., Mathematical programs with equilibrium constraints, (1996), Cambridge University Press Cambridge, UK
[3] E. Morlok, J. Schofer, W. Pierskalla et al., Development and Application of a Highway Network Design Model, Final Report: FHWA Contract Number DOT-PH-11, Northwestern University, 1973
[4] Friesz, T.L.; Cho, H.J.; Mehta, N.J., A simulated annealing approach to the network design problem with variational inequality constraints, Transportation science, 26, 18-26, (1992) · Zbl 0764.90084
[5] Marcotte, P., Network optimization with continuous control parameters, Transportation science, 17, 181-197, (1983)
[6] Suwansirikul, C.; Friesz, T.L.; Tobin, R.L., Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem, Transportation science, 21, 254-263, (1987) · Zbl 0638.90097
[7] Abdulaal, M.; LeBlanc, L.J., Continuous equilibrium network design models, Transportation research, 13B, 19-32, (1979)
[8] Yang, H., Sensitivity analysis for the elastic demand network equilibrium problem with applications, Transportation research, 31B, 55-70, (1997)
[9] Yang, H.; Bell, M.G.H., Transport bilevel programming problems: recent methodological advances, Transportation research, 35B, 1-4, (2001)
[10] Meng, Q.; Yang, H.; Bell, M.G.H., An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem, Transportation research, 35B, 83-105, (2001)
[11] Marcotte, P.; Zhu, D.L., Exact and inexact penalty methods for the generalized bilevel programming problem, Mathematical programming, 74, 141-157, (1996) · Zbl 0855.90120
[12] Patriksson, M.; Rockafellar, R.T, A mathematical model and descent algorithm for bilevel traffic management, Transportation science, 36, 271-291, (2002) · Zbl 1134.90319
[13] M. Anitescu, On Solving Mathematical Programs with Complementarity Constraints as Nonlinear Programs, MCS Division, Argonne National Laboratory, Argonne, IL, 2000. Reprint ANL/MCS-P864-1200
[14] M. Anitescu, Global Convergence of an Elastic Mode Approach for a Class of Mathematical Programs with Complementarity Constraints, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, USA, 2004. Preprint ANL/MCS-P1143-0404 · Zbl 1099.65050
[15] Fletcher, R.; Leyffer, S., Solving mathematical program with complementarity constraints as nonlinear programs, Optimization methods and software, 19, 1, 15-40, (2004) · Zbl 1074.90044
[16] Hu, X.; Ralph, D., A note on sensitivity of value functions of mathematical programs with complementarity constraints, Mathematical programming, 93, 2, 265-279, (2002) · Zbl 1065.90072
[17] Jiang, H.; Ralph, D., Smooth SQP methods for mathematical programs with nonlinear complementarity constraints, SIAM journal of optimization, 10, 3, 779-808, (2000) · Zbl 0955.90134
[18] Jiang, H.; Ralph, D., Extension of quasi-Newton methods to mathematical programs with complementarity constraints, Computational optimization and applications, 25, 1-3, 123-150, (2003) · Zbl 1038.90100
[19] Scheel, H.; Scholte, S., Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity, Mathematics of operations research, 22, 1, 1-22, (2000) · Zbl 1073.90557
[20] Ralph, D.; Wright, S.J., Some properties of regularization and penalization schemes for mpecs, Optimization methods and software, 19, 527-556, (2004) · Zbl 1097.90054
[21] Wardrop, J.G., Some theoretical aspects of road traffic research, Proceedings of the institution of civil engineers, part II, 1, 325-378, (1952)
[22] Patriksson, M., The traffic assignment problem, models and methods, (1994), VSP · Zbl 0828.90127
[23] J.X. Ban, Quasi-variational inequality formulations and solution approaches for dynamic user equilibria, Ph.D. Thesis, University of Wisconsin-Madison, 2005
[24] J.X. Ban, H.X. Liu, J.G. Lu, M.C. Ferris, A decomposition scheme for continuous network design problem with asymmetric user equilibrium. Accepted for presentation and pending for publication at Transportation Research Board Meeting
[25] Harker, T.L.; Friesz, T.L., Bounding the solution of the continuous equilibrium network design problem, () · Zbl 0558.90094
[26] Leblanc, L.J.; Morlok, E.K.; Pierskalla, W.P., An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation research, 9, 309-318, (1975)
[27] M.C. Ferris, S.P. Dirkse, A. Meeraus, Mathematical programs with equilibrium constraints: automatic reformulation and solution via constrained optimization, Numerical Analysis Group Research Report NA-02/11, Oxford University Computing Laboratory, Oxford University, USA, 2002 · Zbl 1203.91142
[28] Nagurney, A., Comparative test of multimodal traffic equilibrium methods, Transportation research, 18B, 469-485, (1984)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.