A decomposition heuristic for a rich production routing problem

Autor(es)

Miranda, Pedro L. ^[1] ; Cordeau, Jean-Francois ^{[2, 3]} ; Ferreira, Deisemera ^[4] ; Jans, Raf ^{[2, 3]} ; Morabito, Reinaldo ^[1]

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

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

^[2] HEC Montreal, 3000 Chemin Cote St Catherine, Montreal, PQ H3T 2A7 - Canada

^[3] CIRRELT, 3000 Chemin Cote St Catherine, Montreal, PQ H3T 2A7 - Canada

^[4] Univ Fed Sao Carlos, Dept Phys Chem & Math, Rodovia Joao Leme dos Santos Km 110, BR-18052780 Sorocaba, SP - Brazil

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 98, p. 211-230, OCT 2018.
• Citações Web of Science: 2

Resumo

We propose a decomposition heuristic to solve a rich production routing problem arising in the context of a make-to-order company. The problem is motivated by the operations of a Brazilian furniture manufacturer and considers several important features, such as multiple products, sequence-dependent setup times, a heterogeneous fleet of vehicles, routes extending over one or more periods, multiple time windows and customer deadlines, among others. An integrated mathematical model is presented and is used as a basis to develop the heuristic, which solves the problem by decomposing it in two parts that are solved iteratively. The first subproblem focuses on the production planning and customer assignment decisions, and uses an approximation for the routing costs and travel times. The second subproblem makes the routing decisions, which are further improved by a local search algorithm. The solution of the second subproblem is then used to update the approximation of the routing costs and travel times in the first subproblem. We use a large set of random instances to benchmark our heuristic against a general-purpose solver. Numerical results show that our method provides, in shorter computing times, solutions of similar quality as those obtained by the solver for instances with up to 15 customers. For larger instances, with 20 to 50 customers, the heuristic clearly outperforms the solver, which in most cases cannot find any solution after 24 h of computing time. (C) 2018 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 14/10565-8 - Modelos matemáticos e métodos de solução para o problema integrado de dimensionamento, sequenciamento e distribuição da produção com entregas fracionárias
• Beneficiário: Pedro Luis Miranda Lugo
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 15/24916-0 - Métodos de solução para um problema integrado de dimensionamento de lotes, sequenciamento e roteamento em indústrias moveleiras
• Beneficiário: Pedro Luis Miranda Lugo
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado