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

Author(s)

Moreno, Alfredo ^[1] ; Munari, Pedro ^[1] ; Alem, Douglas ^[2]

Affiliation

^[1] Univ Fed Sao Carlos, Prod Engn Dept, Rod Washington Luis Km 235, BR-13565905 Sao Carlos, SP - Brazil

^[2] Univ Edinburgh, Business Sch, Management Sci & Business Econ Grp, 29 Buccleuch Pl, Edinburgh EH8 9JS, Midlothian - Scotland

• Document type: Journal article
• Source: Computers & Operations Research; v. 119, JUL 2020.
• Web of Science Citations: 0

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. (C) 2020 Elsevier Ltd. All rights reserved. (AU)

• FAPESP's process: 16/15966-6 - Crew scheduling and routing in network repair under uncertainty
• Grantee: Alfredo Daniel Moreno Arteaga
• Support Opportunities: Scholarships in Brazil - Doctorate
• FAPESP's process: 15/26453-7 - Humanitarian supply chain: models and solution methods
• Grantee: Douglas José Alem Junior
• Support Opportunities: Regular Research Grants
• FAPESP's process: 16/23366-9 - Models and solution methods for variants of the inventory routing problem
• Grantee: Pedro Augusto Munari Junior
• Support Opportunities: Regular Research Grants