Online optimization of first-responder routes in disaster response logistics

Abstract

After a disaster, first responders should reach critical locations in the disaster-affected region in the shortest time. However, road network edges can be damaged or blocked by debris. Since response time is crucial, relief operations may start before knowing which edges are blocked. A blocked edge is revealed online when it is visited at one o f its end-nodes. Multiple first-responder teams, who can communicate the blockage information, gather initially at an origin node and are assigned to target destinations (nodes) in the disaster-affected area. We consider multiple teams assigned to one destination. The objective is to find an online travel plan such that at least one of the teams finds a route from the origin to the destination in minimum time. This problem is known as the online multi-agent Canadian traveler problem. We develop an effective online heuristic policy and test it on real city road networks as well as randomly generated networks leading to instances with multiple blockages. We compare the performance of the online strategy with the offline optimum and obtain an average competitive ratio of 1.164 over 70,100 instances with varying parameter values.