Formulations, branch-and-cut and a hybrid heuristic algorithm for an inventory routing problem with perishable products

Autor(es)

Alvarez, Aldair ^{[1, 2]} ; Cordeau, Jean-Francois ^{[3, 2]} ; Jans, Raf ^{[3, 2]} ; Munari, Pedro ^[1] ; Morabito, Reinaldo ^[1]

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

^[1] Univ Fed Sao Carlos, Dept Prod Engn, BR-13565905 Sao Carlos, SP - Brazil

^[2] Interuniv Res Ctr Enterprise Networks Logist & Tr, Montreal, PQ H3T 1J4 - Canada

^[3] HEC Montreal, Dept Logist & Operat Management, Montreal, PQ H3T 2A7 - Canada

• Tipo de documento: Artigo Científico
• Fonte: European Journal of Operational Research; v. 283, n. 2, p. 511-529, JUN 1 2020.
• Citações Web of Science: 0

Resumo

In this paper, we study an inventory routing problem in which goods are perishable. In this problem, a single supplier is responsible for delivering a perishable product to a set of customers during a given finite planning horizon. The product is assumed to have a fixed shelf-life during which it is usable and after which it must be discarded. We introduce four mathematical formulations for the problem, two with a vehicle index and two without a vehicle index, and propose branch-and-cut algorithms to solve them. In addition, we propose a hybrid heuristic based on the combination of an iterated local search meta-heuristic and two mathematical programming components. We present the results of extensive computational experiments using instances from the literature as well as new larger instances. The results show the different advantages of the introduced formulations and show that the hybrid method is able to provide high-quality solutions in relatively short running times for small- and medium-sized instances while good quality solutions are found within reasonable running times for larger instances. We also adapted the proposed hybrid heuristic to solve the basic variant of the inventory routing problem. The results using standard instances show that our heuristic is also able to find good quality solutions for this problem when compared to the state-of-the-art methods from the literature. (C) 2019 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 17/13739-5 - Métodos híbridos para problemas de roteamento de estoques
• Beneficiário: Aldair Alberto Alvarez Diaz
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Processo FAPESP: 17/06664-9 - Métodos exatos, heurísticos e híbridos para o problema de roteamento de estoques
• Beneficiário: Aldair Alberto Alvarez Diaz
• Modalidade de apoio: Bolsas no Brasil - Doutorado