Comparing four MILP formulations for the time-dependent inventory routing problem with FIFO-compliant travel times

The Inventory Routing Problem (IRP) is an operational problem in logistics combining inventory management and vehicle routing decisions. While extensive research addresses uncertainties in travel times through robust and stochastic optimization approaches, the incorporation of deterministic time-dependent travel patterns remains almost unexplored. This paper introduces the Time-Dependent Inventory Routing Problem (TD-IRP), which explicitly incorporates realistic travel time whereby delivery times vary throughout the day in response to predictable traffic congestion patterns. We propose four mixed-integer linear programming (MILP) formulations employing distinct time-discretization schemes while strictly enforcing the First-In-First-Out (FIFO) property. Through computational experiments on benchmark instances derived from real traffic data for the city of Lyon, France, we demonstrate that formulations incorporating explicit waiting time outperform time-restrictive approaches. All four formulations achieve identical optimality for inventory decisions. Empirical results show near-optimal routing solutions with at most 5% degradation in arrival time. We further compare the best performing formulation to the static IRP baseline, quantifying the practical value of time-dependent modelling. The paper provides concrete guidance for implementation and demonstrates the tractability of time-dependent inventory routing for realistically-sized instances.