Improved branch-and-cut for the Inventory Routing Problem based on a two-commodity flow formulation

This paper examines the Inventory Routing Problem (IRP) with Maximum Level inventory policy. The IRP is a broad class of hard to solve problems with numerous practical applications in the field of freight transportation and logistics. A supplier is responsible for determining the timing and the quantity of replenishment services offered to a set of customers over a multi-period time horizon. In addition, vehicle routes have to be defined jointly with the inventory related decisions. A novel two-commodity flow formulation is introduced together with a new set of valid inequalities. On this basis, a branch-and-cut algorithm that employs methods for separating various families of cuts is proposed. Extensive computational experiments are reported on well-established benchmark data sets. The proposed solution approach outmatches results of current state-of-the-art branch-and-cut, branch-and-price, metaheuristic and mathematical programming based heuristic approaches, especially for hard-to-solve instances. Notably, we report 116 new upper bounds out of 640 problems of a well-known benchmark data set. Moreover, for the first time, we present new lower and upper bounds for the same data set with a larger number of vehicles. Finally, we improve 139 upper bounds out of 200 hard-to-solve larger problems of the IRP literature.