A new decomposition algorithm for a liquefied natural gas inventory routing problem
- 7 May 2015
- journal article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 54 (2) , 564-578
Abstract
We consider an inventory routing problem (IRP) in the liquefied natural gas (LNG) supply chain, called the LNG-IRP. Here, an actor is responsible for the LNG production and inventory management at the liquefaction plants, the routing and scheduling of a heterogeneous fleet of LNG ships, as well as the inventories and sales at the regasification terminals. Furthermore, all ports have a limited number of berths available for loading and unloading. The LNG-IRP is more complicated than many other maritime inventory routing problems because a constant rate of the cargo evaporates in the tanks each day and is used as fuel during transportation. In addition, a variable number of tanks are unloaded at the regasification terminals. We introduce a new path flow formulation for this problem arising from a novel decomposition scheme based on parts of a ship schedule, called duties. A ship schedule for the entire planning horizon can be divided into duties consisting of a visit to a liquefaction plant, then one or two visits to a regasification terminal before ending in a liquefaction plant. The solution method suggested is based on a priori generation of duties, and the formulation is strengthened by valid inequalities. The same problem was previously solved by a branch-price-and-cut algorithm for a schedule-based formulation. Computational results show that the new formulation provides tighter bounds than the previous schedule-based formulation. Furthermore, on a set of 27 benchmark instances, the proposed algorithm clearly outperforms the previous branch-price-and-cut algorithm both with regard to computational time and the number of problems solved within a 10-h time limit.Keywords
This publication has 26 references indexed in Scilit:
- Thirty Years of Inventory RoutingTransportation Science, 2014
- Ship routing and scheduling in the new millenniumEuropean Journal of Operational Research, 2013
- A Branch-Price-and-Cut Algorithm for Single-Product Maritime Inventory RoutingOperations Research, 2012
- LNGScheduler: a rich model for coordinating vessel routing, inventories and trade in the liquefied natural gas supply chainJournal of Energy Markets, 2010
- Industrial aspects and literature survey: Combined inventory management and routingComputers & Operations Research, 2010
- Transportation Planning and Inventory Management in the LNG Supply Chain2010
- Maritime Inventory Routing Problems2008
- Chapter 4 Maritime Transportation2007
- Flight String Models for Aircraft Fleeting and RoutingTransportation Science, 1998
- A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems1998