Solving The Liner Shipping Fleet Repositioning Problem with Cargo Flows

TR-2013-165, Authors: Kevin Tierney, Björg Áskelsdóttir, Rune Møller Jensen, and David Pisinger

Solving The Liner Shipping Fleet Repositioning Problem with Cargo Flows

Kevin Tierney
Björg Áskelsdóttir
Rune Møller Jensen
David Pisinger

February 2013

Abstract

 We solve a central problem in the liner shipping industry called the Liner Shipping Fleet Repositioning Problem (LSFRP). The LSFRP poses a large financial burden on liner shipping firms. During repositioning, vessels are moved between routes in a liner shipping network. Shippers wish to reposition vessels as cheaply as possible without disrupting the cargo flows of the network. The LSFRP is characterized by chains of interacting activities with a multi-commodity flow over paths defined by the activities chosen. Despite its industrial importance, the LSFRP has received little attention in the literature.  We introduce a novel mathematical model and a simulated annealing algorithm of the LSFRP with cargo flows that makes use of a carefully constructed graph and evaluate them on real world data from our industrial collaborator. Additionally, we compare our approach's performance against an actual repositioning scenario, one of many undertaken by our industrial collaborator in 2011, in which our simulated annealing algorithm is able to double the profit earned in our industrial collaborator's solution to $15.5 million dollars using only few minutes of CPU time, showing that our algorithm could be used in a decision support system to solve the LSFRP.

Technical report TR-2013-165 in IT University Technical Report Series, February 2013.

Available as PDF