Comparison of formulations for the Inventory Routing Problem

Claudia Archetti and Ivana Ljubić

European Journal of Operational Research, 2022, vol. 303, issue 3, 997-1008

Abstract: 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.

Keywords: Routing; Inventory routing; Aggregated formulation; Linear programming relaxation; Polyhedral projection (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721011073
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:303:y:2022:i:3:p:997-1008

DOI: 10.1016/j.ejor.2021.12.051

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().