A variable MIP neighborhood descent for the multi-attribute inventory routing problem. (December 2020)

• Record Type: Journal Article
• Authors: Coelho, Leandro Callegari; De Maio, Annarita; Laganà, Demetrio
• Is Part Of: Transportation research. Volume 144(2020)
• Publication Date: 2020-12
• Subjects: Variable neighborhood search -- Mixed-integer programming -- Inventory routing problem -- Exact algorithm; Logistics -- Periodicals; Transportation -- Periodicals; 388.011
• DOI: 10.1016/j.tre.2020.102137
• Languages: English
• ISSNs: 1366-5545

Abstract

Abstract: In this paper we study a Multi-Attribute Inventory Routing Problem (MAIRP). A mathematical formulation and exact solution algorithms are introduced for this problem. More precisely, we extend the Multi-Depot Inventory Routing Problem (MDIRP) in order to consider the multi-product case with a heterogeneous fleet of vehicles and explicit constraints for the route duration. The MAIRP is an NP-hard problem more complex than the classical Inventory Routing Problem. Moreover, it captures many features that can be found in real applications of a vendor-managed inventory strategy. We introduce a hybrid exact algorithm to solve it, in which several Mixed Integer Programming (MIP) models are solved to explore the neighborhoods of a Variable Neighborhood Search (VNS) scheme applied to the MAIRP. We design several neighborhoods that are based on the features of the problem. The impact of this hybridization is a faster convergence of the model and an accelerated resolution process with respect to a branch-and-cut algorithm applied to the regular MIP formulation. Extensive computational results on new and existing instances from the literature on two benchmark problems and a real data set confirm the high efficiency of our algorithm. Highlights: We provide a mathematical formulation for the multi-attribute IRP. We design a variable MIP neighborhood descendent for solving the problem. We design a branch-a-cut algorithm that embeds a local search scheme. The algorithm is very effective in terms of solution quality and computational time. The algorithm is tested on four classes of both classical and real data instances.