As a result of a natural disaster, roads can be damaged and blocked by debris and other structures. This in turn impedes accessibility between critical locations such as hospitals, disaster response centers, shelters, airports and disaster-struck areas. We study the post-disaster road clearing problem with the aim of providing a fast and effective method to determine the route of a work troop responsible for clearing the blocked roads. The objective is to minimize the total latency, that is, the sum of the waiting times until each critical location is reached by the troop over all critical nodes. The latency of a critical node is the travel time from the origin (depot) node, where the work troop is initially positioned, to that critical node. The Total Latency Problem is to find an optimal route to determine which roads should be unblocked in what order. We develop an exact mathematical model for this NP-hard problem. However, for instances with more than seven critical nodes, the exact formulation falls short of solving the problem optimally in the 3-hour time limit. Hence, we propose an efficient heuristic method to find a near-optimal solution in short running time. We test the heuristic on Istanbul data and show that optimal or near-optimal solutions are obtained within seconds.
| Subject : | : | Abstracts |
| Topics | : | Heuristics |
| PDF version | : |  PDF version |
