Reliable Urban Transportation Network Design Problem Considering Recurrent Traffic Congestions

Document Type : Research Paper


1 Department of Civil Engineering University of Memphis Memphis, Tennessee, USA

2 Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran.

3 Department of Civil Engineering, University of Calgary, Calgary, Alberta, Canada.


Traffic congestion is one of the main reasons for the unsustainability of an urban transportation network. Changes in travel demand and streets’ capacity lead to traffic congestion in urban transportation networks, which is known as recurrent traffic congestion. This study aims to assess the performance reliability of urban transportation networks subject to recurrent traffic congestion conditions in order to help travelers to find alternative non-congested routes. A non-congested route is a route without any congested link. The network reliability is defined and modeled as two different scenarios; users’ unawareness of the network’s traffic congestion and users’ ongoing awareness of the network’s traffic congestion. In addition, a reliable network design model is provided to optimize the reliability of the network taking into account street widening policy and budget constraints. Lastly, a Quantum-Inspired Evolutionary Meta-Heuristic Algorithm is adopted; while maintaining accuracy, to reduce problem-solving time and providing the possibility of solving large-scale problems for real networks. To show the applicability of the proposed models and algorithm, they have been implemented on the Sioux Falls transportation network. The results indicate users’ awareness of traffic congestion in the network increases its reliability, and centrally located links are the first candidates for street widening.


  • [1] Khayamim, R., et al., A sustainable approach for selecting and timing the urban transportation infrastructure projects in large-scale networks: A case study of Isfahan, Iran. Sustainable Cities and Society, 2020. 53: p. 101981.
  • [2] Mahmoudi, R., et al., Determining the relative importance of sustainability evaluation criteria of urban transportation network. Sustainable Cities and Society, 2019. 47: p. 101493.
  • [3] Mahmoudi, R.S., Nader; Hejazi, Reza; Emrouznejad, Ali; Rajabi, Parisa;, A hybrid egalitarian bargaining game-DEA and sustainable network design approach for evaluating, selecting and scheduling urban road construction projects. Transportation Research Part E: Logistics and Transportation Review, 2019. 130: p. 161-183.
  • [4] Hojjati-Emami, K., B. Dhillon, and K. Jenab, Reliability prediction for the vehicles equipped with advanced driver assistance systems (ADAS) and passive safety systems (PSS). International Journal of Industrial Engineering Computations, 2012. 3(5): p. 731-742.
  • [5] Du, Z.-P. and A. Nicholson, Degradable transportation systems: sensitivity and reliability analysis. Transportation Research Part B: Methodological, 1997. 31(3): p. 225-237.
  • [6] Naresky, J.J., Reliability definitions. IEEE Transactions on Reliability, 1970. 19(4): p. 198-200.
  • [7] Sumalee, A., D.P. Watling, and S. Nakayama, Reliable network design problem: case with uncertain demand and total travel time reliability. Transportation Research Record, 2006. 1964(1): p. 81-90.
  • [8] Chen, A., et al., Transport network design problem under uncertainty: a review and new developments. Transport Reviews, 2011. 31(6): p. 743-768.
  • [9] Wardrop, J.G. and J. Whitehead, some theoretical aspects of road traffic research. Proceedings of the Institution of Civil Engineers, 1952. 1(5): p. 767-768.
  • [10] Herman, R. and T. Lam, Trip time characteristics of journeys to and from work. Transportation and traffic theory, 1974. 6: p. 57-86.
  • [11] Richardson, A. and M. Taylor, Travel time variability on commuter journeys. High Speed Ground Transportation Journal, 1978. 12(1).
  • [12] Polus, A., A study of travel time and reliability on arterial routes. Transportation, 1979. 8(2): p. 141-151.
  • [13] Al-Deek, H. and E.B. Emam, New methodology for estimating reliability in transportation networks with degraded link capacities. Journal of intelligent transportation systems, 2006. 10(3): p. 117-129.
  • [14] Van Lint, J., H.J. Van Zuylen, and H. Tu, Travel time unreliability on freeways: Why measures based on variance tell only half the story. Transportation Research Part A: Policy and Practice, 2008. 42(1): p. 258-277.
  • [15] Pu, W., Analytic relationships between travel time reliability measures. Transportation Research Record: Journal of the Transportation Research Board, 2011(2254): p. 122-130.
  • [16] Institute, T.T., Providing a Highway System with Reliable Travel Times. F-SHRP Web Document 3. Transportation Research Board of the National Academies, Washington, D. C., 2003.
  • [17] Clark, S. and D. Watling, Modelling network travel time reliability under stochastic demand. Transportation Research Part B: Methodological, 2005. 39(2): p. 119-140.
  • [18] Dui, H., et al., Model and simulation analysis for the reliability of the transportation network. Journal of Simulation, 2020: p. 1-10.
  • [19] Liu, J., et al., Connectivity Reliability on an Urban Rail Transit Network from the Perspective of Passenger Travel. Urban Rail Transit, 2020. 6(1): p. 1-14.
  • [20] Wakabayashi, H. and Y. Iida, Improvement of road network reliability with traffic management. IFAC Proceedings Volumes, 1994. 27(12): p. 603-608.
  • [21] Lee, S., B. Moon, and Y. Asakura, Reliability analysis and calculation on large scale transport networks. Reliability of transport networks. Research Studies Press Ltd, 2000.
  • [22] Chen, A., P. Kasikitwiwat, and C. Yang, Alternate capacity reliability measures for transportation networks. Journal of Advanced Transportation, 2013. 47(1): p. 79-104.
  • [23] Chiou, J.-M., H.-T. Liou, and W.-H. Chen, Modeling Time-Varying Variability and Reliability of Freeway Travel Time Using Functional Principal Component Analysis. IEEE Transactions on Intelligent Transportation Systems, 2019.
  • [24] Zhang, Z., et al., Analyzing travel time reliability and its influential factors of emergency vehicles with generalized extreme value theory. Journal of Intelligent Transportation Systems, 2019. 23(1): p. 1-11.
  • [25] Lu, C., et al., Incorporating the standstill distance and time headway distributions into freeway car-following models and an application to estimating freeway travel time reliability. Journal of Intelligent Transportation Systems, 2019: p. 1-20.
  • [26] Knoop, V.L., et al., Link-level vulnerability indicators for real-world networks. Transportation Research Part A: Policy and Practice, 2012. 46(5): p. 843-854.
  • [27] El-Rashidy, R.A. and S.M. Grant-Muller, An assessment method for highway network vulnerability. Journal of Transport Geography, 2014. 34: p. 34-43.
  • [28] Wang, D.Z., et al., Identification of critical combination of vulnerable links in transportation networks–a global optimisation approach. Transportmetrica A: Transport Science, 2016. 12(4): p. 346-365.
  • [29] Bagloee, S.A., et al., Identifying critical disruption scenarios and a global robustness index tailored to real life road networks. Transportation Research Part E: Logistics and Transportation Review, 2017. 98: p. 60-81.
  • [30] Vodák, R., et al., A deterministic approach for rapid identification of the critical links in networks. PloS one, 2019. 14(7).
  • [31] Gecchele, G., R. Ceccato, and M. Gastaldi, Road Network Vulnerability Analysis: Case Study Considering Travel Demand and Accessibility Changes. Journal of Transportation Engineering, Part A: Systems, 2019. 145(7): p. 05019004.
  • [32] Cantillo, V., L.F. Macea, and M. Jaller, Assessing vulnerability of transportation networks for disaster response operations. Networks and Spatial Economics, 2019. 19(1): p. 243-273.
  • [33] Tian, Z., et al., Key links identification for urban road traffic network based on temporal-spatial distribution of traffic congestion. Modern Physics Letters B, 2019. 33(25): p. 1950307.
  • [34] Guo, S., et al., Identifying the most influential roads based on traffic correlation networks. EPJ Data Science, 2019. 8(1): p. 1-17.
  • [35] Poorzahedy, H. and S.N.S. Bushehri, Network performance improvement under stochastic events with long-term effects. Transportation, 2005. 32(1): p. 65-85.
  • [36] Chen, H. and H.A. Rakha, Real-time travel time prediction using particle filtering with a non-explicit state-transition model. Transportation Research Part C: Emerging Technologies, 2014. 43: p. 112-126.
  • [37] Iida, Y. and H. Wakabayashi. An approximation method of terminal reliability of road network using partial minimal path and cut sets. in Transport policy, management & technology towards 2001: selected proceedings of the fifth world conference on transport research. 1989.
  • [38] Valiant, L.G., The complexity of enumeration and reliability problems. SIAM Journal on Computing, 1979. 8(3): p. 410-421.
  • [39] Shier, D.R., Network reliability and algebraic structures. 1991: Clarendon Press.
  • [40] Konak, A. and A. Smith. A general upperbound for all-terminal network reliability and its uses. in Proceedings of the Industrial Engineering Research Conference. 1998.
  • [41] Sharafat, A.R. and O.R. Ma'rouzi, All-terminal network reliability using recursive truncation algorithm. IEEE Transactions on Reliability, 2009. 58(2): p. 338-347.
  • [42] Satyanarayana, A., A unified formula for analysis of some network reliability problems. IEEE Transactions on Reliability, 1982. 31(1): p. 23-32.
  • [43] Fishman, G.S., A Monte Carlo sampling plan for estimating network reliability. Operations Research, 1986. 34(4): p. 581-594.
  • [44] Karp, R.M. and M. Luby. Monte-Carlo algorithms for enumeration and reliability problems. in Foundations of Computer Science, 1983., 24th Annual Symposium on. 1983. IEEE.
  • [45] Everitt, B. and A. Skrondal, The Cambridge dictionary of statistics. Vol. 106. 2002: Cambridge University Press Cambridge.
  • [46] Farahani, R.Z., et al., A review of urban transportation network design problems. European Journal of Operational Research, 2013. 229(2): p. 281-302.
  • [47] Bryden, K.M., et al., Optimization of heat transfer utilizing graph based evolutionary algorithms. International Journal of Heat and Fluid Flow, 2003. 24(2): p. 267-277.
  • [48] Beheshti, A. and S. Hejazi, A Quantum evolutionary algorithm for the vehicle routing problem with delivery time cost. International Journal of Industrial Engineering and Production Research, 2014. 25(4): p. 287-295.
  • [49] Mani, N. and A. Mani, Solving Combinatorial Optimization problems with Quantum inspired Evolutionary Algorithm Tuned using a Novel Heuristic Method. arXiv preprint arXiv:1612.08109, 2016.
  • [50] Narayanan, A. and M. Moore. Quantum-inspired genetic algorithms. in Evolutionary Computation, 1996., Proceedings of IEEE International Conference on. 1996. IEEE.
  • [51] Han, K.-H. and J.-H. Kim. Genetic quantum algorithm and its application to combinatorial optimization problem. in Evolutionary Computation, 2000. Proceedings of the 2000 Congress on. 2000. IEEE.
  • [52] Han, K.-H. and J.-H. Kim, Quantum-inspired evolutionary algorithm for a class of combinatorial optimization. IEEE transactions on evolutionary computation, 2002. 6(6): p. 580-593.
  • [53] Zhang, G., Quantum-inspired evolutionary algorithms: a survey and empirical study. Journal of Heuristics, 2011. 17(3): p. 303-351.
  • [54] Kourank Beheshti, A. and S.R. Hejazi, A Quantum Evolutionary Algorithm for the Vehicle Routing Problem with Single-sided Time Window Setting. International Journal of Industrial Engineering & Production Research, 2014. 25(4): p. 287-295.