This monograph addresses several critical problems to the operations of shipping lines and
ports and provides algorithms and mathematical models for use by shipping lines and port
authorities for decision support. One of these problems is the repositioning of container ships
in a liner shipping network in order to adjust the network to seasonal shifts in demand or
changes in the world economy. We provide the first problem description and mathematical model
of repositioning and define the liner shipping fleet repositioning problem (LSFRP). The LSFRP
is characterized by chains of interacting activities with a multi-commodity flow over paths
defined by the activities chosen. We first model the problem without cargo flows with a variety
of well-known optimization techniques as well as using a novel method called linear temporal
optimization planning that combines linear programming with partial-order planning in a
branch-and-bound framework. We then model the LSFRP with cargo flows using several different
mathematical models as well as two heuristic approaches. We evaluate our techniques on a
real-world dataset that includes a scenario from our industrial collaborator. We show that our
approaches scale to the size of problems faced by industry and are also able to improve the
profit on the reference scenario by over US$14 million.
