Groupe d’études et de recherche en analyse des décisions

G-2012-17

Branch-Price-and-Cut for Creating an Annual Delivery Program of Multi-Product Liquefied Natural Gas

, , et

In this paper a new branch-price-and-cut method for a maritime inventory routing problem for one of the world's largest producers of liquefied natural gas (LNG) is presented. 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 long-term delivery program to fulfill the long-term contracts at minimum cost, while maximizing revenue from selling LNG in the spot market. Two mixed integer programs (MIPs) are presented and compared. The first was introduced by Rakke et al. (2011) and can be solved directly by a MIP solver. The second is new and relies on delivery patterns at the customers. To solve it, we develop an exact branch-price-and-cut algorithm. Computational results show that the new formulation provides tigther lower bounds than the first formulation and that, on a set of 27 benchmark instances, the proposed branch-price-and-cut method clearly outperforms the direct MIP method.

, 26 pages