×

Optimizing reserve capacity of urban road networks in a discrete network design problem. (English) Zbl 1239.90014

Summary: We address the problem of designing of street directions and lane additions in urban road networks, based on the concept of reserve capacity. Reserve capacity is identified by the largest multiplier applied to a given existing demand matrix, that can be allocated to a network without violating the arc capacities. Having a two-way streets base network and the allowable street lane additions, the problem is to find the optimum configuration of street directions and two-way street lane allocations, and the optimum selection of street lane addition projects, in a way that the reserve capacity of the network is maximized. The problem is considered in two variations; in the first variation no restriction is imposed on the symmetricity of lane allocations for two-way streets, and in the second variation, two-way street lane allocations are restricted to be symmetric. The proposed problems are modeled as mixed-integer bi-level mathematical problems. A hybrid genetic algorithm and an evolutionary simulated annealing algorithm are proposed to solve the models. Computational results for both problem variations are presented.

MSC:

90B10 Deterministic network models in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Yang, H.; Bell, M. G. H.: Models and algorithms for road network design: A review and some new developments, Transport rev 18, No. 3, 257-278 (1998)
[2] Steenbrink, P. A.: Optimization of transport network, (1974) · Zbl 0329.14007
[3] Magnanti, T. L.; Wong, R. T.: Network design and transportation planning: models and algorithms, Transport sci 18, No. 1, 1-55 (1984)
[4] Friesz, T. L.: Transportation network equilibrium, design and aggregation: key developments and research opportunities, Transport res part A 19, No. 5 – 6, 413-427 (1985)
[5] Migdalas, A.: Bilevel programming in traffic planning: models, methods, and challenge, J global optim 7, No. 4, 381-405 (1995) · Zbl 0844.90050 · doi:10.1007/BF01099649
[6] Abdulaal, M.; Leblanc, L. J.: Continuous equilibrium network design models, Transport res part B 13, No. 1, 19-32 (1979) · Zbl 0398.90042
[7] Dantzig, G. B.; Harvey, R. P.; Lansdowne, Z. F.; Robinson, D. W.; Maier, S. F.: Formulating and solving the network design problem by decomposition, Transport res part B 13, No. 1, 5-17 (1979)
[8] Meng, Q.; Yang, H.; Bell, M. G. H.: An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem, Transport res part B 35, No. 1, 83-105 (2001)
[9] Meng, Q.; Yang, H.: Benefit distribution and equity in road network design, Transport res part B 36, No. 11, 19-35 (2002)
[10] Chiou, S. W.: Bilevel programming for the continuous transport network design problem, Transport res part B 39, No. 4, 361-383 (2005)
[11] Gao, Z.; Sun, H.; Zhang, H.: A globally convergent algorithm for transportation continuous network design problem, Optim eng 8, No. 3, 241-257 (2007) · Zbl 1175.90061 · doi:10.1007/s11081-007-9015-1
[12] Chiou, S. W.: A hybrid approach for optimal design of signalized road network, Appl math model 32, No. 2, 195-207 (2008) · Zbl 1187.90093 · doi:10.1016/j.apm.2006.11.007
[13] Mathew, T. V.; Shrama, S.: Capacity expansion problem for large urban transportation networks, J transport eng 135, No. 7, 406-415 (2009)
[14] Dimitriou, L.; Stathopoulos, S.; Tsekeris, T.: Reliable stochastic design of road network systems, Int J ind syst eng 3, No. 5, 549-574 (2008)
[15] Wang, D. Z. W.; Lo, H. K.: Global optimum of the linearized network design problem with equilibrium flows, Transport res part B 44, No. 4, 482-492 (2010)
[16] Steenbrink, P. A.: Transport network optimization in the Dutch integral transportation study, Transport res 8, No. 1, 11-27 (1974)
[17] Leblanc, L. J.: An algorithm for the discrete network design problem, Transport sci 9, No. 3, 183-199 (1975)
[18] Poorzahedy, H.; Turnquist, M. A.: Approximate algorithms for the discrete network design problem, Transport res part B 16, No. 1, 45-55 (1982)
[19] Gao, Z.; Wu, J.; Sun, H.: Solution algorithm for the bi-level discrete network design problem, Transport res part B 39, No. 6, 479-495 (2005)
[20] Poorzahedy, H.; Abulghasemi, F.: Application of ant system to network design problem, Transportation 32, No. 3, 251-273 (2005)
[21] Poorzahedy, H.; Rouhani, O. M.: Hybrid meta-heuristic algorithms for solving network design problem, Eur J oper res 182, No. 2, 578-596 (2007) · Zbl 1121.90024 · doi:10.1016/j.ejor.2006.07.038
[22] Ukkusuri, S. V.; Mathew, T. V.; Waller, S. T.: Robust transportation network design under demand uncertainty, Comput-aided civ infrastruct eng 22, No. 1, 6-18 (2007)
[23] Wu, J. J.; Sun, H. J.; Gao, Z. Y.; Zhang, H. Z.: Reversible Lane-based traffic network optimization with an advanced traveller information system, Eng optim 41, No. 1, 87-97 (2009)
[24] Cantarella, G. E.; Pavone, G.; Vitetta, A.: Heuristics for urban road network design: Lane layout and signal settings, Eur J oper res 175, No. 3, 1682-1695 (2006) · Zbl 1142.90345 · doi:10.1016/j.ejor.2005.02.034
[25] Cantarella, G. E.; Vitetta, A.: The multi-criteria road network design problem in an urban area, Transportation 33, No. 6, 567-588 (2006)
[26] Zhang, H.; Gao, Z.: Bilevel programming model and solution method for mixed transportation network design problem, J syst sci complex 22, No. 3, 446-459 (2009) · Zbl 1193.49041 · doi:10.1007/s11424-009-9177-3
[27] Gallo, M.; D’acierno, L.; Montella, B.: A meta-heuristic approach for solving the urban network design problem, Eur J oper res 201, No. 1, 144-157 (2010) · Zbl 1177.90052 · doi:10.1016/j.ejor.2009.02.026
[28] Webster FV, Cobbe BM. Traffic signal. Road Research Technical Paper No. 56, HMSO, London, UK; 1966.
[29] Allsop, R. E.: Estimating the traffic capacity of a signalized road junction, Transport res 6, No. 3, 245-255 (1972)
[30] Wong, S. C.: On the reserve capacities of priority junctions and roundabouts, Transport res part B 30, No. 6, 441-453 (1996)
[31] Wong, S. C.; Yang, H.: Reserve capacity of a signal-controlled road network, Transport res part B 31, No. 5, 397-402 (1997)
[32] Yang, H.; Bell, M. G. H.: A capacity paradox in network design and how to avoid it, Transport res part A 32, No. 7, 539-545 (1998)
[33] Yang, H.; Wang, J. Y. T.: Travel time minimization versus reserve capacity maximization in the network design problem, Transport res rec 1783, 17-26 (2002)
[34] Ziyou, G.; Yifan, S.: A reserve capacity model of optimal signal control with user-equilibrium route choice, Transport res part B 36, No. 4, 313-323 (2002)
[35] Chen, A.; Yang, H.; Hong, K. L.; Wilson, H. T.: Capacity reliability of a road network: an assessment methodology and numerical results, Transport res part B 36, No. 3, 225-252 (2002)
[36] Ceylan, H.; Bell, M. G. H.: Reserve capacity for a road network under optimized fixed time traffic signal control, Intell transport syst 8, No. 2, 87-99 (2004) · Zbl 1062.90505 · doi:10.1080/15472450490437780
[37] Roberts, F. S.; Xu, Y.: On the optimal strongly connected orientations of city street graphs I: Large grids, SIAM J discrete math 1, No. 2, 199-222 (1988) · Zbl 0658.05033 · doi:10.1137/0401022
[38] Roberts, F. S.; Xu, Y.: On the optimal strongly connected orientations of city street graphs: II. Two east – west avenues or north – south streets, Networks 19, No. 2, 221-233 (1989) · Zbl 0708.05026 · doi:10.1002/net.3230190204
[39] Roberts, F. S.; Xu, Y.: On the optimal strongly connected orientations of city street graphs: III. Three east – west avenues or north – south streets, Networks 22, No. 2, 109-143 (1992) · Zbl 0757.05057 · doi:10.1002/net.3230220202
[40] Roberts, F. S.; Xu, Y.: On the optimal strongly connected orientations of city street graphs IV: Four east – west avenues or north – south streets, Discrete appl math 49, No. 1 – 3, 331-356 (1994) · Zbl 0795.05068 · doi:10.1016/0166-218X(94)90217-8
[41] Lee, C. K.; Yang, K. I.: Network design of one-way streets with simulated annealing, Pap reg sci 73, No. 2, 119-134 (1994)
[42] Drezner, Z.; Wesolowsky, G. O.: Selecting an optimum configuration of one-way and two-way routes, Transport sci 31, No. 4, 386-394 (1997) · Zbl 0919.90056 · doi:10.1287/trsc.31.4.386
[43] Drezner, Z.; Salhi, S.: Selecting a good configuration of one-way and two-way routes using tabu search, Control cybern 29, No. 3, 725-740 (2000) · Zbl 0983.90004
[44] Drezner, Z.; Salhi, S.: Using hybrid metaheuristics for the one-way and two-way network design problem, Nav res log 49, No. 5, 449-463 (2002) · Zbl 1013.90013 · doi:10.1002/nav.10026
[45] Drezner, Z.; Wesolowsky, G. O.: Network design: selection and design of links and facility location, Transport res part A 37, No. 3, 241-256 (2003)
[46] Miandoabchi, E.; Farahani, R. Z.; Szeto, W. Y.: Bi-objective bimodal urban road network design using hybrid metaheuristics, Central eur J oper res, 1-39 (2011) · Zbl 1339.90062
[47] Miandoabchi E, Farahani RZ, Dullaert W, Szeto WY. Hybrid evolutionary metaheuristics for concurrent multi-objective design of urban road and public transit networks. Networks Spatial Econ 2011. doi:10.1007/s11067-011-9163-x. · Zbl 1332.90051
[48] Sheffi, Y.: Urban transportation networks: equilibrium analysis with mathematical programming methods, (1985)
[49] Ben-Ayed, O.; Boyce, D. E.; Blair, C. E.: A general bilevel linear programming formulation of the network design problem, Transport res part B 22, No. 4, 311-318 (1988)
[50] Holland, J. H.: Adaptation in natural and artificial systems, (1975) · Zbl 0317.68006
[51] Tobin, R. L.; Friesz, T. L.: Sensitivity analysis for equilibrium network flow, Transport sci 22, No. 4, 242-250 (1988) · Zbl 0665.90031 · doi:10.1287/trsc.22.4.242
[52] Kirkpatrick, S.; Jr., C. D. Gelatt; Vecchi, M. P.: Optimization by simulated annealing, Science 220, No. 4598, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[53] 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, Eur J oper res 65, No. 1, 44-57 (1993) · Zbl 0772.90043 · doi:10.1016/0377-2217(93)90143-B
[54] Aydin, M. E.; Fogarty, T. C.: A distributed evolutionary simulated annealing algorithm for combinatorial optimisation problems, J heuristics 10, No. 3, 269-292 (2004)
[55] Harker PT, Freisz TL. Bounding the solution of the continuous equilibrium network design problem. in: Proceedings of the 9th international symposium on transportation and traffic theory. VNU Science Press; 1984. p. 233 – 52.
[56] Nguyen, S.; Dupuis, C.: An efficient method for computing traffic equilibria in networks with asymmetric transportation costs, Transport sci 18, No. 2, 185-202 (1984)
[57] Leblanc, L. J.; Morlok, E. K.; Pierskalla, W. P.: An efficient approach to solving the road network equilibrium traffic assignment problem, Transport res 9, 309-318 (1975)
[58] Nagurney, A.: Comparative tests of multimodal traffic equilibrium methods, Transport res part B 18, No. 6, 469-485 (1984)
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.