Improving the Performance of the Bilevel Solution for the Continuous Network Design Problem
For a long time, many researchers have investigated the continuous network design problem (CNDP) to distribute equitably additional capacity between selected links in a road network, to overcome traffic congestion in urban roads. In addition, CNDP plays a critical role for local authorities in tackling traffic congestion with a limited budget. Due to the mutual interaction between road users and local authorities, CNDP is usually solved using the bilevel modeling technique. The upper level seeks to find the optimal capacity enhancements of selected links, while the lower level is used to solve the traffic assignment problem. In this study, we introduced the enhanced differential evolution algorithm based on multiple improvement strategies (EDEMIS) for solving CNDP. We applied EDEMIS first to a hypothetical network to show its ability in finding the global optimum solution, at least in a small network. Then, we used a 16-link network to reveal the capability of EDEMIS especially in the case of high demand. Finally, we used the Sioux Falls city network to evaluate the performance of EDEMIS according to other solution methods on a medium-sized road network. The results showed that EDEMIS produces better solutions than other considered algorithms, encouraging transportation planners to use it in large-scale road networks.
 Farahani RZ, Miandoabchi E, Szeto WY, Rashidi H. A review of urban transportation network design problems. European Journal of Operational Research. 2013;229: 281-302. Available from: doi:10.1016/j.ejor.2013.01.001
 Baskan O, Ceylan H. Modified Differential Evolution Algorithm for the Continuous Network Design Problem. Procedia-Social and Behavioral Sciences. 2014;111: 48-57. Available from: doi:10.1016/j.sbspro.2014.01.037
 Abdulaal M, LeBlanc L. Continuous equilibrium network design models. Transportation Research Part B. 1979;13(1): 19-32. Available from: doi:10.1016/0191-2615(79)90004-3
 Suwansirikul C, Friesz TL, Tobin RL. Equilibrium decomposed optimisation: A heuristic for the continuous equilibrium network design problem. Transportation Science. 1987;21(4): 254-263.
 Marcotte P. Network optimization with continuous control parameters. Transportation Science. 1983;17(2): 181-197. Available from: doi:10.1287/trsc.17.2.181
 Marcotte P, Marquis G. Efficient implementation of heuristics for the continuous network design problem. Annals of Operational Research. 1992;34(1): 163-176. Available from: doi:10.1007/BF02098178
 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(1): 83-105. Available from: doi:10.1016/S0191-2615(00)00016-3
 Chiou SW. Bilevel programming for the continuous transport network design problem. Transportation Research Part B. 2005;39(4): 361-383. Available from: doi:10.1016/j.trb.2004.05.001
 Ban XG, Liu HX, Lu JG, Ferris MC. Decomposition scheme for continuous network design problem with asymmetric user equilibria. Transportation Research Record. 2006;1964: 185-192. Available from: doi:10.3141/1964-20
 Karoonsoontawong A, Waller ST. Dynamic continuous network design problem-Linear bilevel programming and metaheuristic approaches. Transportation Research Record. 2006;1964: 104-117. Available from: doi:10.3141/1964-12
 Gao Z, Sun H, Zhang H. A globally convergent algorithm for transportation continuous network design problem. Optimization and Engineering. 2007;8(3): 241-257. Available from: doi:10.1007/s11081-007-9015-1
 Xu T, Wei H, Hu G. Study on continuous network design problem using simulated annealing and genetic algorithm. Expert Systems with Applications. 2009;36(2): 1322-1328. Available from: doi:10.1016/j.eswa.2007.11.023
 Mathew TV, Sharma S. Capacity expansion problem for large urban transportation networks. Journal of Transportation Engineering. 2009;135(7): 406-415. Available from: doi:10.1061/(ASCE)0733-947X(2009)135:7(406)
 Wang DZW, Lo HK. Global optimum of the linearized network design problem with equilibrium ﬂows. Transportation Research Part B. 2010;44(4): 482-492. Available from: doi:10.1016/j.trb.2009.10.003
 Li C, Yang H, Zhu D, Meng Q. A global optimization method for continuous network design problems. Transportation Research Part B. 2012;46(9): 1144-1158. Available from: doi:10.1016/j.trb.2012.05.003
 Baskan O. Determining Optimal Link Capacity Expansions in Road Networks Using Cuckoo Search Algorithm with Lévy Flights. Journal of Applied Mathematics. 2013;2013: 1-11. Available from: doi:10.1155/2013/718015
 Baskan O. An evaluation of heuristic methods for determining optimal link capacity expansions on road networks. International Journal of Transportation. 2013;2(1): 77-94. Available from: doi:10.14257/ijt.2014.2.1.05
 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: 1846-1858. Available from: doi:10.1016/j.apm.2013.10.003
 Wang GM, Gao Z, Xu M, Sun H. 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. Available from: doi:10.1016/j.cor.2012.11.010
 Wang GM, Gao Z, Xu M, Sun H. Joint link-based credit charging and road capacity improvement in continuous network design problem. Transportation Research Part A. 2014;67: 1-14. Available from: doi:10.1016/j.tra.2014.05.012
 Davis GA. Exact local solution of the continuous network design problem via stochastic user equilibrium assignment. Transportation Research Part B. 1994;28(1): 61-75. Available from: doi:10.1016/0191-2615(94)90031-0
 Liu H, Wang DZW. Global optimization method for network design problem with stochastic user equilibrium. Transportation Research Part B. 2015;72: 20-39. Available from: doi:10.1016/j.trb.2014.10.009
 Du B, Wang DZW. Solving Continuous Network Design Problem with Generalized Geometric Programming Approach. Transportation Research Record. 2016;2567: 38-46. Available from: doi:10.3141/2567-05
 Chen M, Alfa AS. A Network Design Algorithm Using a Stochastic Incremental Traffic Assignment Approach. Transportation Science. 1991;25(3): 215-224. Available from: doi:10.1287/trsc.25.3.215
 Zhang H, Gao Z. Two-Way Road Network Design Problem With Variable Lanes. Journal of Systems Science and Systems Engineering. 2007;16(1): 50-61. Available from: doi:10.1007/s11518-007-5034-x
 Wu JJ, Sun HJ, Gao ZY, Zhang HZ. Reversible lanebased traffic network optimization with an advanced traveller information system. Engineering Optimization. 2009;41(1): 87-97. Available from: doi:10.1080/03052150802368799
 Long J, Gao Z, Zhang H, Szeto WY. A turning restriction design problem in urban road networks. European Journal of Operational Research. 2010;206: 569-578. Available from: doi:10.1016/j.ejor.2010.03.013
 Liu H, Wang DZW. Modeling and solving discrete network design problem with stochastic user equilibrium. Journal of Advanced Transportation. 2016;50: 1295-1313. Available from: doi:10.1002/atr.1402
 Dimitriou L, Tsekeris T, Stathopoulos A. Genetic computation of road network design and pricing Stackelberg games with multi-class users. In: Giacobini, M, et al. (eds.) Applications of Evolutionary Computing. Berlin, Heidelberg: Springer: 2008. p. 669-678. Available from: doi:10.1007/978-3-540-78761-7_73
 Gallo M, D’Acierno L, Montella B. A meta-heuristic approach for solving the Urban Network Design Problem. European Journal of Operational Research. 2010;201: 144-157. Available from: doi:10.1016/j.ejor.2009.02.026
 Wardrop JG. Some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers. 1952;1(3): 325-362. Available from: doi:10.1680/ipeds.1952.11259
 Beckmann M, McGuire CB, Winsten CB. Studies in the Economics of Transportation. New Haven: Yale University Press; 1956.
 Frank M, Wolfe P. An algorithm for quadratic programming. Naval Research Logistics Quarterly. 1956;3(1-2): 95-110. Available from: doi:10.1002/nav.3800030109
 Storn R, Price K. Differential evolution: A simple and efficient adaptive scheme for global optimization over continuous spaces. ICSI, USA. Tech. Rep: TR-95-012, 1995.
 Allsop RE. Some possibilities for using traffic control to influence trip distribution and route choice. In: Proceedings of the 6th International Symposium on Transportation and Traffic Theory, 26-28 August 1974, Sydney, Australia. New York, USA: Elsevier Publishing Company; 1974. Vol. 6. p. 345-373.
 Friesz TL, Cho HJ, 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. Available from: doi:10.1287/trsc.26.1.18
 Yang H, Yagar S. Traffic assignment and signal control in saturated road networks. Transportation Research Part A. 1995;29(2): 125-139. Available from: doi:10.1016/0965-8564(94)E0007-V
 Luathep P, Sumalee A, Lam WHK, Li ZC, Lo HK. Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach. Transportation Research Part B. 2011;45(6): 808-827. Available from: doi:10.1016/j.trb.2011.02.002
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).