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.
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.
Guest Editor: Eleonora Papadimitriou, PhD
Editors: Dario Babić, PhD; Marko Matulin, PhD; Marko Ševrović, PhD.
The mission of our journal is to provide high quality communication of research results, which is crucial for the effectiveness of scientific research, the promotion of scientific information, new ideas, and original research in the field of traffic and transportation engineering.
1848-4069
0353-5320
Proud publisher
Accelerating Discoveries in Traffic Science |
2024 © Promet - Traffic&Transportation journal
