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 a depot to demand nodes that become accessible only after the damaged nodes in these paths are repaired. The objective is to minimize the total 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 exact, heuristic and hybrid approaches for the CSRP. Specifically, we introduce (i) a branch-and-Benders-cut (BBC) method that enhances a previous approach by using a different variable partitioning scheme and new valid inequalities that strengthen the linear relaxation of the master problem; (ii) genetic algorithm and simulated annealing metaheuristics; and (iii) an exact hybrid BBC (HBBC) method that effectively combines the first two approaches. Computational experiments using benchmark instances show the benefits of the proposed enhancements for the BBC method and indicate that its performance is improved significantly by the use of metaheuristics within the hybridization scheme. The HBBC method obtained feasible solutions for the 390 tested instances, solving 30 of them to proven optimality for the first time. On average, it improved the best known lower and upper bounds by 15.21% and 8.41%, respectively, and reduced the computational times by more than 70% with respect to the standalone BBC.
Citation
Moreno, A.; Munari, P.; Alem, D. Decomposition-based algorithms for the crew scheduling and routing problem in road restoration. Computers & Operations Research, v. 119, 104935, 2020. [http://dx.doi.org/10.1016/j.cor.2020.104935]
Article
View Decomposition-based algorithms for the crew scheduling and routing problem in road restoration