The Liner Shipping Fleet Repositioning Problem with Cargo Flows

We solve an important problem for 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 services 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 great industrial importance, the LSFRP has received little attention in the literature. We introduce a novel mathematical model of the LSFRP with cargo flows based on a carefully constructed graph and evaluate it on real world data from our industrial collaborator.