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 IRP (VMIRP), is the IRP 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. These reformulations take into account the special nature of the test instances–constant demand for each client over time and stock/production upper bounds that are fixed small multiples of the client's demand. 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 the single‐item reformulations. Computational results on benchmark instances with 50 customers and six periods with a single product and a single vehicle are presented.