Improving the Performance of the Bilevel Solution for the Continuous Network Design Problem
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.
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.
Copyright (c) 2018 Ozgur Baskan, Cenk Ozan, Mauro Dell’Orco, Mario Marinelli
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).
