IDEAS home Printed from https://ideas.repec.org/a/plo/pone00/0164780.html
   My bibliography  Save this article

An Optimal Schedule for Urban Road Network Repair Based on the Greedy Algorithm

Author

Listed:
  • Guangquan Lu
  • Ying Xiong
  • Chuan Ding
  • Yunpeng Wang

Abstract

The schedule of urban road network recovery caused by rainstorms, snow, and other bad weather conditions, traffic incidents, and other daily events is essential. However, limited studies have been conducted to investigate this problem. We fill this research gap by proposing an optimal schedule for urban road network repair with limited repair resources based on the greedy algorithm. Critical links will be given priority in repair according to the basic concept of the greedy algorithm. In this study, the link whose restoration produces the ratio of the system-wide travel time of the current network to the worst network is the minimum. We define such a link as the critical link for the current network. We will re-evaluate the importance of damaged links after each repair process is completed. That is, the critical link ranking will be changed along with the repair process because of the interaction among links. We repair the most critical link for the specific network state based on the greedy algorithm to obtain the optimal schedule. The algorithm can still quickly obtain an optimal schedule even if the scale of the road network is large because the greedy algorithm can reduce computational complexity. We prove that the problem can obtain the optimal solution using the greedy algorithm in theory. The algorithm is also demonstrated in the Sioux Falls network. The problem discussed in this paper is highly significant in dealing with urban road network restoration.

Suggested Citation

  • Guangquan Lu & Ying Xiong & Chuan Ding & Yunpeng Wang, 2016. "An Optimal Schedule for Urban Road Network Repair Based on the Greedy Algorithm," PLOS ONE, Public Library of Science, vol. 11(10), pages 1-15, October.
  • Handle: RePEc:plo:pone00:0164780
    DOI: 10.1371/journal.pone.0164780
    as

    Download full text from publisher

    File URL: https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0164780
    Download Restriction: no

    File URL: https://journals.plos.org/plosone/article/file?id=10.1371/journal.pone.0164780&type=printable
    Download Restriction: no

    File URL: https://libkey.io/10.1371/journal.pone.0164780?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
    ---><---

    References listed on IDEAS

    as
    1. Sohn, Jungyul, 2006. "Evaluating the significance of highway network links under the flood damage: An accessibility approach," Transportation Research Part A: Policy and Practice, Elsevier, vol. 40(6), pages 491-506, July.
    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. Junlong Peng & Mengyao Wang & Chao Peng & Ke Hu, 2022. "Research on extremely short construction period of engineering project based on labor balance under resource tolerance," PLOS ONE, Public Library of Science, vol. 17(3), pages 1-18, March.

    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. Amin, Shohel & Tamima, Umma & Amador-Jiménez, Luis E., 2019. "Optimal pavement management: Resilient roads in support of emergency response of cyclone affected coastal areas," Transportation Research Part A: Policy and Practice, Elsevier, vol. 119(C), pages 45-61.
    2. Chen, Shaopei & Claramunt, Christophe & Ray, Cyril, 2014. "A spatio-temporal modelling approach for the study of the connectivity and accessibility of the Guangzhou metropolitan network," Journal of Transport Geography, Elsevier, vol. 36(C), pages 12-23.
    3. Rahimi-Golkhandan, Armin & Garvin, Michael J. & Brown, Bryan L., 2019. "Characterizing and measuring transportation infrastructure diversity through linkages with ecological stability theory," Transportation Research Part A: Policy and Practice, Elsevier, vol. 128(C), pages 114-130.
    4. Liang Jia & Saini Yang & Weiping Wang & Xinlong Zhang, 2022. "Impact analysis of highways in China under future extreme precipitation," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 110(2), pages 1097-1113, January.
    5. Jesus Gonzalez-Feliu & Aurélie Mercier, 2013. "A combined people-freight accessibility approach for urban retailing and leisure planning at strategic level," Post-Print halshs-00919537, HAL.
    6. Jenelius, Erik, 2010. "User inequity implications of road network vulnerability," The Journal of Transport and Land Use, Center for Transportation Studies, University of Minnesota, vol. 2(3), pages 57-73.
    7. Jenelius, Erik & Mattsson, Lars-Göran, 2012. "Road network vulnerability analysis of area-covering disruptions: A grid-based approach with case study," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(5), pages 746-760.
    8. Almoghathawi, Yasser & Barker, Kash & Rocco, Claudio M. & Nicholson, Charles D., 2017. "A multi-criteria decision analysis approach for importance identification and ranking of network components," Reliability Engineering and System Safety, Elsevier, vol. 158(C), pages 142-151.
    9. Akbari, Vahid & Salman, F. Sibel, 2017. "Multi-vehicle synchronized arc routing problem to restore post-disaster network connectivity," European Journal of Operational Research, Elsevier, vol. 257(2), pages 625-640.
    10. Rolf Nyberg & Magnus Johansson, 2013. "Indicators of road network vulnerability to storm-felled trees," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 69(1), pages 185-199, October.
    11. Sarlas, Georgios & Páez, Antonio & Axhausen, Kay W., 2020. "Betweenness-accessibility: Estimating impacts of accessibility on networks," Journal of Transport Geography, Elsevier, vol. 84(C).
    12. Yi‐Ping Fang & Giovanni Sansavini & Enrico Zio, 2019. "An Optimization‐Based Framework for the Identification of Vulnerabilities in Electric Power Grids Exposed to Natural Hazards," Risk Analysis, John Wiley & Sons, vol. 39(9), pages 1949-1969, September.
    13. Michal Bíl & Jan Kubeček & Richard Andrášik, 2014. "An epidemiological approach to determining the risk of road damage due to landslides," Natural Hazards: Journal of the International Society for the Prevention and Mitigation of Natural Hazards, Springer;International Society for the Prevention and Mitigation of Natural Hazards, vol. 73(3), pages 1323-1335, September.
    14. Yücel, E. & Salman, F.S. & Arsik, I., 2018. "Improving post-disaster road network accessibility by strengthening links against failures," European Journal of Operational Research, Elsevier, vol. 269(2), pages 406-422.
    15. Yu Miao & Anning Ni, 2019. "Vulnerability Analysis of Intercity Multimode Transportation Networks; A Case Study of the Yangtze River Delta," Sustainability, MDPI, vol. 11(8), pages 1-16, April.
    16. Nogal, Maria & Morales Nápoles, Oswaldo & O’Connor, Alan, 2019. "Structured expert judgement to understand the intrinsic vulnerability of traffic networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 127(C), pages 136-152.
    17. Tong, Lu & Zhou, Xuesong & Miller, Harvey J., 2015. "Transportation network design for maximizing space–time accessibility," Transportation Research Part B: Methodological, Elsevier, vol. 81(P2), pages 555-576.
    18. 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.
    19. Li, Hongchang & Strauss, Jack & Shunxiang, Hu & Lui, Lu, 2018. "Do high-speed railways lead to urban economic growth in China? A panel data study of China’s cities," The Quarterly Review of Economics and Finance, Elsevier, vol. 69(C), pages 70-89.
    20. Lindell, Michael K., 2008. "EMBLEM2: An empirically based large scale evacuation time estimate model," Transportation Research Part A: Policy and Practice, Elsevier, vol. 42(1), pages 140-154, January.

    More about this item

    Statistics

    Access and download statistics

    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:plo:pone00:0164780. 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: plosone (email available below). General contact details of provider: https://journals.plos.org/plosone/ .

    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.