A New Formulation Based on Customer Delivery Patterns for a Maritime Inventory Routing Problem

Jørgen Glomvik Rakke (), Henrik Andersson (), Marielle Christiansen () and Guy Desaulniers ()
Additional contact information
Jørgen Glomvik Rakke: Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7491 Trondheim, Norway
Henrik Andersson: Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7491 Trondheim, Norway
Marielle Christiansen: Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7491 Trondheim, Norway
Guy Desaulniers: Department of Mathematics and Industrial Engineering, École Polytechnique and GERAD, Montréal, Québec H3C 3A7, Canada

Transportation Science, 2015, vol. 49, issue 2, 384-401

Abstract: In this paper we address a maritime inventory routing problem encountered by one of the world’s largest producers of liquefied natural gas (LNG). The producer is responsible for the LNG inventories at the liquefaction plant, the loading port with a limited number of berths, and the routing and scheduling of a heterogeneous fleet of LNG ships. In addition, the producer has to fulfill a set of long-term contracts to customers all around the world. The producer’s goal is to create a minimum-cost long-term delivery program that respects the long-term contracts while maximizing revenue from selling LNG in the spot market. We introduce a new formulation for this problem arising from a novel decomposition scheme based on delivery patterns. To solve this formulation, we develop an exact branch-price-and-cut algorithm. Computational results show that this new formulation provides much tighter lower bounds than the only known mixed integer programming (MIP) formulation for this problem. Furthermore, on a set of 27 benchmark instances, the proposed branch-price-and-cut method clearly outperforms a commercial MIP solver applied to the existing MIP model.

Keywords: maritime transportation; inventory routing; branch-price-and-cut; delivery patterns; valid inequalities (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2013.0503 (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:49:y:2015:i:2:p:384-401

Access Statistics for this article

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