A Three-Front Parallel Branch-and-Cut Algorithm for Production and Inventory Routing Problems

Autor(es)

Schenekemberg, Cleder Marcos ; Guimaraes, Thiago Andre ; Chaves, Antonio Augusto ; Coelho, Leandro C.

• Tipo de documento: Artigo Científico
• Fonte: TRANSPORTATION SCIENCE; v. N/A, p. 22-pg., 2023-08-16.

Resumo

Production and inventory routing problems consider a single-product supply chain operating under a vendor-managed inventory system. A plant creates a production plan and vehicle routes over a planning horizon to replenish its customers at minimum cost. In this paper, we present two-and three-index formulations, implement a branch-and-cut algorithm based on each formulation, and introduce a local search matheuristic-based algorithm to solve the problem. In order to combine all benefits of each algorithm, we design a parallel framework to integrate all three fronts, called the three-front parallel branch-and cut algorithm (3FP-B & C). We assess the performance of our method on well-known benchmark instances of the inventory routing problem (IRP) and the production routing problem (PRP). The results show that our 3FP-B & C outperforms by far other approaches from the literature. For the 956 feasible small-size IRP instances, our method proves optimality for 746, being the first exact algorithm to solve all instances with up to two vehicles. 3FP-B & C finds 949 best known solutions (BKS) with 153 new BKS (NBKS). For the large-size set, our method provides two new optimal solutions (OPT), and finds 82% of BKS, being 70% of NBKS for instances with up to five vehicles. This result is more than twice the number of BKS considering all heuristic methods from the literature combined. Finally, our 3FP-B & C finds the best lower bounds (BLB) for 1,169/1,316 instances, outperforming all previous exact algorithms. On the PRP, our method obtained 278 OPT out of the 336 instances of benchmark set of small-and medium-size instances being 19 new ones in addition to 335 BKS (74 NBKS) and 313 BLB (52 new ones). On another set of PRP with medium-and large-size instances, our algorithm finds 1,105 BKS out of 1,440 instances with 584 NBKS. Besides that, our 3FP-B & C is the first exact algorithm to solve the instances with an unlimited fleet, providing the first lower bounds for this subset with an average optimality gap of 0.61%. We also address a very large-size instance set, the second exact algorithm to address this set, outperforming the previous approach by far. Finally, a comparative analysis of each front shows the gains of the integrated approach. (AU)

• Processo FAPESP: 20/07145-8 - Uma meta-heurística adaptativa aplicada ao problema dial-a-ride e variantes
• Beneficiário: Cleder Marcos Schenekemberg
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 18/15417-8 - Desenvolvimento de uma meta-heurística híbrida com fluxo de controle e parâmetros adaptativos
• Beneficiário: Antônio Augusto Chaves
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores - Fase 2
• Processo FAPESP: 16/01860-1 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento, localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático