Short-term planning of liquefied natural gas deliveries

The ability of a supplier of liquefied natural gas (LNG) to deliver cargoes at desired times, while effectively managing a fleet of cryogenic vessels can significantly impact its profits. We investigate in this paper an LNG short-term delivery planning problem by considering mandatory cargoes as well as optional cargoes to select, along with the scheduling of a heterogeneous vessel fleet with controllable cruising speeds. Several technical constraints are accommodated including time windows, berth availability, bunkering restrictions, inventory, liquefaction terminal storage capacity, maximum waiting time, and planned maintenance restrictions. The objective is to maximize the net profit. We propose a mixed-integer programming formulation that includes a polynomial number of variables and constraints and accommodates all of the problem features. Also, we describe an optimization-based variable neighborhood search procedure that embeds the proposed compact formulation. To assess the quality of the generated solutions, we propose a second valid formulation with an exponential number of decision variables and we solve its linear programming relaxation using column generation. We provide the results of extensive computational results that were carried out on a set of large-scale set of realistic instances, with up to 62 vessels and 160 cargoes, provided by a major LNG producer. These results provide evidence that the proposed improvement procedure yields high-quality solutions.