×

A bi-objective turning restriction design problem in urban road networks. (English) Zbl 1304.90061

Summary: We introduce a bi-objective turning restriction design problem (BOTRDP), which aims to simultaneously improve network traffic efficiency and reduce environmental pollution by implementing turning restrictions at selected intersections. A bi-level programming model is proposed to formulate the BOTRDP. The upper level problem aims to minimize both the total system travel time (TSTT) and the cost of total vehicle emissions (CTVE) from the viewpoint of traffic managers, and the lower level problem depicts travelers’ route choice behavior based on stochastic user equilibrium (SUE) theory. The modified artificial bee colony (ABC) heuristic is developed to find Pareto optimal turning restriction strategies. Different from the traditional ABC heuristic, crossover operators are captured to enhance the performance of the heuristic. The computational experiments show that incorporating crossover operators into the ABC heuristic can indeed improve its performance and that the proposed heuristic significantly outperforms the non-dominated sorting genetic algorithm (NSGA) even if different operators are randomly chosen and used in the NSGA as in our proposed heuristic. The results also illustrate that a Pareto optimal turning restriction strategy can obviously reduce the TSTT and the CTVE when compared with those without implementing the strategy, and that the number of Pareto optimal turning restriction designs is smaller when the network is more congested but greater network efficiency and air quality improvement can be achieved. The results also demonstrate that traffic information provision does have an impact on the number of Pareto optimal turning restriction designs. These results should have important implications on traffic management.

MSC:

90B20 Traffic problems in operations research
90C29 Multi-objective and goal programming
90C35 Programming involving graphs or networks
90C59 Approximation methods and heuristics in mathematical programming

Software:

