Improving the Performance of the Bilevel Solution for the Continuous Network Design Problem

Keywords: continuous network design, capacity enhancement, mutual interaction, user equilibrium

Abstract

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.

Author Biographies

Ozgur Baskan, Pamukkale University

Associate Professor, Ph.D., Transportation Division, Department of Civil Engineering, Pamukkale University

Cenk Ozan, Adnan Menderes University
Assistant Professor, Ph.D., Transportation Division, Department of Civil Engineering, Adnan Menderes University
Mauro Dell’Orco, Polytechnic University of Bari
D.I.C.A.T.E.Ch. – Polytechnic University of Bari

References

[1] Baskan O. Harmony search algorithm for continuous network design problem with link capacity expansions. KSCE Journal of Civil Engineering. 2014;18(1): 273-283. Available from: doi:10.1007/s12205-013-0122-6
[2] 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
[3] 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
[4] 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
[5] 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.
[6] Marcotte P. Network optimization with continuous control parameters. Transportation Science. 1983;17(2): 181-197. Available from: doi:10.1287/trsc.17.2.181
[7] 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
[8] 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
[9] 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
[10] 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
[11] 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
[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
[13] 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
[14] 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)
[15] Wang DZW, Lo HK. Global optimum of the linearized network design problem with equilibrium flows. Transportation Research Part B. 2010;44(4): 482-492. Available from: doi:10.1016/j.trb.2009.10.003
[16] 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
[17] 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
[18] 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
[19] 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
[20] 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
[21] 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
[22] 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
[23] 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
[24] 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
[25] 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
[26] 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
[27] 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
[28] 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
[29] 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
[30] 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
[31] 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
[32] 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
[33] Beckmann M, McGuire CB, Winsten CB. Studies in the Economics of Transportation. New Haven: Yale University Press; 1956.
[34] 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
[35] 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.
[36] 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.
[37] 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
[38] 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
[39] 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
Published
2018-12-27
How to Cite
1.
Baskan O, Ozan C, Dell’Orco M, Marinelli M. Improving the Performance of the Bilevel Solution for the Continuous Network Design Problem. Promet - Traffic & Transportation [Internet]. 27Dec.2018 [cited 26Mar.2019];30(6):709-20. Available from: https://traffic.fpz.hr/index.php/PROMTT/article/view/2789
Section
Articles