Information Technology Reference
In-Depth Information
A Node Flow Model for the Inflexible Visitation
Liner Shipping Fleet Repositioning Problem
with Cargo Flows
Kevin Tierney and Rune Møller Jensen
IT University of Copenhagen, Copenhagen, Denmark
{
kevt,rmj
}
@itu.dk
Abstract.
We introduce a novel, node flow based mathematical model
for the fixed-time version of a central problem in the liner shipping indus-
try called the Liner Shipping Fleet Repositioning Problem (LSFRP). We
call this version of the problem the Inflexible Visitation LSFRP (IVLS-
FRP). During repositioning, vessels are moved between routes in a liner
shipping network. Shipping lines 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. We introduce two ver-
sions of a node flow based model that exploit the fixed activity times
of the IVLSFRP's graph to handle cargo demands on the nodes of the
graph, instead of the arcs, significantly reducing the number of variables.
Using this model in CPLEX, we are able to solve 12 previously unsolved
IVLSFRP instances to optimality. Additionally, we improve the solution
time on every instance in the IVLSFRP dataset, sometimes by several
orders of magnitude.
1 Introduction
Liner shipping networks are the lifeblood of the world economy, providing cheap
and reliable freight services between nations around the globe. Vessels are regu-
larly repositioned between services in liner shipping networks to adjust networks
to the continually changing world economy. Repositioning vessels involves creat-
ing a plan for a set of vessels out of a number of cost saving (or revenue earning)
activities that moves (
repositions
) the vessels to a particular route in the net-
work. Since repositioning a single vessel can cost hundreds of thousands of US
dollars, optimizing the repositioning activities of vessels is an important problem
for the liner shipping industry.
The Liner Shipping Fleet Repositioning Problem (LSFRP) with cargo flows,
first introduced in [18], consists of finding sequences of activities that move
vessels between services in a liner shipping network while respecting the cargo
flows of the network. The LSFRP maximizes the profit earned on the subset of
the network affected by the repositioning, balancing sailing costs and port fees
against cargo and equipment revenues, while respecting important liner shipping
