Crew Scheduling and Routing Problem in Road Restoration via Branch-and-Price Algorithms

This paper addresses the single crew scheduling and routing problem in the context of road network repair and restoration, which is critical in assisting complex postdisaster decisions in humanitarian logistics settings. We present three novel formulations for this problem, which are the first suitable for column generation and branch-and-price (BP) algorithms. Specifically, our first formulation is based on enumerating crew schedules and routes while explicitly defining the relief paths. The second formulation relies on enumerating the schedules, routes, and relief paths. Finally, the third formulation builds upon the second one by including additional constraints and variables related to relief path decisions. Considering each formulation, we propose BP algorithms that rely on several enhancements, including a new dynamic programming labeling algorithm to efficiently solve the subproblems. Extensive computational results based on 648 benchmark instances reveal that our BP algorithms significantly outperform existing exact approaches, solving 450 instances to optimality, and remarkably 118 instances for the first time. Our framework is also very effective in improving the lower bounds, upper bounds, and optimality gaps that have been reported in the literature. Funding: This work was supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo [Grants 15/26453-7, 16/01860-1, 16/15966-6, and 19/23596-2], the Conselho Nacional de Desenvolvimento Científico e Tecnológico [Grant 313220/2020-4], and the Coordenação de Aperfeiçoamento de Pessoal de Nível Superior. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2023.0227 .