A path-based two-commodity flow model and a branch-price-and-cut algorithm for the inventory routing problem with time windows

Official URL: https://dx.doi.org/10.1111/itor.70235

We study an inventory routing problem with time windows (IRPTW). A single supplier serves a set of customers to fulfill their demand throughout a planning horizon. Each customer can be visited only within designated time windows, assuming each customer provides a single delivery time window valid for all periods. We propose a two-commodity flow formulation for this problem and develop a branch-price-and-cut algorithm to solve it. We test our algorithm on a rich set of benchmark instances with fixed and time-varying demands and with up to 100 customers. Computational experiments demonstrate the effectiveness of this approach. Within a 2-hour time limit, it can provide a lower bound for all 492 tested instances. Furthermore, 211 of them are solved to optimality, achieving an average optimality gap of 4.07% for large instances and closing the gap for 11 instances for the first time in the literature.