IDEAS home Printed from https://ideas.repec.org/a/eee/reensy/v209y2021ics0951832021000260.html
   My bibliography  Save this article

A computationally efficient metric for identification of critical links in large transportation networks

Author

Listed:
  • Almotahari, Amirmasoud
  • Yazici, Anil

Abstract

Maintaining safety and resilience in transportation system requires identification of critical components. The existing transportation link criticality metrics typically require multiple traffic assignments to perform a full scan of the network. Link removals create computational burden and can cause network disconnectivity which makes it problematic to run traffic assignment. The authors previously introduced Link Criticality Index (LCI) that identifies the criticality ranking within a single User Equilibrium (UE) traffic assignment using Frank-Wolfe (FW) algorithm. While LCI is shown to provide balanced rankings with respect to connectivity and flow conditions, its computational efficiency diminishes for larger networks due to the need for path enumeration. This paper formulates an adjusted LCI to make it computationally efficient for larger networks. Adjusted LCI utilizes 1) viable routes instead of the complete list of enumerated paths; and, 2) a path-based traffic assignment algorithm (Gradient Projection) to replace FW. The consistency of rankings between original/adjusted LCIs, and other measures from the literature are analyzed and compared for three networks, and through an experimental setup. The proposed method is also applied on a large-scale transportation network, i.e., Chicago network. The results show that both modifications are effective and yield faster results without compromising LCI's advantages.

