×

Multi-objective discrete urban road network design. (English) Zbl 1348.90159

Summary: This paper addresses the problem of designing urban road networks in a multi-objective decision making framework. Given a base network with only two-way links, and the candidate lane addition and link construction projects, the problem is to find the optimal combination of one-way and two-way links, the optimal selection of network capacity expansion projects, and the optimal lane allocations on two-way links to optimize the reserve capacity of the network, and two new travel time related performance measures. The problem is considered in two variations; in the first scenario, two-way links may have different numbers of lanes in each direction and in the second scenario, two-way links must have equal number of lanes in each direction. The proposed variations are formulated as mixed-integer programming problems with equilibrium constraints. A hybrid genetic algorithm, an evolutionary simulated annealing, and a hybrid artificial bee colony algorithm are proposed to solve these two new problems. A new measure is also proposed to evaluate the effectiveness of the three algorithms. Computational results for both problems are presented.

MSC:

90B10 Deterministic network models in operations research
90C29 Multi-objective and goal programming
90C59 Approximation methods and heuristics in mathematical programming

Software:

ABC
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Abdulaal, M.; LeBlanc, L. J., Continuous equilibrium network design models, Transportation Research Part B, 13, 1, 19-32 (1979)
[2] Allsop, R. E., Estimating the traffic capacity of a signalized road junction, Transportation Research, 6, 245-255 (1972)
[3] Alzaqebah, M.; Abullah, S., Hybrid artificial bee colony search algorithm based on disruptive selection for examination timetabling problems, Lecture Notes in Computer Science, 6831, 31-45 (2011) · Zbl 1342.68308
[4] Aydin, M. E.; Fogarty, T. C., A distributed evolutionary simulated annealing algorithm for combinatorial optimization problems, Journal of Heuristics, 10, 3, 269-292 (2004)
[6] Ben-Ayed, O.; Boyce, D. E.; Blair, C. E., A general bilevel linear programming formulation of the network design problem, Transportation Research Part B, 22, 4, 311-318 (1988)
[7] Cantarella, G. E.; Pavone, G.; Vitetta, A., Heuristics for urban road network design: lane layout and signal settings, European Journal of Operational Research, 175, 3, 1682-1695 (2006) · Zbl 1142.90345
[8] Cantarella, G. E.; Vitetta, A., The multi-criteria road network design problem in an urban area, Transportation, 33, 6, 567-588 (2006)
[9] Chen, O. J.; Ben-Akiva, M. E., Game-theoretic formulations of interaction between dynamic traffic control and dynamic traffic assignment, Transportation Research Record, 1617, 179-188 (1998)
[10] Chen, A.; Kim, J.; Zhou, Z.; Chootinan, P., Alpha reliable network design problem, Transportation Research Record, 2029, 49-57 (2007)
[11] Chen, A.; Subprasom, K.; Ji, Z., A Simulation-based Multi-objective Genetic Algorithm (SMOGA) for build-operate-transfer network design problem, Optimization and Engineering Journal, 7, 3, 225-247 (2006) · Zbl 1138.90466
[12] Chen, A.; Yang, C., Stochastic transportation network design problem with spatial equity constraint, Transportation Research Record, 1882, 97-104 (2004)
[14] Dahl, G.; Minken, H., Methods based on discrete optimization for finding road network rehabilitation strategies, Computers & Operations Research, 35, 7, 2193-2208 (2008) · Zbl 1180.90051
[15] Dantzig, G. B.; Harvey, R. P.; Lansdowne, Z. F.; Robinson, D. W.; Maier, S. F., Formulating and solving the network design problem by decomposition, Transportation Research Part B, 13, 1, 5-17 (1979)
[16] Drezner, Z.; Salhi, S., Selecting a good configuration of one-way and two-way routes using tabu search, Control and Cybernetics, 29, 3, 725-740 (2000) · Zbl 0983.90004
[17] Drezner, Z.; Salhi, S., Using hybrid metaheuristics for the one-way and two-way network design problem, Naval Research Logistics, 49, 5, 449-463 (2002) · Zbl 1013.90013
[18] Drezner, Z.; Wesolowsky, G. O., Selecting an optimum configuration of one-way and two-way routes, Transportation Science, 31, 4, 386-394 (1997) · Zbl 0919.90056
[19] Drezner, Z.; Wesolowsky, G. O., Network design: selection and design of links and facility location, Transportation Research Part A, 37, 3, 241-256 (2003)
[21] Fisk, C. S., Game theory and transportation systems modeling, Transportation Research Part B, 18, 4-5, 301-313 (1984)
[22] Friesz, T. L., Transportation network equilibrium, design and aggregation: key developments and research opportunities, Transportation Research Part A, 19, 5-6, 413-427 (1985)
[23] Friesz, T. L.; Anandalingam, G.; 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
[24] Friesz, T. L.; Harker, P. T., Properties of the iterative optimization-equilibrium algorithm, Civil Engineering Systems, 2, 142-154 (1985)
[25] Gallo, M.; D’Acierno, L.; Montella, B., A meta-heuristic approach for solving the urban network design problem, European Journal of Operational Research, 201, 1, 144-157 (2010) · Zbl 1177.90052
[26] Gao, Z.; Wu, J.; Sun, H., Solution algorithm for the bi-level discrete network design problem, Transportation Research Part B, 39, 6, 479-495 (2005)
[27] Gen, M.; Cheng, R., Genetic algorithms and engineering optimization (2000), John Wiley and Sons: John Wiley and Sons New York, USA
[29] Holland, J. H., Adaptation in natural and artificial systems (1975), The University of Michigan Press: The University of Michigan Press Michigan, USA
[30] Karaboga, D., An idea based on honey bee swarm for numerical optimization (2005), Erciyes University, Engineering Faculty, Computer Engineering Department, Technical report-TR06
[31] Karaboga, D.; Basturk, B., On the performance of artificial bee colony (ABC) algorithm, Applied Soft Computing, 8, 1, 687-697 (2008)
[32] LeBlanc, L. J., An algorithm for the discrete network design problem, Transportation Science, 9, 3, 183-199 (1975)
[33] LeBlanc, L. J.; Morlok, E. K.; Pierskalla, W. P., An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation Research, 9, 309-318 (1975)
[34] Lee, C. K.; Yang, K. I., Network design of one-way streets with simulated annealing, Papers in Regional Science, 73, 2, 119-134 (1994)
[35] Lo, H. K.; Szeto, W. Y., Time-dependent transport network design under cost-recovery, Transportation Research Part B, 43, 1, 142-158 (2009)
[37] Luathep, P.; Sumalee, A.; Lam, W. H.K; Li, Z. C.; Lo, H. K., Global optimization method for mixed transportation network design problem: a mixed-integer linear programming approach, Transportation Research Part B, 45, 5, 808-827 (2011)
[38] Magnanti, T. L.; Wong, R. T., Network design and transportation planning: models and algorithms, Transportation Science, 18, 1, 1-55 (1984)
[39] Meng, Q.; Yang, H.; Bell, M. G.H., An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem, Transportation Research Part B, 35, 1, 83-105 (2001)
[40] Meng, Q.; Yang, H., Benefit distribution and equity in road network design, Transportation Research Part B, 36, 11, 19-35 (2002)
[41] Meng, Q.; Khoo, H. L., Optimizing contraflow scheduling problem: model and algorithm, Journal of Intelligent Transportation Systems, 12, 3, 126-138 (2008) · Zbl 1171.90401
[42] Meng, Q.; Ling, H.; Cheu, R. L., Microscopic traffic simulation model-based optimization approach for the contraflow lane configuration problem, Journal of Transportation Engineering-ASCE, 134, 1, 41-49 (2008)
[43] Miandoabchi, E.; Farahani, R. Z., Optimizing reserve capacity of urban road networks in a discrete network design problem, Advances in Engineering Software, 42, 12, 1041-1050 (2011) · Zbl 1239.90014
[44] Miandoabchi, E.; Farahani, R. Z.; 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
[45] Migdalas, A., Bilevel programming in traffic planning: models, methods, and challenge, Journal of Global Optimization, 7, 4, 381-405 (1995) · Zbl 0844.90050
[46] Nagurney, A., Comparative tests of multimodal traffic equilibrium methods, Transportation Research Part B, 18, 6, 469-485 (1984)
[47] Nguyen, S.; Dupuis, C., An efficient method for computing traffic equilibria in networks with asymmetric transportation costs, Transportation Science, 18, 2, 185-202 (1984)
[48] Pacheco, J.; Alvarez, A.; Casado, S.; González-Velarde, J. L., A tabu search approach to an urban transport problem in Northern Spain, Computers & Operations Research, 36, 3, 967-979 (2009) · Zbl 1157.90475
[50] Poorzahedy, H.; Abulghasemi, F., Application of ant system to network design problem, Transportation, 32, 3, 251-273 (2005)
[51] Poorzahedy, H.; Rouhani, O. M., Hybrid meta-heuristic algorithms for solving network design problem, European Journal of Operational Research, 182, 2, 578-596 (2007) · Zbl 1121.90024
[52] Poorzahedy, H.; Turnquist, M. A., Approximate algorithms for the discrete network design problem, Transportation Research Part B, 16, 1, 45-55 (1982)
[53] Russo, F.; Vitetta, A., A topological method to choose optimal solutions after solving the multi-criteria urban road network design problem, Transportation, 33, 4, 347-370 (2006)
[54] Sadiq, A. T.; Hamad, A. G., BSA: a hybrid bees’ simulated annealing algorithm to solve optimization & NP-complete problems, Engineering & Technology Journal, 28, 2, 271-281 (2010)
[55] Sheffi, Y., Urban transportation networks: equilibrium analysis with mathematical programming methods (1985), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ, USA
[56] Steenbrink, P. A., Optimization of transportation networks (1974), John Wiley & Sons: John Wiley & Sons New York, USA
[57] Steenbrink, P. A., Transport network optimization in the Dutch integral transportation study, Transportation Research, 8, 1, 11-27 (1974)
[58] Szeto, W. Y.; Lo, H. K., Strategies for road network design over time: robustness under uncertainty, Transportmetrica, 1, 1, 47-63 (2005)
[59] Szeto, W. Y.; Lo, H. K., Transportation network improvement and tolling strategies: the issue of intergeneration equity, Transportation Research Part A, 40, 3, 227-243 (2006)
[60] Szeto, W. Y.; Lo, H. K., Time-dependent transport network improvement and tolling strategies, Transportation Research Part A, 42, 2, 376-391 (2008)
[61] Szeto, W. Y.; Jaber, X. Q.; O’Mahony, M., Time-dependent discrete network design frameworks considering land use, Computer-Aided Civil and Infrastructure Engineering, 25, 6, 411-426 (2010)
[62] Szeto, W. Y.; Wu, Y. Z., A simultaneous bus route design and frequency setting problem for Tin Shui Wai, Hong Kong, European Journal of Operations Research, 209, 1, 141-155 (2011) · Zbl 1208.90023
[63] Szeto, W. Y.; Wu, Y. Z.; Ho, S. C., An artificial bee colony algorithm for the capacitated vehicle routing problem, European Journal of Operational Research, 215, 126-135 (2011)
[64] Szeto, W. Y.; Jiang, Y., Hybrid artificial bee colony algorithm for transit network design, Transportation Research Record, 2284, 47-56 (2012)
[66] Teodorović, D.; Edara, P., A real-time road pricing system: the case of a two-link parallel network, Computers and Operations Research, 34, 1, 2-27 (2007) · Zbl 1109.90013
[67] Teklu, F.; Sumalee, A.; Watling, D. P., A genetic algorithm approach for optimising traffic control signals considering routing, Journal of Computer-Aided Civil and Infrastructure Engineering, 22, 1, 31-43 (2007)
[68] Tobin, R. L.; Friesz, T. L., Sensitivity analysis for equilibrium network flow, Transportation Science, 22, 4, 242-250 (1988) · Zbl 0665.90031
[69] Wardrop, J. G., Some theoretical aspects of road traffic research, Proceedings of the Institute of Civil Engineers Part II, 1, 325-378 (1952)
[70] Webster, F. V.; Cobbe, B. M., Traffic signal. Road research technical paper no. 56 (1966), HMSO: HMSO London, UK
[71] Wong, S. C., On the reserve capacities of priority junctions and roundabouts, Transportation Research Part B, 30, 6, 441-453 (1996)
[72] Yang, H., Heuristic algorithms for the bilevel origin-destination matrix estimation problem, Transportation Research Part B, 29, 4, 231-242 (1995)
[73] Yang, H.; Bell, M. G.H., Models and algorithms for road network design: a review and some new developments, Transport Reviews, 18, 3, 257-278 (1998)
[74] Yang, H.; Bell, M. G.H., A capacity paradox in network design and how to avoid it, Transportation Research Part A, 32, 7, 539-545 (1998)
[75] Yang, H.; Yagar, S.; Iida, Y.; Asakura, Y., An algorithm for the inflow control problem on urban freeway networks with user-optimal flows, Transportation Research Part B, 28, 2, 123-139 (1994)
[76] Yang, H.; Wang, J. Y.T., Travel time minimization versus reserve capacity maximization in the network design problem, Transportation Research Record, 1783, 17-26 (2002)
[77] Yang, X. S., Engineering optimizations via nature-inspired virtual bee algorithms, Lecture Notes in Computer Science, 3562, 317-323 (2005)
[78] Zhang, H.; Gao, Z., Bilevel programming model and solution method for mixed transportation network design problem, Journal of Systems Science and Complexity, 22, 446-459 (2009) · Zbl 1193.49041
[79] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evolutionary Computation, 8, 2, 173-195 (2000)
[80] Ziyou, G.; Yifan, S., A reserve capacity model of optimal signal control with user-equilibrium route choice, Transportation Research Part B, 36, 4, 313-323 (2002)
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.