A construction and improvement heuristic for a liquefied natural gas inventory routing problem

We present a large scale ship routing and inventory management problem for a producer and distributor of liquefied natural gas (LNG). The problem contains multiple products, inventory and berth capacity at the loading port and a heterogeneous fleet of ships. The goal is to create an annual delivery program to fulfill the producer’s long-term contracts at minimum cost, while maximizing the revenue from selling LNG in the spot market. To solve this problem we have developed a construction and improvement heuristic (CIH).The CIH is a multi-start local search heuristic that constructs a set of solutions using a greedy insertion procedure. The solutions are then improved using either a first-descent neighborhood search, branch-and-bound on a mathematical formulation, or both. Tests on real-life instances show that the CIH provides good solutions in a short amount of time.

► We present a new heuristic to solve a large scale LNG inventory routing problem.
► The problem is solved using multi-start local search.
► We present local search operators customized for this particular problem.
► An intensification strategy using B&B is applied to further improve solutions.
► Best-known solutions have been found to many test instances.