1 Software Development Group, Software & Systems, The Department2 Software & Systems, The Department3 Software Development Group, Theoretical Computer Science, The Department4 Computer Science, IT University of Copenhagen5 IT University of Copenhagen6 King's College London7 IT University of Copenhagen8 King's College London
The Liner Shipping Fleet Repositioning Problem (LSFRP) poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between services in a liner shipping network. The LSFRP is characterized by chains of interacting activities, many of which have costs that are a function of their duration; for example, sailing slowly between two ports is cheaper than sailing quickly. Despite its great industrial importance, the LSFRP has received little attention in the literature. We show how the LSFRP can be solved sub-optimally using the planner POPF and optimally with a mixed-integer program (MIP) and a novel method called Temporal Optimization Planning (TOP). We evaluate the performance of each of these techniques on a dataset of real-world instances from our industrial collaborator, and show that automated planning scales to the size of problems faced by industry.
Icaps 2012, the 22nd International Conference on Automated Planning and Scheduling, 2012, p. 279-287