Solving the Inventory Routing Problem with Logistic Ratio through Iterated Local Search

The Inventory Routing Problem (IRP) aims at determining the optimal delivery plan of a single commodity distributed from one supplier to a set of customers over a planning horizon. The goal is to minimize the total cost, which is given by the sum of transportation cost and inventory cost, the latter being incurred both at the supplier and customers for the quantity held in inventory. Because of the inventory cost, what typically happens in the optimal solution of the IRP is that customers have no inventory at the end of the horizon, which might clearly generate issues at the beginning of the next planning cycle. In practice, companies often consider a different objective function, i.e., minimizing the logistic ratio, which corresponds to the ratio of the total transportation cost to the total quantity distributed. Implicitly, minimizing the logistic ratio corresponds to minimizing the unitary transportation cost. While this fractional objective function makes a lot of sense in practical applications, it creates challenges in the design of efficient solution approaches. We present a new heuristic algorithm to tackle the IRP with logistic ratio, which is based on Iterated Local Search (ILS). The algorithm has the advantage of being easy to understand and implement, combining classical operators with “smart” moves tailored to the problem. Tests on benchmark instances, where the algorithm is compared with existing approaches, show that, despite its simplicity, the algorithm beats the competitors and is currently the state-of-the-art for the problem.