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

Baskan O. Harmony search algorithm for continuous network design problem with link capacity expansions. KSCE Journal of Civil Engineering. 2014; 18(1): 273-283. DOI: 10.1007/s12205-013-0122-6.

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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. DOI: 10.1061/(ASCE)0733-947X(2009)135:7(406).

Wang DZW, Lo HK. Global optimum of the linearized network design problem with equilibrium flows. Transportation Research Part B. 2010; 44(4): 482–492. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. DOI: 10.1007/s11518-007-5034-x

Wu JJ, Sun HJ, Gao ZY, Zhang HZ. Reversible lane-based traffic network optimization with an advanced traveller information system. Engineering Optimization. 2009; 41(1): 87-97. 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. 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. 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.etal.(Eds.),Applications of Evolutionary Computing. 2008; 669–678. Springer, Berlin, Heidelberg. 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. 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. 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. DOI: 10.1002/nav.3800030109.

Sheffi Y. Urban Transport Networks: Equilibrium Analysis with Mathematical Programming Methods. New Jersey, USA: Prentice-Hall Inc.; 1985.

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.

Liu H, Cai Z, Wang Y. Hybridizing particle swarm optimization with differential evolution for constrained numerical and engineering optimization. Applied Soft Computing. 2010; 10(2): 629-640. DOI: 10.1016/j.asoc.2009.08.031.

Allsop RE. Some possibilities for using traffic control to influence trip distribution and route choice. In: Proc., 6th International Symposium on Transportation and Traffic Theory, 26-28 August 1974, New York, USA. Elsevier; 1974. 6: 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. 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. 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. 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 [Internet]. 2018Dec.27 [cited 2019Jun.20];30(6):709-20. Available from: https://traffic.fpz.hr/index.php/PROMTT/article/view/2789
Section
Articles