An iterated local search matheuristic approach for the multi-vehicle inventory routing problem

The multi-vehicle inventory routing problem considers an integrated system in which a supplier must satisfy deterministic demands from a set of customers over a finite and discrete time horizon. A limited inventory capacity is available at the customers, and a deterministic amount of product is available at the supplier in each period to fulfill customer demands with a homogeneous fleet of vehicles. The supplier decides when to resupply the customers, the quantities of product to deliver, and the routes to serve the customers. The aim is to find the best supply policy, which minimizes the total inventory and routing costs while ensuring that no stock-out occurs at the customers, while respecting the capacity of each vehicle. The problem has attracted significant attention in recent decades due to its wide applicability in fields where both inventory and routing aspects are addressed together. In this work, we present a matheuristic algorithm based on a mathematical formulation in which we associate a decision variable with each route and period. The size of this set of decision variables is clearly exponential; therefore, we devise a column generation approach in which we heuristically generate a subset of these variables within an iterated local search framework. Each iteration of the algorithm is composed by two phases: in the first one, the current model is solved by means of a general-purpose solver, whereas in the second one the model is updated by replacing some variables with a suitable subset of new variables. Once a local optimum is reached, a diversification step takes place in which the set of columns is expanded to possibly define a new starting solution. We have compared our approach with state-of-the-art algorithms on a large benchmark of instances from the literature. Our computational results show that the proposed algorithm outperforms most of the existing heuristic methods.