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

Autor(es)

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

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 119, JUL 2020.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 16/15966-6 - Programação e roteamento de equipes de trabalho na restauração de redes sob incerteza
• Beneficiário: Alfredo Daniel Moreno Arteaga
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 15/26453-7 - Cadeia de suprimentos humanitária: modelos e métodos de solução
• Beneficiário: Douglas José Alem Junior
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 16/23366-9 - Modelos e métodos de solução para variantes do problema de roteamento de estoques
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Auxílio à Pesquisa - Regular