A Branch-Price-and-Cut Algorithm for the Inventory-Routing Problem

Guy Desaulniers (), Jørgen G. Rakke () and Leandro C. Coelho ()
Additional contact information
Guy Desaulniers: Department of Mathematics and Industrial Engineering, École Polytechnique and GERAD, Montréal, Québec H3C 2A7, Canada
Jørgen G. Rakke: Department of Marine Technology, Norwegian University of Science and Technology, 7491 Trondheim, Norway
Leandro C. Coelho: Faculté des sciences de l’administration, Université Laval and CIRRELT, Québec, Québec G1V 0A6, Canada

Transportation Science, 2016, vol. 50, issue 3, 1060-1076

Abstract: The inventory-routing problem (IRP) integrates two well-studied problems, namely, inventory management and vehicle routing. Given a set of customers to service over a multiperiod horizon, the IRP consists of determining when to visit each customer, which quantity to deliver in each visit, and how to combine the visits in each period into feasible routes such that the total routing and inventory costs are minimized. In this paper, we propose an innovative mathematical formulation for the IRP and develop a state-of-the-art branch-price-and-cut algorithm for solving it. This algorithm incorporates known and new families of valid inequalities, including an adaptation of the well-known capacity inequalities, as well as an ad hoc labeling algorithm for solving the column generation subproblems. Through extensive computational experiments on a widely used set of 640 benchmark instances involving between two and five vehicles, we show that our branch-price-and-cut algorithm clearly outperforms a state-of-the-art branch-and-cut algorithm on the instances with four and five vehicles. In this instance set, 238 were still open before this work and we proved optimality for 54 of them.

Keywords: inventory routing; branch price and cut; capacity inequalities; labeling algorithm; exact algorithm (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (32)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2015.0635 (application/pdf)

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:inm:ortrsc:v:50:y:2016:i:3:p:1060-1076

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().