ABC; TRANSYT-7F
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Akamatsu, T., Cyclic flows, Markov process and stochastic traffic assignment, Transportation Research B, 30, 5, 369-386 (1996)
[2] Akbari, R.; Hedayatzadeh, R.; Ziarati, K.; Hassanizadeh, B., A multi-objective artificial bee colony algorithm, Swarm and Evolutionary Computation, 2, 39-52 (2012)
[3] Armentano, V. A.; Claudio, J. E., An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem, Journal of Heuristics, 10, 5, 463-481 (2004) · Zbl 1062.90057
[4] Bach, W., Atmospheric pollution (1972), McGraw-Hill Book Company: McGraw-Hill Book Company USA
[6] Bekhor, S.; Toledo, B., Investigating path-based solution algorithms to the stochastic user equilibrium problem, Transportation Research Part B, 39, 3, 279-295 (2005)
[7] Blum, J. R., Multidimensional stochastic approximation methods, Annals of Mathematical Statistics, 25, 4, 737-744 (1954) · Zbl 0056.38305
[8] Cantarella, G. E., A general fixed-point approach to multimode multi-user equilibrium assignment with elastic demand, Transportation Science, 31, 2, 107-128 (1997) · Zbl 0886.90071
[9] Cantarella, G. E.; Pavone, G.; Vitetta, A., Heuristics for urban road network design: Lane layout and signal settings, European Journal of Operational Research, 175, 1682-1695 (2006) · Zbl 1142.90345
[10] Cantarella, G. E.; Vitetta, A., The multi-criteria road network design problem in an urban area, Transportation, 33, 567-588 (2006)
[11] Chan, C. K.; Yao, X. H., Air pollution in mega cities in China, Atmospheric Environment, 42, 1, 1-42 (2008)
[12] Chen, M. Y.; Alfa, A. S., Algorithms for solving Fisk’s stochastic traffic assignment model, Transportation Research Part B, 25, 6, 405-412 (1991)
[13] Chen, M. Y.; Alfa, A. S., A network design algorithm using a stochastic incremental traffic assignment approach, Transportation Science, 25, 3, 215-224 (1991) · Zbl 0729.90985
[14] Chen, A.; Kim, J.; Lee, S.; Kim, Y., Stochastic multi-objective models for network design problem, Expert Systems with Applications, 37, 2, 1608-1619 (2010)
[15] Chen, A.; Lee, D.; Jayakrishnan, R., Computational study of state-of-the-art path-based traffic assignment algorithms, Mathematics and Computers in Simulation, 59, 6, 509-518 (2002) · Zbl 1030.90012
[16] Chen, A.; Subprasom, K.; Ji, Z., A simulation-based multi-objective genetic algorithm (SMOGA) procedure for BOT network design problem, Optimization and Engineering, 7, 3, 225-247 (2006) · Zbl 1138.90466
[17] Chung, S. H.; Weaver, R. D.; Friesz, T. L., Strategic response to pollution taxes in supply chain networks: Dynamic, spatial, and organizational dimensions, European Journal of Operational Research, 231, 2, 314-327 (2013) · Zbl 1317.91014
[18] Daganzo, C. F., Stochastic network equilibrium with multiple vehicle types and asymmetric, indefinite link cost Jacobians, Transportation Science, 17, 3, 282-300 (1983)
[19] Deb, K.; Pratap, A.; Agarwal, S.; Meyarivan, T., A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6, 2, 182-197 (2002)
[20] Deb, K.; Sinha, A., An efficient and accurate solution methodology for bilevel multiobjective programming problems using a hybrid evolutionary-local-search algorithm, Evolutionary Computation Journal, 18, 3, 403-449 (2010)
[21] Demir, E.; Bektaş, T.; Laporte, G., An adaptive large neighborhood search heuristic for the pollution-routing problem, European Journal of Operational Research, 223, 2, 346-359 (2012) · Zbl 1292.90045
[22] Demir, E.; Bektaş, T.; Laporte, G., The bi-objective pollution-routing problem, European Journal of Operational Research, 232, 3, 464-478 (2014) · Zbl 1305.90053
[23] Dial, R. B., A probabilistic multipath traffic assignment model which obviates path enumeration, Transportation Research, 5, 2, 83-111 (1971)
[24] Farahani, R. Z.; Miandoabchi, E.; Szeto, W. Y.; Rashidi, H., A review of urban transportation network design problems, European Journal of Operational Research, 229, 2, 281-302 (2013) · Zbl 1317.90047
[25] Fernandez, E.; Lopez, E.; Lopez, F.; Coello, C. A., Increasing selective pressure towards the best compromise in evolutionary multiobjective optimization: The extended NOSGA method, Information Sciences, 181, 1, 44-56 (2011) · Zbl 1206.90160
[27] Friesz, T. L.; Anandalingham, A.; Mehta, N. J.; Nam, K.; Shah, S. J.; Tobin, R. L., The multiobjective equilibrium network design problem revisited: A simulated annealing approach, European Journal of Operational Research, 65, 1, 44-57 (1993) · Zbl 0772.90043
[28] Fu, L.; Hao, J.; He, D.; He, K., Assessment of vehicular pollution in China, Journal of the Air and Waste Management Association, 51, 5, 658-668 (2001)
[29] Gen, M.; Cheng, R.; Lin, L., Network models and optimization: Multiobjective genetic algorithm approach (2008), Springer: Springer Heidelberg · Zbl 1193.90006
[30] Gokhale, S., Impacts of traffic-flows on vehicular-exhaust emissions at traffic junctions, Transportation Research Part D, 17, 1, 21-27 (2012)
[31] Goldberg, D., Genetic algorithms in search, optimization and machine learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[32] Goyal, S. K.; Ghatge, S. V.; Nema, P.; Tamhane, S. M., Understanding urban vehicular pollution problem vis-a-vis ambient air quality - Case study of megacity (Delhi, India), Environmental Monitoring and Assessment, 119, 1-3, 557-569 (2006)
[33] Horowitz, A. J., Intersection delay in region wide traffic assignment: Implications of 1994 update of the highway capacity manual, Transportation Research Record, 1572, 1-8 (1997)
[34] Huang, H. J., A combined algorithm for solving and calibrating the stochastic traffic assignment model, Journal of Operational Research Society, 46, 8, 977-987 (1995) · Zbl 0832.90035
[35] Huang, H. J.; Bell, M. G.H., A study on logit assignment which excludes all cyclic flows, Transportation Research B, 32, 6, 401-412 (1998)
[36] Huang, H. J.; Li, Z. C., A multiclass, multicriteria logit-based traffic equilibrium assignment model under ATIS, European Journal of Operational Research, 176, 3, 1464-1477 (2007) · Zbl 1113.90020
[37] Ishibuchi, H.; Murata, T., A multiobjective genetic local search algorithm and its application to flowshop scheduling, IEEE Transactions on Systems, Man, and Cybernetics, 28, 3, 392-403 (1998)
[38] Jaeggi, D. M.; Parks, G. T.; Kipouros, T.; Clarkson, P. J., The development of a multi-objective Tabu search algorithm for continuous optimisation problems, European Journal of Operational Research, 185, 3, 1192-1212 (2008) · Zbl 1175.90354
[39] Jones, D. F.; Mirrazavi, S. K.; Tamiz, M., Multi-objective meta-heuristics: An overview of the current state-of-the-art, European Journal of Operational Research, 137, 1, 1-9 (2002) · Zbl 1002.90060
[41] Karaboga, N., A new design method based on artificial bee colony algorithm for digital IIR filters, Journal of the Franklin Institute, 346, 4, 328-348 (2009) · Zbl 1166.93351
[42] Karaboga, D., Artificial bee colony algorithm, Scholarpedia, 5, 3, 6915 (2010)
[43] Karaboga, D.; Basturk, B., On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing, 8, 1, 687-697 (2008)
[44] Konak, A., Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation, European Journal of Operational Research, 218, 1, 829-837 (2012)
[45] Leblanc, L. J.; Morlok, E. K.; Pierskalla, W. P., An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation Research, 9, 5, 309-318 (1975)
[46] Liu, H.; He, X.; He, B., Method of successive weighted averages (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem, Networks and Spatial Economics, 9, 4, 485-503 (2009) · Zbl 1178.90066
[47] Lo, H. K.; Szeto, W. Y., A methodology for sustainable traveller information services, Transportation Research Part B, 36, 2, 113-130 (2002)
[48] Lo, H. K.; Szeto, W. Y., Road pricing modeling for hyper-congestion, Transportation Research Part A, 39, 7-9, 705-722 (2005)
[49] Lo, H. K.; Szeto, W. Y., Time-dependent transport network design under cost-recovery, Transportation Research Part B, 43, 1, 142-158 (2009)
[50] Long, J. C.; Gao, Z. Y.; Zhang, H. Z.; Szeto, W. Y., A turning restriction design problem in urban road networks, European Journal of Operational Research, 206, 3, 569-578 (2010) · Zbl 1188.90050
[51] Maher, M., Algorithms for logit-based stochastic user equilibrium assignment, Transportation Research Part B, 32, 8, 539-549 (1998)
[52] Mayeres, I.; Ochelen, S.; Proost, S., The marginal external costs of urban transport, Transportation Research Part D, 1, 2, 111-130 (1996)
[53] Meng, Q.; Lee, D. H.; Cheu, R. L.; Yang, H., Logit based stochastic user equilibrium problem for entry exit toll schemes, Journal of Transportation Engineering ASCE, 130, 6, 787-795 (2004)
[54] Meng, Q.; Liu, Z., Trial-and-error method for congestion pricing scheme under side-constrained probit-based stochastic user equilibrium conditions, Transportation, 38, 11, 819-843 (2011)
[55] Miandoabchi, E.; Daneshzand, F.; Szeto, W. Y.; Farahani, R. Z., Multi-objective discrete urban road network design, Computers & Operations Research, 40, 10, 2429-2449 (2013) · Zbl 1348.90159
[56] Miandoabchi, E.; Farahani, Z. R.; Dullaert, W.; Szeto, W. Y., Hybrid evolutionary metaheuristics for concurrent multi-objective design of urban road and public transit networks, Networks and Spatial Economics, 12, 3, 441-480 (2012) · Zbl 1332.90051
[57] Miandoabchi, E.; Farahani, Z. R.; Szeto, W. Y., Bi-objective bimodal urban road network design using hybrid metaheuristics, Central European Journal of Operations Research, 20, 4, 583-621 (2012) · Zbl 1339.90062
[58] Ng, M. W.; Lo, H. K., Regional air quality conformity in transportation networks with stochastic dependencies: A theoretical copula-based model, Networks and Spatial Economics, 13, 4, 373-397 (2013) · Zbl 1332.86013
[59] Omkar, S. N.; Senthilnath, J.; Khandelwal, R.; Naik, G. N.; Gopalakrishnan, S., Artificial bee colony (ABC) for multi-objective design optimization of composite structures, Applied Soft Computing, 11, 1, 489-499 (2011)
[60] Orubu, C. O., Using transportation control measures and economic instruments to reduce air pollution due to automobile emissions, Journal of Social Science, 8, 3, 227-236 (2004)
[61] Pandian, S.; Gokhale, S.; Ghoshal, A. K., Evaluating effects of traffic and vehicle characteristics on vehicular emissions near traffic intersections, Transportation Research Part D, 14, 3, 180-196 (2009)
[62] Penic, M. A.; Upchurch, J., TRANSYT-7F: Enhancement for fuel consumption, pollution emissions, and user costs, Transportation Research Record, 1360, 104-111 (1992)
[63] Powell, W. B.; Sheffi, Y., The convergence of equilibrium algorithms with predetermined step sizes, Transportation Science, 16, 1, 45-55 (1982)
[64] Robbins, H.; Monro, S., A stochastic approximation method, Annals of Mathematical Statistics, 22, 3, 400-407 (1951) · Zbl 0054.05901
[66] Sharma, S.; Ukkusuri, S. V.; Mathew, T. V., Pareto optimal multiobjective optimization for robust transportation network design problem, Transportation Research Record, 2090, 95-104 (2009)
[67] Sheffi, Y., Urban transportation networks: Equilibrium analysis with mathematical programming methods (1985), Prentice-Hall: Prentice-Hall Englewood Cliffs, New Jersey, USA
[68] Sheffi, Y.; Powell, W. B., An algorithm for the equilibrium assignment problem with random link times, Networks, 12, 2, 191-207 (1982) · Zbl 0485.90082
[69] Shepherd, S. P.; Sumalee, A., A genetic algorithm based approach to optimal toll level and location problem, Networks and Spatial Economics, 4, 161-179 (2004) · Zbl 1079.90082
[70] Singh, A., An artificial bee colony algorithm for the leaf-constrained minimum spanning tree problem, Applied Soft Computing, 9, 2, 625-631 (2009)
[71] Sohn, K., Multi-objective optimization of a road diet network design, Transportation Research Part A, 45, 6, 499-511 (2011)
[72] Srinivas, N.; Deb, K., Multiobjective optimization using nondominated sorting genetic algorithms, Evolutionary Computation, 2, 3, 221-248 (1994)
[73] Suppapitnarm, A.; Seffen, K. A.; Parks, G. T.; Clarkson, P. J., A simulated annealing algorithm for multiobjective optimization, Engineering Optimization, 33, 1, 59-85 (2000)
[75] Szeto, W. Y.; Jaber, X. Q.; Wong, S. C., Road network equilibrium approaches to environmental sustainability, Transport Reviews, 32, 491-518 (2012)
[76] Szeto, W. Y.; Jiang, Y., Hybrid artificial bee colony algorithm for transit network design, Transportation Research Record, 2284, 47-56 (2012)
[77] Szeto, W. Y.; Jiang, Y.; Sumalee, A., A cell-based model for multi-class doubly stochastic dynamic traffic assignment, Computer-Aided Civil and Infrastructure Engineering, 26, 8, 595-611 (2011)
[78] Szeto, W. Y.; Jiang, Y.; Wang, D. Z.W.; Sumalee, A., A sustainable road network design problem with land use transportation interaction over time, Networks and Spatial Economics (2013) · Zbl 1338.90115
[79] Szeto, W. Y.; Lo, H. K., Time-dependent transport network improvement and tolling strategies, Transportation Research Part A, 42, 2, 376-391 (2008)
[80] Szeto, W. Y.; Wang, Y.; Wong, S. C., The chemical reaction optimization approach to solving the environmentally sustainable network design problem, Computer-Aided Civil and Infrastructure Engineering, 29, 2, 373-397 (2014)
[81] Szeto, W. Y.; Wu, Y.; Ho, S. C., An artificial bee colony algorithm for the capacitated vehicle routing problem, European Journal of Operational Research, 215, 1, 126-135 (2011)
[82] Teklu, F.; Sumalee, A.; Watling, D. P., A genetic algorithm approach for optimising traffic control signals considering routing, Computer-Aided Civil and Infrastructure Engineering, 22, 1, 31-43 (2007)
[83] Uno, T.; Katagiri, H., Single- and multi-objective defensive location problems on a network, European Journal of Operational Research, 188, 1, 76-84 (2008) · Zbl 1135.90022
[84] Vilcot, G.; Billaut, J. C., A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem, European Journal of Operational Research, 190, 2, 398-411 (2008) · Zbl 1146.90427
[85] Whittaker, G.; Confesorjr, R.; Griffith, S.; Fare, R.; Grosskopf, S.; Steiner, J.; Muellerwarrant, G.; Banowetz, G. M., A hybrid genetic algorithm for multiobjective problems with activity analysis-based local search, European Journal of Operational Research, 193, 1, 195-203 (2009) · Zbl 1152.90603
[86] Xu, T.; Wei, H.; Wang, Z. D., Study on continuous network design problem using simulated annealing and genetic algorithm, Expert Systems with Applications, 36, 2, 2735-2741 (2009)
[87] Yin, Y., Genetic-algorithm-based approach for bilevel programming models, Journal of Transportation Engineering, 126, 2, 115-120 (2000)
[88] Yin, Y., Multiobjective bilevel optimization for transportation planning and management problems, Journal of Advanced Transportation, 36, 1, 93-105 (2002)
[89] Zhang, H.; Zhu, Y.; Zou, W.; Yan, X., A hybrid multi-objective artificial bee colony algorithm for burdening optimization of copper strip production, Applied Mathematical Modelling, 36, 6, 2578-2591 (2012) · Zbl 1246.90165
[90] Zheng, Y.; Wan, Z.; Wang, G., A fuzzy interactive method for a class of bilevel multiobjective programming problem, Expert Systems with Applications, 38, 8, 10384-10388 (2011)
[91] Zhu, F.; Lo, H. K.; Lin, H. Z., Delay and emissions modelling for signalised intersections, Transportmetrica B: Transport Dynamics, 1, 2, 111-135 (2013)
[92] Zitzler, E.; Thiele, L., Multiobjective evolutionary algorithms: A comparative case study and the strength Pareto approach, IEEE Transactions on Evolutionary Computation, 3, 4, 257-271 (1999)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.