Randomized Local Search for Real‐Life Inventory Routing

In this paper, a new practical solution approach based on randomized local search is presented for tackling a real‐life inventory routing problem. Inventory routing refers to the optimization of transportation costs for the replenishment of customers' inventories: based on consumption forecasts, the vendor organizes delivery routes. Our model takes into account pickups, time windows, drivers' safety regulations, orders, and many other real‐life constraints. This generalization of the vehicle‐routing problem was often handled in two stages in the past: inventory first, routing second. On the contrary, a characteristic of our local search approach is the absence of decomposition, made possible by a fast volume assignment algorithm. Moreover, thanks to a large variety of randomized neighborhoods, a simple first‐improvement descent is used instead of tuned, complex metaheuristics. The problem being solved every day with a rolling horizon, the short‐term objective needs to be carefully designed to ensure long‐term savings. To achieve this goal, we propose a new surrogate objective function for the short‐term model, based on long‐term lower bounds. An extensive computational study shows that our solution is effective, efficient, and robust, providing long‐term savings exceeding 20% on average, compared to solutions built by expert planners or even a classical urgency‐based constructive algorithm. Confirming the promised gains in operations, the resulting decision support system is progressively deployed worldwide.