Work crew routing problem for infrastructure network restoration

This paper introduces a synchronized routing problem for planning and scheduling restorative efforts for infrastructure networks in the aftermath of a disruptive event. In this problem, a set of restoration crews are dispatched from depots to a road network to restore the disrupted infrastructure network. Two mathematical formulations are presented to scheduling and sequencing disrupted network components to restoration crews and route the crews towards disrupted components to maximize network resilience progress in any given time horizon. In the first formulation, the number of restoration crews assigned to each disrupted component, the arrival time of each assigned crew to each disrupted component and consequently the restoration rate associated with each disrupted component are considered as variables to increase the flexibility of the model in the presence of different disruptive events. Along with the contributions applies in the first formulation, in the second formulation, each disrupted component can be partially active during its restoration process. To find the coordinated routes, we propose a relaxed mixed integer program as well as a set of valid inequalities which relates the planning and scheduling efforts to decision makers policies. The integration of the relaxed formulation and valid inequalities results in a lower bound for the original formulations. We further introduce a feasibility algorithm to derive a strong initial solution for the routing restorative capacity problem. Computational results on gas, water, and electric power infrastructure network instances from Shelby County, TN data, demonstrates both the effectiveness of the proposed model formulation, in solving small to medium scale problems, the strength of the initial solution procedure, especially for large scale problems.