An online optimization approach to post-disaster road restoration

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.