An MPCC Formulation and Its Smooth Solution Algorithm for Continuous Network Design Problem
Abstract
Continuous network design problem (CNDP) is searching for a transportation network configuration to minimize the sum of the total system travel time and the investment cost of link capacity expansions by considering that the travellers follow a traditional Wardrop user equilibrium (UE) to choose their routes. In this paper, the CNDP model can be formulated as mathematical programs with complementarity constraints (MPCC) by describing UE as a non-linear complementarity problem (NCP). To address the difficulty resulting from complementarity constraints in MPCC, they are substituted by the Fischer-Burmeister (FB) function, which can be smoothed by the introduction of the smoothing parameter. Therefore, the MPCC can be transformed into a well-behaved non-linear program (NLP) by replacing the complementarity constraints with a smooth equation. Consequently, the solver such as LINDOGLOBAL in GAMS can be used to solve the smooth approximate NLP to obtain the solution to MPCC for modelling CNDP. The numerical experiments on the example from the literature demonstrate that the proposed algorithm is feasible.
References
Yang H, Bell MGH. Models and algorithms for road network design: a review and some new developments. Transport Reviews. 1998;18(3): 257-278.
Marcotte P, Marquis G. Efficient implementation of heuristic for the continuous network design problems. Annals of operation research. 1992;34: 163-176.
Allsop RE. Some possibilities of using traffic control to influence trip distribution and route choice. In: Buckley, DJ editor. Proceedings of the 6th International Symposium on Transportation and Traffic Theory. Amsterdam: Elsevier. 1974; p. 345-374.
Farahani RZ, Miandoabchi E, Szeto WY, Rashidi H. A review of urban transportation network design problems. European Journal of Operational Research. 2013;229(2): 281-302.
Abdulaal M, LeBlanc LJ. Continuous equilibrium network design models. Transportation Research Part B. 1979;13: 19-32.
Suwansirikul C, Friesz TL, Tobin RL. Equilibrium decomposed optimization: a heuristic for the continuous equilibrium network design problem. Transportation Science. 1987;21: 254-263.
Kim TJ, Suh S. Toward developing a national transportation planning model: A bilevel programming approach for Korea. The Annals of Regional Science. 1998;22(1): 65-80.
Friesz TL, Hsun-jung C, Mehta NJ, Tobin RL, Anandalingam G. A simulated annealing approach to the network design problem with variational inequality constraints. Transportation Science. 1992;26(1): 18-26.
Yang H, Yagar S. Traffic assignment and signal control in saturated road networks. Transportation Research Part A. 1995;29(2): 125-139.
Yang H. Heuristic algorithms for the bilevel origin-destination estimation problem. Transportation Research Part B. 1995;29: 231-242.
Gao ZY, Song YF, Si BF. Urban Transportation Continuous Equilibrium Network Design Problem: Theory and Method (in Chinese). Beijing (China): China Railway Publishing House; 2000.
Meng Q, Yang H, Bell MGH. An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem. Transportation Research Part B. 2001;35: 83-105.
Chiou SW. Bilevel programming for the continuous transport network design problem. Transportation Research Part B. 2005;39(4): 361-383.
Ban JX, Liu HX, Ferris MC, Ran B. A general MPCC model and its solution algorithm for continuous network design problem. Mathematical and Computer Modelling. 2006;43(5-6): 493-505.
Wang GM, Gao ZY, Xu M, Sun HJ. Models and a relaxation algorithm for continuous network design problem with a tradable credit scheme and equity constraints. Computers & Operations Research. 2014;41: 252-261.
Wang GM, Gao ZY, Xu M, Sun HJ. Joint link-based credit charging and road capacity improvement in continuous network design problem. Transportation Research Part A. 2014;67: 1-14.
Gao ZY, Sun HJ, Zhang HZ. A globally convergent algorithm for transportation continuous network design problem. Optimization and Engineering. 2007;8(3): 241-257.
Sumalee A, Multi-concentric optimal charging cordon design. Transportmetrica. 2007;3(1): 41-71.
Chiou SW. A subgradient optimization model for continuous road network design problem. Applied Mathematical Modelling. 2009;33(3): 1386-1396.
Wang DZW, Lo HK. Global optimum of the linearized network design problem with equilibrium flows. Transportation Research Part B. 2010;44(4): 482-492.
Luathep P, Sumalee A, Lam WHK, Li ZC, Hong KL. Global optimization method for mixed transportation network design problem: A mixed-integer linear programming approach. Transportation Research Part B. 2011;45(5): 808-827.
Li CM, Yang H, Zhu DL, Meng Q. A global optimization method for continuous network design problems. Transportation Research Part B. 2012;46(9): 1144-1158.
Liu H, Wang DZW. Global optimization method for network design problem with stochastic user equilibrium. Transportation Research Part B. 2015;72: 20-39.
Baskan O. Harmony search algorithm for continuous network design problem with link capacity expansions. KSCE Journal of Civil Engineering. 2014;18(1): 273-283.
Baskan O, Ceylan H. Modified Differential Evolution Algorithm for the Continuous Network Design Problem. Procedia - Social and Behavioral Sciences. 2014;11: 48-57.
Wang GM, Gao ZY, Xu M. An MPEC formulation and its cutting constraint algorithm for continuous network design problem with multi-user classes. Applied Mathematical Modelling. 2014;38(5–6): 1846-1858.
Liu XY, Chen Q. An algorithm for the mixed transportation network design problem. PloS one. 2016;11(9): e0162618.
Sun ZC. Continuous Transportation Network Design Problem Based on Bi-level Programming Model. Procedia Engineering. 2016;137: 277-282.
Chen Y, Florian M. The nonlinear bilevel programming problem: Formulations, regularity and optimality conditions. Optimization. 1995;32: 193-209.
Scheel H, Scholte S. Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Mathematics of Operations Research. 2000;22(1): 1-22.
Bard JF. Convex two-level optimization. Mathematical Programming. 1988;40(1): 15-27.
Outrata J, Kocvara M, Zowe J. Nonsmooth Approach to Optimization Problems with Equilibrium Constraints: Theory, Applications and Numerical Results. Boston (MA): Kluwer Academic Publishers; 1998.
Luo ZQ, Pang JS, Ralph D. Mathematical Programs with Equilibrium Constraints. Cambridge (UK): Cambridge University Press; 1996.
Dirkse SP, Ferris MC, Meeraus A. Mathematical programs with equilibrium constraints: Automatic reformulation and solution via constraint optimization. Technical Report NA-02/11, Oxford: Oxford University Computing Laboratory; 2002.
Scholtes S. Convergence properties of regularization schemes for mathematical programs with complementarity constraints. SIAM Journal on Optimization. 2001;11(4): 918-936.
Fukushima M, Pang JS. Convergence of a smoothing continuation method for mathematical problems with complementarity constraints. In: Théra M, Tichatschke R, editors. Illposed Variational Problems and Regularization Techniques, Lecture Notes in Economics and Mathematical Systems, Heidelberg (Berlin): Springer-Verlag. 1999; p. 105-116.
Lin GH, Fukushima M. A new relaxation method for mathematical programs with complementarity constraints. Journal of Optimization Theory and Applications. 2003;118: 81-116.
Lin GH, Fukushima M. A modified relaxation scheme for mathematical programs with complementarity constraints. Annals of Operations Research. 2005;133(133): 63-84.
Lin GH, Fukushima M. Hybrid approach with active set identification for mathematical programs with complementarity constraints. Journal of Optimization Theory and Applications. 2006;128(1): 1-28.
Leyffer S. Complementarity constraints as nonlinear equations: theory and numerical experience. Technical Report NA/209, Dundee (UK): Univ. of Dundee; 2002. [41] Ralph D, Wright SJ. Some properties of regularization and penalization schemes for MPEC's. Optimization
Methods & Software. 2004;19(5): 527-556.
Bouza G, Still G. Mathematical programs with complementarity constraints: convergence properties of a smoothing method. Mathematics of Operations Research. 2007;32(2): 467-483.
Fletcher R, Leyffer S. Solving mathematical program with complementarity constraints as nonlinear programs. Optimization Methods and Software. 2004;19(1): 15-40.
Fischer A. A special Newton-type optimization method. Optimization. 1992;24: 269-284.
Kanzow C. Some noninterior continuation methods for linear complementarity problems. SIAM Journal on Matrix Analysis and Applications. 1996;17(4): 851-868.
GAMS. GAMS-The Solver Manuals. Washington, DC: GAMS Development Corporation; 2009.
Wardrop JG. Some theoretical aspects of road traffic research. Operational Research Quarterly. 1952;4(4): 325-378.
Ahuja RK, Magnanti TL, Orlin JB. Network Flows: Theory, Algorithms, and Application. New York: Prentice Hall; 1998.
Zhang L, Lawphongpanich S, Yin Y. An active-set algorithm for discrete network design problems. In: Lam KWH, Wong SC, Lo KH, editors. Transportation and Traffic Theory 2009: golden jubilee. Boston (MA): Spring US. 2009; p. 283-300.
Han J, Xiu N, Qi H. Theory and Methods of Nonlinear Complementarity (in Chinese). Shanghai (China): Shanghai Scientific and Technical Publishers; 2006.
Lo HK, Chen A. Traffic equilibrium problem with route-specific costs: formulation and algorithms. Transportation Research Part B Methodological. 2000;34(6): 493-513.
Xu M, Chen A, Gao ZY. An efficient algorithm for traffic equilibrium problem with a general nonadditive route cost. Applied Mathematical Modelling. 2011;35(6): 3048-3062.
Jiang H, Ralph D. Smooth SQP methods for mathematical programs with nonlinear complementarity constraints. SIAM Journal on Optimization. 2000;10(3): 779-808.
Harker PL, Friesz TL. Bounding the solution of the continuous equilibrium network design problem. Proceedings of the Ninth International Symposium on Transportation and Traffic Theory. Delft (Netherlands): VNU Science Press; 1984.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
