Decomposition-based algorithms for the crew scheduling and routing problem in road restoration. (July 2020)

• Record Type: Journal Article
• Authors: Moreno, Alfredo; Munari, Pedro; Alem, Douglas
• Is Part Of: Computers & operations research. Volume 119(2020)
• Publication Date: 2020-07
• Subjects: Benders decomposition -- Branch-and-Benders-cut -- Decomposition-based metaheuristic -- Hybrid method -- Crew scheduling and routing -- Road restoration; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2020.104935
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: We develop two new metaheuristics to solve the crew scheduling and routing problem. We devise a new branch-and-Benders-cut approach for the crew scheduling and routing problem. We hybridize the branch-and-Benders-cut approach embedding the metaheuristics in the branch-and-cut tree that solves the master problem. The hybrid branch-and-Benders-cut approach found new optimal solutions and improved bounds for benchmark instances of the problem. Abstract: 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 that the proposed algorithms can solve large-scale instances in comparison to other methods proposed in the literature, mainly as result of the enhanced BBC method and 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.