A hybrid heuristic strategy for liquefied natural gas inventory routing

•A hybrid heuristic strategy is proposed for LNG-IRP to develop LNG annual delivery plans.•A suite of construction techniques and local search methods are developed.•Computational results show better solutions over previous methods for 100% cases with significantly less CPU time.•The combination of simple neighborhood structures outperforms sophisticated neighborhood search methods.

As liquefied natural gas (LNG) steadily grows to be a common mode for commercializing natural gas, LNG supply chain optimization is becoming a key technology for gas companies to maintain competitiveness. This paper develops methods for improving the solutions for a previously stated form of an LNG inventory routing problem (LNG-IRP). Motivated by the poor performance of a Dantzig-Wolfe-based decomposition approach for exact solutions, we develop a suite of advanced heuristic techniques and propose a hybrid heuristic strategy aiming to achieve improved solutions in shorter computational time. The heuristics include two phases: the advanced construction phase is based on a rolling time algorithm and a greedy randomized adaptive search procedure (GRASP); and the solution improvement phase is a series of novel MIP-based neighborhood search techniques. The proposed algorithms are evaluated based on a set of realistic large-scale instances seen in recent literature. Extensive computational results indicate that the hybrid heuristic strategy is able to obtain optimal or near optimal feasible solutions substantially faster than commercial optimization software and also the previously proposed heuristic methods.