A three-front parallel branch-and-cut algorithm for production and inventory routing problems
Carregando...
Arquivos
Data
2023
Autores
Chaves, Antonio Augusto [UNIFESP]
Orientadores
Tipo
Artigo
Título da Revista
ISSN da Revista
Título de Volume
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 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.