Creating annual delivery programs of liquefied natural gas

The annual delivery program (ADP) setup is an important problem in liquefied natural gas (LNG) supply chain planning. The ADP for an actor in the chain is the complete sailing schedule of the ships in the fleet for the coming year. In this paper we focus on the ADP planning problem for one of the world's largest producers of LNG. 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 objective is to design an ADP to fulfill the long-term contracts at minimum cost, while maximizing revenue from selling LNG in the spot market. A mixed integer programming (MIP) formulation of the ADP planning problem is presented and solved with a branch-and-cut algorithm. Several types of valid inequalities are developed that allow us to reduce the linear programming gap of the MIP formulation. The computational study shows that the problem is very complex, but that the valid inequalities are effective.