Multi-vehicle arc routing problems to restore post-disaster network connectivity

After a natural disaster roads can be damaged or blocked by debris, while bridges and viaducts may collapse. This commonly observed hazard causes some road sections to be closed and may even disconnect the road network. In the immediate disaster response phase work teams are dispatched to open a subset of roads to reconnect the network. Closed roads are traversable only after they are unblocked/cleared by one of the teams. The main objective is to provide an efficient solution method to generate a synchronized work schedule for the road clearing teams so that none of the closed roads are traversed unless their unblocking/clearing procedure is finished. We address two arc routing problems that find the route of multiple work-troops dispatched to clear blocked roads and achieve connectivity. In the first problem, we minimize the time to reconnect the network entirely. In the second problem, we maximize the total prize gained by reconnecting disconnected network components within a specified time limit. For each problem, we develop an exact Mixed Integer Programming (MIP) formulation. Furthermore, for the first problem, we propose a matheuristic that is based on an MIP-relaxation and a local search algorithm. We prove that the optimality gap of the relaxation solution is bounded by K times the lower bound obtained from the relaxed model, where K is the number of teams. For the second problem, we develop a matheuristic method. The matheuristic solves single vehicle problems sequentially with updated prizes. To obtain an upperbound, we first relax the timing elements in the exact formulation and then solve its relaxed MIP, which decomposes into single vehicle problems by Lagrangian Relaxation. We show the effectiveness of the proposed methods computationally on both random Euclidean and three distinct Istanbul road network data generated with respect to predicted earthquake scenarios.