A branch-and-cut algorithm for the inventory routing problem with pickups and deliveries

This paper addresses the Inventory Routing Problem with Pickups and Deliveries (IRP-PD). A single commodity has to be picked up from several origins and distributed to several destinations. The commodity is made available at the supplier depot and at the pickup customers, with known amounts in each period of a discretized time horizon. The commodity is consumed by the delivery customers, whose demand, in each period of the time horizon, is known. The vehicles start and end their routes at the supplier depot. The objective is to determine a collection and distribution plan minimizing the sum of routing and inventory costs, satisfying inventory and capacity constraints. A mixed integer linear programming model is presented for the IRP-PD. Valid inequalities are proposed that are adapted from the inventory routing, the vehicle routing and the lot-sizing problems literature. Moreover, a new set of valid inequalities, called interval inequalities, is presented. A branch-and-cut algorithm is designed and tested on a large set of instances. Computational results show that the proposed approach is able to solve to optimality 946 out of 1280 instances. Moreover, the approach outperforms the state-of-the art method for the single vehicle case, increasing the number of instances solved to optimality from 473 to 538 out of 640 instances tested, with 133 new best known solutions.