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

Author(s)

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

Affiliation

^[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

• Document type: Journal article
• Source: European Journal of Operational Research; v. 283, n. 2, p. 511-529, JUN 1 2020.
• Web of Science Citations: 0

Abstract

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)

• FAPESP's process: 17/13739-5 - Hybrid solution methods for inventory routing problems
• Grantee: Aldair Alberto Alvarez Diaz
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• FAPESP's process: 17/06664-9 - Exact, heuristic and hybrid approaches for the inventory routing problem
• Grantee: Aldair Alberto Alvarez Diaz
• Support Opportunities: Scholarships in Brazil - Doctorate