Optimizing the long-term costs of an Inventory Routing Problem using linear relaxation

Abstract

The Inventory Routing Problem (IRP) arises in logistics operations when routing and inventory decisions are made simultaneously. In this work, some ideas to improve the long-term performance of the rolling horizon strategy are explored. First, three simple modifications to the IRP are tested to improve its long-term performance: using safety stocks, defining minimum inventory levels for the last period of the planning horizon, and using an artificial discount rate in the objective function. We use this improved IRP as a benchmark. Then, a solution strategy is proposed where an approximation is used in the final periods of the planning horizon, which is based on the linear relaxation of the IRP. The algorithm is calibrated and, through simulation, compared to the benchmark on a set of randomly generated instances with up to 30 customers, three vehicles, and 20 periods, and different costs and uncertainty levels. It is shown that the proposed algorithm is, on average, three times faster than the benchmark and generates savings between 1% and 2%. Under favorable conditions (low uncertainty, low inventory cost, and one vehicle), it can generate savings of around 10% in long-term costs.