The introduction of transshipment ports in the liquefied natural gas (LNG) supply chain in recent years offers additional flexibility, but also challenges to the planning of the annual delivery program. We present a new variant of the LNG-annual delivery program (ADP) planning problem by considering transshipment as well as time-dependent sailing times. We present a continuous time formulation for the LNG-ADP problem and propose a rolling horizon heuristic to solve the problem. Both the model and heuristic were used to solve a case inspired by the Yamal LNG project. The computational results show that the heuristic provides good solutions within a relatively short amount of time, especially compared to the exact solution methods. However, there is a trade-off between computational time and solution quality when designing the rolling horizon heuristic. The results also show the impact storage capacity at the transshipment port has on the total cost.