A variable MIP neighborhood descent for the multi-attribute inventory routing problem. (December 2020) - Coelho, Leandro Callegari; De Maio, Annarita; Laganà, Demetrio
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.