Abstract Natural disasters impact transportation networks adversely and cause road sections to be damaged or blocked. The road network may even become disconnected, impeding accessibility between disaster-stricken areas and critical locations such as hospitals, relief aid depots and transportation hubs. In the immediate response phase, a set of blocked edges should be selected and restored to reconnect the transportation network. While locations of the disrupted roads can be identified using drone or satellite images, an accurate estimation of time to restore a road segment can be carried out only after expert observations on the field. In this article, we study a post-disaster road restoration problem modeled on an undirected edge-weighted graph with k blocked edges, where the unblocking time of a blocked edge is revealed online once the road restoration team visits an end-node of that blocked edge. The objective is to minimize the time at which the road network is reconnected. We first investigate the worst-case performance of online algorithms against offline optimal solutions by means of the competitive ratio. We prove that any online deterministic algorithm cannot achieve a competitive ratio better than 2 k 1 . We also provide an optimal online algorithm that is proven to achieve this lower bound. In addition, to achieve good performance on realistic instances, we implement an algorithm that solves a mixed integer programming model each time new information is revealed. Since model solution is prohibitively time-consuming, we also propose a novel polynomial time online algorithm. We compare these two algorithms with two other benchmark online algorithms on both Istanbul road network instances and several other city instances from the literature. Our experiments show that the proposed polynomial time online algorithm performs superior to the benchmark ones and obtains solutions close to the offline optimum on all the tested instances.

    Highlights An online optimization approach is proposed for post-disaster road restoration. A comprehensive theoretical worst-case competitive analysis is presented. An online algorithm that solves a mixed integer programming model is implemented. A novel polynomial time online heuristic algorithm is proposed. Extensive computational experiments are conducted on real city instances from the literature.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    An online optimization approach to post-disaster road restoration


    Beteiligte:
    Akbari, Vahid (Autor:in) / Shiri, Davood (Autor:in) / Sibel Salman, F. (Autor:in)


    Erscheinungsdatum :

    2021-05-31


    Format / Umfang :

    25 pages




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch






    Post-Disaster Reconstruction of Road Infrastructure

    Akvan Gajanayake / Tehmina Khan / Guomin Zhang | DOAJ | 2020

    Freier Zugriff

    Post-disaster recovery sequencing strategy for road networks

    Gokalp, Can / Patil, Priyadarshan N. / Boyles, Stephen D. | Elsevier | 2021