A Branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory Routing

Faramroze G. Engineer (), Kevin C. Furman (), George L. Nemhauser (), Martin W. P. Savelsbergh () and Jin-Hwa Song ()
Additional contact information
Faramroze G. Engineer: School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, New South Wales 2308, Australia
Kevin C. Furman: ExxonMobil Research and Engineering Company, Annandale, New Jersey 08801
George L. Nemhauser: H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332
Martin W. P. Savelsbergh: School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, New South Wales 2308, Australia
Jin-Hwa Song: ExxonMobil Research and Engineering Company, Annandale, New Jersey 08801

Operations Research, 2012, vol. 60, issue 1, 106-122

Abstract: A branch-price-and-cut algorithm is developed for a complex maritime inventory-routing problem with varying storage capacities and production/consumption rates at facilities. The resulting mixed-integer pricing problem is solved exactly and efficiently using a dynamic program that exploits certain “extremal” characteristics of the pricing problem. The formulation is tightened by using the problem's boundary conditions in preprocessing and to restrict the set of columns that are produced by the pricing problem. Branching schemes and cuts are introduced that can be implemented efficiently and that preserve the structure of the pricing problem. Some of the cuts are inspired by the capacity cuts known for the vehicle-routing problem, whereas others specifically target fractional solutions brought about by individual vessels “competing” for limited inventory at load ports and limited storage capacity at discharge ports. The branch-price-and-cut approach solves practically sized problems motivated by the operations of an oil company to optimality, and it provides reasonable bounds for larger instances.

Keywords: maritime inventory routing; integer programming; column generation; dynamic programming (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (16)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.0997 (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:oropre:v:60:y:2012:i:1:p:106-122

Access Statistics for this article

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