In the Inventory Routing Problem (IRP) the amount and timing of deliveries to individual customers is determined to minimize inventory holding and transportation costs. Given the complexity of the IRP, existing solution approaches are limited to solving small to medium-sized instances. We propose an alternative approach reminiscent of the Joint Replenishment Problem to minimize inventory holding and transportation costs in large scale distribution problems. Rather than servicing customers in an explicit route, subsets of customers are created and their routing cost is approximated.

To determine replenishment quantities at the level of individual customers and delivery moments at the level of subsets of customers, a branch-and-price framework is used. The master problem selects for each day at most one customer subset to be delivered by one or several vehicles to minimize costs. The customers subsets are determined by a pricing problem for which we are examining alternative approaches using routing cost approximations developed by a.o. Daganzo (1984).

The inventory routing problem under consideration is inspired by a real life case in replenishing ATMs. The banch-and-price framework is therefore tested on both artificial problem instances and real-life data.