Suggested Citation

  • Almotahari, Amirmasoud & Yazici, Anil, 2021. "A computationally efficient metric for identification of critical links in large transportation networks," Reliability Engineering and System Safety, Elsevier, vol. 209(C).
    • Handle: RePEc:eee:reensy:v:209:y:2021:i:c:s0951832021000260
    DOI: 10.1016/j.ress.2021.107458
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0951832021000260
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ress.2021.107458?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Meisam Akbarzadeh & Soroush Memarmontazerin & Sybil Derrible & Sayed Farzin Salehi Reihani, 2019. "Correction to: The role of travel demand and network centrality on the connectivity and resilience of an urban street system," Transportation, Springer, vol. 46(5), pages 1969-1969, October.
    2. Jayakrishnan, R. & Tsai, Wei T. & Prashker, Joseph N. & Rajadhyaksha, Subodh, 1994. "A Faster Path-Based Algorithm for Traffic Assignment," University of California Transportation Center, Working Papers qt2hf4541x, University of California Transportation Center.
    3. Almotahari, Amirmasoud & Yazici, M. Anil, 2019. "A link criticality index embedded in the convex combinations solution of user equilibrium traffic assignment," Transportation Research Part A: Policy and Practice, Elsevier, vol. 126(C), pages 67-82.
    4. Bramka Arga Jafino & Jan Kwakkel & Alexander Verbraeck, 2020. "Transport network criticality metrics: a comparative analysis and a guideline for selection," Transport Reviews, Taylor & Francis Journals, vol. 40(2), pages 241-264, March.
    5. Cats, Oded & Jenelius, Erik, 2015. "Planning for the unexpected: The value of reserve capacity for public transport network robustness," Transportation Research Part A: Policy and Practice, Elsevier, vol. 81(C), pages 47-61.
    6. Akbarzadeh, Meisam & Salehi Reihani, Sayed Farzin & Samani, Keivan Aghababaei, 2019. "Detecting critical links of urban networks using cluster detection methods," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 515(C), pages 288-298.
    7. Berdica, Katja, 2002. "An introduction to road vulnerability: what has been done, is done and should be done," Transport Policy, Elsevier, vol. 9(2), pages 117-127, April.
    8. Oded Cats & Erik Jenelius, 2014. "Dynamic Vulnerability Analysis of Public Transport Networks: Mitigation Effects of Real-Time Information," Networks and Spatial Economics, Springer, vol. 14(3), pages 435-463, December.
    9. Voltes-Dorta, Augusto & Rodríguez-Déniz, Héctor & Suau-Sanchez, Pere, 2017. "Vulnerability of the European air transport network to major airport closures from the perspective of passenger delays: Ranking the most critical airports," Transportation Research Part A: Policy and Practice, Elsevier, vol. 96(C), pages 119-145.
    10. Cats, Oded & Koppenol, Gert-Jaap & Warnier, Martijn, 2017. "Robustness assessment of link capacity reduction for complex networks: Application for public transport systems," Reliability Engineering and System Safety, Elsevier, vol. 167(C), pages 544-553.
    11. Oliveira, Eduardo Leal de & Portugal, Licínio da Silva & Porto Junior, Walter, 2016. "Indicators of reliability and vulnerability: Similarities and differences in ranking links of a complex road system," Transportation Research Part A: Policy and Practice, Elsevier, vol. 88(C), pages 195-208.
    12. Alireza Ermagun & David M Levinson, 2019. "Development and application of the network weight matrix to predict traffic flow for congested and uncongested conditions," Environment and Planning B, , vol. 46(9), pages 1684-1705, November.
    13. Chen, Bi Yu & Lam, William H.K. & Sumalee, Agachai & Li, Qingquan & Li, Zhi-Chun, 2012. "Vulnerability analysis for large-scale and congested road networks with demand uncertainty," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(3), pages 501-516.
    14. Xu, Hongli & Lou, Yingyan & Yin, Yafeng & Zhou, Jing, 2011. "A prospect-based user equilibrium model with endogenous reference points and its application in congestion pricing," Transportation Research Part B: Methodological, Elsevier, vol. 45(2), pages 311-328, February.
    15. Reggiani, Aura & Nijkamp, Peter & Lanzi, Diego, 2015. "Transport resilience and vulnerability: The role of connectivity," Transportation Research Part A: Policy and Practice, Elsevier, vol. 81(C), pages 4-15.
    16. Jenelius, Erik & Petersen, Tom & Mattsson, Lars-Göran, 2006. "Importance and exposure in road network vulnerability analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 40(7), pages 537-560, August.
    17. Taylor, Michael A.P. & Susilawati,, 2012. "Remoteness and accessibility in the vulnerability analysis of regional road networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 761-771.
    18. Cats, O. & Yap, M. & van Oort, N., 2016. "Exposing the role of exposure: Public transport network risk analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 88(C), pages 1-14.
    19. Sang Nguyen & Clermont Dupuis, 1984. "An Efficient Method for Computing Traffic Equilibria in Networks with Asymmetric Transportation Costs," Transportation Science, INFORMS, vol. 18(2), pages 185-202, May.
    20. Karen E Joyce & Paul J Laurienti & Jonathan H Burdette & Satoru Hayasaka, 2010. "A New Measure of Centrality for Brain Networks," PLOS ONE, Public Library of Science, vol. 5(8), pages 1-13, August.
    21. Demirel, Hande & Kompil, Mert & Nemry, Françoise, 2015. "A framework to analyze the vulnerability of European road networks due to Sea-Level Rise (SLR) and sea storm surges," Transportation Research Part A: Policy and Practice, Elsevier, vol. 81(C), pages 62-76.
    22. Watling, David & Balijepalli, N.C., 2012. "A method to assess demand growth vulnerability of travel times on road network links," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 772-789.
    23. Meisam Akbarzadeh & Soroush Memarmontazerin & Sybil Derrible & Sayed Farzin Salehi Reihani, 2019. "The role of travel demand and network centrality on the connectivity and resilience of an urban street system," Transportation, Springer, vol. 46(4), pages 1127-1141, August.
    24. Sullivan, J.L. & Novak, D.C. & Aultman-Hall, L. & Scott, D.M., 2010. "Identifying critical road segments and measuring system-wide robustness in transportation networks with isolating links: A link-based capacity-reduction approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 44(5), pages 323-336, June.
    25. Anthony Chen & Chao Yang & Sirisak Kongsomsaksakul & Ming Lee, 2007. "Network-based Accessibility Measures for Vulnerability Analysis of Degradable Transportation Networks," Networks and Spatial Economics, Springer, vol. 7(3), pages 241-256, September.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fan, Bing & Tan, Hongtao & Li, Yaqun, 2023. "Critical link identification algorithm for power communication networks in SDN architecture," International Journal of Critical Infrastructure Protection, Elsevier, vol. 40(C).
    2. Hao, Yucheng & Jia, Limin & Zio, Enrico & Wang, Yanhui & He, Zhichao, 2023. "A multi-objective optimization model for identifying groups of critical elements in a high-speed train," Reliability Engineering and System Safety, Elsevier, vol. 235(C).
    3. Lee, Juseong & Mitici, Mihaela, 2022. "Multi-objective design of aircraft maintenance using Gaussian process learning and adaptive sampling," Reliability Engineering and System Safety, Elsevier, vol. 218(PA).
    4. Navin Bhatta & Shakhawat H. Tanim & Pamela Murray-Tuite, 2024. "Dynamics of Link Importance through Normal Conditions, Flood Response, and Recovery," Sustainability, MDPI, vol. 16(2), pages 1-35, January.
    5. Monfared, M.A.S. & Rezazadeh, Masoumeh & Alipour, Zohreh, 2022. "Road networks reliability estimations and optimizations: A Bi-directional bottom-up, top-down approach," Reliability Engineering and System Safety, Elsevier, vol. 222(C).
    6. Boakye, Jessica & Guidotti, Roberto & Gardoni, Paolo & Murphy, Colleen, 2022. "The role of transportation infrastructure on the impact of natural hazards on communities," Reliability Engineering and System Safety, Elsevier, vol. 219(C).
    7. Yu, Yun-Chi & Gardoni, Paolo, 2022. "Predicting road blockage due to building damage following earthquakes," Reliability Engineering and System Safety, Elsevier, vol. 219(C).
    8. Bucar, Raif C.B. & Hayeri, Yeganeh M., 2022. "Quantitative flood risk evaluation to improve drivers’ route choice decisions during disruptive precipitation," Reliability Engineering and System Safety, Elsevier, vol. 219(C).
    9. Wandelt, Sebastian & Lin, Wei & Sun, Xiaoqian & Zanin, Massimiliano, 2022. "From random failures to targeted attacks in network dismantling," Reliability Engineering and System Safety, Elsevier, vol. 218(PA).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Almotahari, Amirmasoud & Yazici, M. Anil, 2019. "A link criticality index embedded in the convex combinations solution of user equilibrium traffic assignment," Transportation Research Part A: Policy and Practice, Elsevier, vol. 126(C), pages 67-82.
    2. Li, Tao & Rong, Lili & Yan, Kesheng, 2019. "Vulnerability analysis and critical area identification of public transport system: A case of high-speed rail and air transport coupling system in China," Transportation Research Part A: Policy and Practice, Elsevier, vol. 127(C), pages 55-70.
    3. Caterina Malandri & Luca Mantecchini & Filippo Paganelli & Maria Nadia Postorino, 2021. "Public Transport Network Vulnerability and Delay Distribution among Travelers," Sustainability, MDPI, vol. 13(16), pages 1-14, August.
    4. Lu, Qing-Chang, 2018. "Modeling network resilience of rail transit under operational incidents," Transportation Research Part A: Policy and Practice, Elsevier, vol. 117(C), pages 227-237.
    5. Pan, Shouzheng & Yan, Hai & He, Jia & He, Zhengbing, 2021. "Vulnerability and resilience of transportation systems: A recent literature review," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 581(C).
    6. Qing-Chang Lu & Shan Lin, 2019. "Vulnerability Analysis of Urban Rail Transit Network within Multi-Modal Public Transport Networks," Sustainability, MDPI, vol. 11(7), pages 1-14, April.
    7. Jiangang Shi & Shiping Wen & Xianbo Zhao & Guangdong Wu, 2019. "Sustainable Development of Urban Rail Transit Networks: A Vulnerability Perspective," Sustainability, MDPI, vol. 11(5), pages 1-24, March.
    8. Gu, Yu & Fu, Xiao & Liu, Zhiyuan & Xu, Xiangdong & Chen, Anthony, 2020. "Performance of transportation network under perturbations: Reliability, vulnerability, and resilience," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 133(C).
    9. Mohamad Darayi & Kash Barker & Joost R. Santos, 2017. "Component Importance Measures for Multi-Industry Vulnerability of a Freight Transportation Network," Networks and Spatial Economics, Springer, vol. 17(4), pages 1111-1136, December.
    10. Rodríguez-Núñez, Eduardo & García-Palomares, Juan Carlos, 2014. "Measuring the vulnerability of public transport networks," Journal of Transport Geography, Elsevier, vol. 35(C), pages 50-63.
    11. Victor Cantillo & Luis F. Macea & Miguel Jaller, 2019. "Assessing Vulnerability of Transportation Networks for Disaster Response Operations," Networks and Spatial Economics, Springer, vol. 19(1), pages 243-273, March.
    12. Kashin Sugishita & Yasuo Asakura, 2021. "Vulnerability studies in the fields of transportation and complex networks: a citation network analysis," Public Transport, Springer, vol. 13(1), pages 1-34, March.
    13. Khademi, Navid & Babaei, Mohsen & Schmöcker, Jan-Dirk & Fani, Amirhossein, 2018. "Analysis of incident costs in a vulnerable sparse rail network – Description and Iran case study," Research in Transportation Economics, Elsevier, vol. 70(C), pages 9-27.
    14. Jafino, Bramka Arga, 2021. "An equity-based transport network criticality analysis," Transportation Research Part A: Policy and Practice, Elsevier, vol. 144(C), pages 204-221.
    15. Richard Connors & David Watling, 2015. "Assessing the Demand Vulnerability of Equilibrium Traffic Networks via Network Aggregation," Networks and Spatial Economics, Springer, vol. 15(2), pages 367-395, June.
    16. Xu, Xiangdong & Qu, Kai & Chen, Anthony & Yang, Chao, 2021. "A new day-to-day dynamic network vulnerability analysis approach with Weibit-based route adjustment process," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 153(C).
    17. Bell, Michael G.H. & Kurauchi, Fumitaka & Perera, Supun & Wong, Walter, 2017. "Investigating transport network vulnerability by capacity weighted spectral analysis," Transportation Research Part B: Methodological, Elsevier, vol. 99(C), pages 251-266.
    18. Li, Tao & Rong, Lili, 2021. "Impacts of service feature on vulnerability analysis of high-speed rail network," Transport Policy, Elsevier, vol. 110(C), pages 238-253.
    19. Gonçalves, L.A.P.J. & Ribeiro, P.J.G., 2020. "Resilience of urban transportation systems. Concept, characteristics, and methods," Journal of Transport Geography, Elsevier, vol. 85(C).
    20. M. D. Yap & N. Oort & R. Nes & B. Arem, 2018. "Identification and quantification of link vulnerability in multi-level public transport networks: a passenger perspective," Transportation, Springer, vol. 45(4), pages 1161-1180, July.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:reensy:v:209:y:2021:i:c:s0951832021000260. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: https://www.journals.elsevier.com/reliability-engineering-and-system-safety .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.