A Heuristic Approach to Creating an Annual Delivery Program for an LNG Producer with Transshipment
MetadataVis full innførsel
In this thesis, an Annual Delivery Program (ADP) planning problem is studied. The objective of the ADP planning problem is to create a cost-efficient delivery schedule for a liquefied natural gas (LNG) producer, who has a fleet of heterogeneous vessels. The fleet of vessels consists of ice-going vessels and conventional vessels. The LNG producer has entered long-term contracts with customers in different parts of the world, and is committed to fulfill the demands stated in the contracts. Voyages to the customers are either direct or via a transshipment port. The direct voyages to the customers in Asia depend on the opening periods of the Northern Sea Route. If the NSR is closed, the ice-going vessels travel to the transshipment port to transfer the cargo onto a conventional vessel, which then continues the journey via the Suez Canal. Only ice-going vessels are permitted to use the NSR. The size of the storage tank at the transshipment port is a challenging factor in the ADP planning problem, and thus partial loading is implemented to avoid a bottleneck caused by residual LNG left in the tank. Partial loading only applies to the ice-going vessels sent from the producer's port, and the filling levels in the vessel tanks are regulated to reduce the effects of sloshing. The ADP planning problem can be classified as an industrial shipping problem with decision making on a tactical planning level. Relevant literature is presented to illustrate how certain properties of the problem, such as partial loading, is implemented in other works, and how different solution methods have been used to solve LNG inventory routing problems (LNG-IRP). The ADP planning problem is a maritime inventory routing problem (MIRP). MIRPs are numerically complex to solve and usually require heuristic solution methods to produce good solutions. A mixed integer programming (MIP) formulation of the ADP planning problem is developed based on the aforementioned factors, where partial loading and boil-off considerations are explicitly handled in the model formulation for some of the vessels. Because of the long planning horizon of the ADP planning problem, a rolling horizon heuristic (RHH) is proposed to solve the problem. Several strategies for the different periods within a sub-horizon are tested to solve the ADP planning problem efficiently. In addition to the RHH, an aggregation and disaggregation heuristic (ADH) is proposed as an alternative approach to solving a reduced size of the problem. The intention behind both methods is to reduce the complexity of the problem during the solution process, by either solving the problem in shorter sub-horizons or by reducing the number of nodes in the network. The solution methods are combined to create an ADP quickly. Results from these solution methods are compared with a solution from a corresponding case solved by exact method. The RHH obtains the best result for the ADP planning problem. The heuristic improves both the ADP-objective and computational time compared to the exact solution method. When the ADH is combined with the RHH to solve the aggregated case, the computational time can be decreased further. Despite the improved solution time, the RHH-ADH did not improve the solution compared with the exact solution method. The results show that the performance of the ADH depends on several factors; the chosen aggregation strategy, the solution method used for solving the aggregated case, and the amount of over- and under-deliveries in the solution for the aggregated case.