A three-front parallel branch-and-cut algorithm for production and inventory routing problems

dc.contributor.authorChaves, Antonio Augusto [UNIFESP]
dc.contributor.authorLatteshttp://lattes.cnpq.br/4973949421738244
dc.date.accessioned2024-05-22T16:08:08Z
dc.date.available2024-05-22T16:08:08Z
dc.date.issued2023
dc.description.abstractProduction 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 has proved optimality for 746, being the first exact algorithm to solve all instances with up to two vehicles. 3FP-B&C has found 949 best-known solutions (BKS), with 153 new BKS (NBKS). For the large-size set, our method provides two new optimal solutions (OPT), and found 82% of BKS, being 70% of NBKS for instances with up to 5 vehicles. This result is more than twice the number of BKS considering all heuristic methods from the literature combined. Finally, our 3FP-B&C found the best lower bounds (BLB) for 1169/1316 instances, outperforming all previous exact algorithms. On the PRP, our method obtained 278 OPT out of the 336 instances of Adulyasak, Cordeau, and Jans (2014a) being 19 new ones, in addition to 335 BKS (74 NBKS) and 313 BLB (52 new ones). On the PRP set of Archetti et al. (2011), our algorithm finds 1105 BKS out of 1440 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 the very large-size instance set of Boudia, Louly, and Prins (2007), 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.
dc.identifier.doihttp://dx.doi.org/ 10.1287/trsc.2022.0261
dc.identifier.urihttps://hdl.handle.net/11600/71130
dc.languageeng
dc.publisherINFORMS
dc.relation.ispartofTransportation Science
dc.rightsAcesso restrito
dc.subjectProduction-routing
dc.subjectInventory-routing
dc.subjectBranch-and-cut
dc.subjectMatheuristic
dc.titleA three-front parallel branch-and-cut algorithm for production and inventory routing problems
dc.typeArtigo
unifesp.campusInstituto de Ciência e Tecnologia (ICT)
unifesp.departamentoCiência e Tecnologia
unifesp.graduacaoNão se aplica
unifesp.graduateProgramPesquisa Operacional
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Carregando...
Imagem de Miniatura
Nome:
Manuscript.pdf
Tamanho:
622.99 KB
Formato:
Adobe Portable Document Format
Descrição:
Licença do Pacote
Agora exibindo 1 - 1 de 1
Carregando...
Imagem de Miniatura
Nome:
license.txt
Tamanho:
5.55 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Coleções