After a natural disaster roads can be damaged or blocked by debris, while bridges and viaducts may collapse. This commonly observed hazard causes many road sections to be closed and may even disconnect the road network, leaving some regions isolated from relief aid. For effective emergency response, establishing accessibility throughout the disaster area carries high priority. In the immediate disaster response phase, information regarding the road conditions should be gathered and work teams should be dispatched to clear/repair the blocked roads. We will present our recent work on generating a coordinated work schedule for the road clearing teams. We define an arc routing and scheduling problem on a network to find which edges to unblock and the routes of each clearing team, so that the connectivity of the network is regained in shortest time. Since an edge can be traversed multiple times after it has been cleared, the timing of traversals by different work teams complicates the problem. We present an exact Mixed Integer Programming (MIP) formulation to solve this problem on smaller networks, and a math-heuristic to solve the problem on larger instances. The heuristic is based on an MIP-relaxation and a local search algorithm. We prove that the optimality gap of the relaxation solution is bounded by the number of teams and the math-heuristic provides solutions with the same gap in the worst case. We present computational results on Istanbul networks and randomly generated data sets and observe that the math-heuristic obtains small optimality gaps in relatively short time.
Homepage of Sibel Salman