Planning at King's

  • Increase font size
  • Default font size
  • Decrease font size

Liner Shipping Fleet Repositioning

E-mail Print PDF

A Maersk ship.  Used under CC licence, from at the heart of global trade, liner shipping networks transported over 1.3 billion tons of cargo on over 9,600 container vessels in 2011.  Vessels are regularly repositioned between services in liner shipping networks to adjust the networks to the world economy and stay competitive. Since repositioning a single vessel can cost hundreds of thousands of US dollars, optimizing the repositioning activities of vessels is an important problem to the liner shipping industry.

The Liner Shipping Fleet Repositioning Problem (LSFRP) consists of finding minimal cost sequences of activities that move vessels from one service to another within a liner shipping network.  Fleet repositioning involves sailing and loading activities subject to complex handling and timing restrictions. As is the case for many industrial problems, the objective is cost minimization (including costs for CO2 emissions and pollution), and it is important that all cost elements, including those that are only loosely coupled with activity choices, can be accurately modeled.


Amanda Coles and Andrew Coles have been working with researchers from the Decision Optimization Lab, ITU Copenhagen on using planning to solve LSFRP problems, using three approaches:

  • A Mixed Integer Programming (MIP) model
  • A 'Linear Temporal Optimisation Planning' (LTOP) formulation - using partial-order planning with a linear-continuous cost model
  • An extended version of POPF, with a novel mechanism for reasoning with Timed Initial Literals

A publication on this work is to appear at ICAPS 2012.  For a PDDL definition of the problem, Kevin Tierney has one available in the PDDL section of his website.

Amanda Coles's involvement in this work is supported by her EPSRC Fellowship, 'Maximising Efficiency of Resource Usage Under Uncertainty in AI Planning'.  The industrial collaborators were Mikkel Muhldorff Sigurd and Shaun Long at Maersk Line.  This research was sponsored in part by the Danish Council for Strategic Research as part of the ENERPLAN research project.