Skip to main content

Research Repository

Advanced Search

An online optimization approach for post-disaster relief distribution with online blocked edges

Akbari, Vahid; Shiri, Davood


Davood Shiri


Disasters can disrupt road networks by blocking some of the roads and consequently impeding accessibility to critical locations. In the immediate post-disaster response phase, while the blockage information is yet to be collected, relief distribution crews (RDCs) should dispatch from warehouses to supply critical locations with first aid items. The RDCs are not capable of unblocking damaged roads and should find a way to bypass them once such edges are observed in their routes. With the objective of minimizing total latency of the critical nodes, we study the problem that addresses the relief distribution operations with k non-recoverable online blocked edges. The online blocked edges are not known to the RDCs initially and the blockage of a blocked edge is revealed when one of the RDCs arrives at one of its end-nodes. Once one of the RDCs knows about a blocked edge, this information is communicated among the rest of the RDCs and they will all be informed about that blocked edge. We first investigate the worst-case performance of online algorithms against offline optimal solutions using competitive ratio. We then prove a lower bound on the competitive ratio of deterministic online algorithms. We also provide an upper bound on the competitive ratio of the optimal deterministic online algorithms by introducing a deterministic algorithm which achieves a bounded competitive ratio. We then develop three heuristic algorithms to solve this problem. One of our algorithms is based on solving an Integer Programming model to find the assignment of the nodes to the RDCs and then finding the routes dynamically. The other algorithms are not based on solving optimization models and hence are more efficient in terms of their computational time. We compare our proposed heuristic algorithms with the best known algorithms from the literature that are developed for a single RDC variation of the problem. Finally, we provide a through computational analysis of our algorithms on instances adopted from real-world road networks.


Akbari, V., & Shiri, D. (2022). An online optimization approach for post-disaster relief distribution with online blocked edges. Computers and Operations Research, 137, Article 105533.

Journal Article Type Article
Acceptance Date Aug 24, 2021
Online Publication Date Sep 5, 2021
Publication Date Jan 1, 2022
Deposit Date Sep 6, 2021
Publicly Available Date Mar 6, 2023
Journal Computers and Operations Research
Print ISSN 0305-0548
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 137
Article Number 105533
Keywords Management Science and Operations Research; Modelling and Simulation; General Computer Science
Public URL
Publisher URL


You might also like

Downloadable Citations