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

Abstract

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.