A new solution approach for the inventory routing problem: Using vehicle routing problem constructive heuristic

Abstract

The Inventory Routing Problem (IRP) is an extension of the vehicle routing problem (VRP) that couples inventory control and routing decisions. This thesis studies an IRP where a warehouse replenishes several customers using a finite fleet of capacitated vehicles. Each customer faces a deterministic demand over a finite planning horizon, and has a finite capacity to keep local inventory. The goal is to minimize system-wide transportation costs over the planning horizon. Our main contribution lies in transforming this problem into an equivalent VRP with fixed size orders, in which split deliveries are allowed and orders must reach the customer between specified days. The transformation allows us to design a constructive heuristic inspired by the VRP literature. This heuristic was run on small instances, and provided solutions with a cost no more than 5.33% above optimum on average. On bigger instances, where no information is available on the optimum, our heuristic outperformed a myopic heuristic by 13.6% in average cost.