Decomposition-based algorithms to the crew scheduling and routing problem in road restoration

The Crew Scheduling and Routing Problem (CSRP) consists of determining the best route and schedule for a single crew to repair damaged nodes in a network affected by extreme events.The problem also involves the design of paths to connect the depot to demand nodes that become accessible only after the damaged nodes in these paths are repaired. The objective is to minimize the sum of time that demand nodes remain inaccessible from the depot. The integrated scheduling and routing decisions make the problem too complicated to be effectively solved using Mixed Integer Programming (MIP) formulations. In this paper, we propose metaheuristics approaches to solve the CSRP. We also propose a Branch-and-Benders-Cuts (BBC) based on anew Benders reformulation of the problem and a hybrid BBC (HBBC) approach that combine the metaheuristics with the BBC algorithm. Additionally, we present strategies to speed up the HBBC. Computational experiments using instances from the literature indicate that hybridizing BBC methods with metaheuristics can significantly improve both the lower and upper bounds simultaneously. The HBBC found new optimal solutions and improved bounds for benchmark instances of the problem, leading to reductions in the average gap and cost of the solutions.Keywords: Hybrid method, Benders decomposition, Branch-and-cut, Decomposition-based metaheuristic, Crew scheduling and routing, Road restoration