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.