The crew scheduling and routing problem in road restoration

Abstract

Extreme events as large-scale disasters can cause partial or total disruption of basic services such as water, energy, communication and transportation. In particular, recovering the transportation infrastructure is of ultimate importance in post-disaster situations, to enable the evacuation of victims and the distribution of supplies to affected areas. Road restoration, one of the main activities in this context, is a complex activity due to its inherent decisions that must be taken quickly and under uncertainty, such as the allocation of resources and the scheduling/routing of the crews that perform the restoration activities. In this thesis, we address road restoration by means of the Crew Scheduling and Routing Problem (CSRP), which integrates scheduling and routing decisions. The problem also involves the design of relief paths to connect a supply depot to demand nodes that become accessible only after the damaged nodes in these paths are repaired. We start addressing the basic variant of the CSRP, which considers a single crew available to perform the repair operations and minimizes the accessibility time of the demand nodes. Then, we extend the problem to consider multiple heterogeneous crews and uncertainties in the repair times via robust optimization. Also, we introduce the minimization of the latency of the demand nodes, where the latency of a node is defined as the accessibility time plus the travel time from the depot to that node. To solve the CSRP and the proposed extensions, effective solution methods based on Benders decomposition are proposed. We propose three types of solution approaches: branch-and-Benders-cut algorithms (BBC), metaheuristics based on simulated annealing and genetic algorithm, and hybrid branch-and-Benders-cut algorithms (HBBC). We develop two BBC algorithms. The first BBC has a master problem with scheduling decisions while the crew routing and the design of relief paths are considered in the subproblems. The second BBC considers the crew scheduling and relief path decisions in the master problem and a subproblem with the routing decisions. The metaheuristics operate on a subproblem representing the scheduling decisions and call for specialized algorithms to optimize the crew routing and the relief path decisions as well as to determine the feasibility and cost of the proposed schedule in the original CSRP. The HBBC combines the metaheuristics with the BBC algorithm. Computational experiments using instances from the literature are performed to verify the performance of the solution methods. The experiments show that the solution approaches developed so far improve the results of other exact and heuristic methods from the literature for the single crew CSRP. Computational experiments with real-world instances based on real disaster situations, such as floods and mass movements in the state of Rio de Janeiro - Brazil, are performed to validate the new proposed multicrew and robust extensions of the problem and they show that the proposed approaches are able to find good quality solutions for practical-sized instances.