Single item reformulations for a vendor managed inventory routing problem: computational experience with benchmark instances

The Inventory Routing Problem (IRP) involves the distribution of one or more products from a supplier to a set of customers over a discrete planning horizon. The version treated here, the so- called Vendor Managed Inventory Routing Problem (VMIRP), is the Inventory Routing problem arising when the replenishment policy is decided a priori. We consider two replenishment policies. The first is known as Order-Up (OU): if a client is visited in a period, then the amount shipped to the client must bring the stock level up to the upper bound. The latter is called Maximum Level (ML): the maximum stock level in each period cannot be exceeded. The objective is to find replenishment decisions minimizing the sum of the storage and distribution costs. VMIRP contains two important subproblems: a lot-sizing problem for each customer and a classical vehicle routing problem for each time period. In this paper we present a-priori reformulations of VMIRP-OU and VMIRP-ML derived from the single-item lot-sizing substructure. In addition we introduce two new cutting plane families - the Cut Inequalities - deriving from the interaction between the Lot-Sizing and the Routing substructures. A Branch-and-Cut algorithm has been implemented to demonstrate the effectiveness of Single-Item reformulations. Computational results on the benchmark instances with 50 customers and 6 periods with a single product and a single vehicle are presented.