Improved branch-and-cut for the Inventory Routing Problem based on a two-commodity flow formulation

Eleftherios Manousakis, Panagiotis Repoussis, Emmanouil Zachariadis and Christos Tarantilis

European Journal of Operational Research, 2021, vol. 290, issue 3, 870-885

Abstract: This paper examines the Inventory Routing Problem (IRP) with Maximum Level inventory policy. The IRP is a broad class of hard to solve problems with numerous practical applications in the field of freight transportation and logistics. A supplier is responsible for determining the timing and the quantity of replenishment services offered to a set of customers over a multi-period time horizon. In addition, vehicle routes have to be defined jointly with the inventory related decisions. A novel two-commodity flow formulation is introduced together with a new set of valid inequalities. On this basis, a branch-and-cut algorithm that employs methods for separating various families of cuts is proposed. Extensive computational experiments are reported on well-established benchmark data sets. The proposed solution approach outmatches results of current state-of-the-art branch-and-cut, branch-and-price, metaheuristic and mathematical programming based heuristic approaches, especially for hard-to-solve instances. Notably, we report 116 new upper bounds out of 640 problems of a well-known benchmark data set. Moreover, for the first time, we present new lower and upper bounds for the same data set with a larger number of vehicles. Finally, we improve 139 upper bounds out of 200 hard-to-solve larger problems of the IRP literature.

Keywords: Transportation; Inventory routing; Two-commodity flow; Branch-and-cut; Cut separation (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720307608
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:290:y:2021:i:3:p:870-885

DOI: 10.1016/j.ejor.2020.08.047

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 ().