Comparison of formulations for the Inventory Routing Problem

In this paper we propose an analysis and comparison of the strength of the lower bound, measured as the value of the linear programming relaxation, of different formulations for the Inventory Routing Problem (IRP). In particular, we first focus on aggregated formulations, i.e., formulations where variables have no index associated with vehicles, and we analyse the link between compact formulations and their counterparts involving exponentially many constraints. We show that they are equivalent in terms of value of the linear relaxation. In addition, we study the link between aggregated and disaggregated formulations, i.e., formulations where variables have an index related to vehicles. Also in this case, we show that aggregated and disaggregated formulations are equivalent in terms of the value of the corresponding linear relaxation. To the best of our knowledge, this analysis has never been done for the IRP, which instead is gaining a lot of popularity in the literature. Finally, we propose different exact solution approaches based on the aggregated formulations and we compare them with state-of-the-art exact methods for the IRP. Results show that the approaches based on aggregated formulations are competitive in terms of quality of both upper and lower bounds.