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

Cleder Marcos Schenekemberg (), Thiago André Guimarães (), Antonio Augusto Chaves () and Leandro C. Coelho ()
Additional contact information
Cleder Marcos Schenekemberg: Federal University of São Paulo, São Paulo - SP 04021-001, Brazil; Aeronautics Institute of Technology, São José dos Campos - SP 12228-900, Brazil
Thiago André Guimarães: Federal University of Paraná, Curitiba - PR 80060-000, Brazil; Federal Institute of Science and Technology of Paraná, Curitiba - PR 80230-901, Brazil
Antonio Augusto Chaves: Federal University of São Paulo, São Paulo - SP 04021-001, Brazil
Leandro C. Coelho: Centre Interuniversitaire de Recherche sur les Reseaux d’Entreprise, la Logistique et le Transport, Montréal, Québec H3T 1J4, Canada; Université Laval, Québec City, Québec G1V 0A6, Canada

Transportation Science, 2024, vol. 58, issue 4, 687-707

Abstract: 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.

Keywords: production routing; inventory routing; branch-and-cut; matheuristic; parallel processing (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.0261 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:58:y:2024:i:4:p:687-707

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().