An online optimization approach to post-disaster road restoration

Vahid Akbari, Davood Shiri and F. Sibel Salman

Transportation Research Part B: Methodological, 2021, vol. 150, issue C, 1-25

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 2k−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.

Keywords: Disaster response logistics; Online optimization; Road clearance; Network restoration; Competitive ratio (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0191261521001028
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:150:y:2021:i:c:p:1-25

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.trb.2021.05.017

Access Statistics for this article

Transportation Research Part B: Methodological is currently edited by Fred Mannering

More articles in Transportation Research Part B: Methodological from Elsevier
Bibliographic data for series maintained by Catherine Liu ().