Information Technology Reference
In-Depth Information
specific constraints dictating the creation of services and movement of cargo. The
Inflexible Visitation LSFRP (IVLSFRP) is a simplified version of the LSFRP in
which the time of every visitation (i.e. port call) a vessel may undertake is known
in advance. Such visitations are called inflexible . In the full LSFRP, the vessel
entry/exit time of some visitations is unknown, requiring solution methods to
schedule these visitations if they are chosen for a repositioning.
The number of variables in the arc flow model from [16,18] grows linearly
in the number of graph arcs multiplied by the number of cargo demands, and,
as a result, it quickly runs out of memory or CPU time on large instances. In
this paper, we introduce a novel node flow model for the IVLSFRP that fits
into memory even on large instances, thanks to the fact that the number of
nodes tends to be significantly lower than the number of arcs. The node flow
model exploits the fact that when all visitations are inflexible, the sequencing
of demands is known in advance. We use this fact in order to model demands
based on the graph nodes they can pass through. We provide two versions of
the node flow model that each handle equipment (i.e. empty container) flows in
different ways; one version uses an arc flow formulation, and the other embeds
equipment into the problem's demand structure.
The node flow model solves 12 previously unsolved IVLSFRP instances to
optimality within 5 hours. The node flow model solves IVLSFRP instances
to optimality significantly faster than the arc flow approach, and is even able
to solve a number of instances in under a second that require 15 minutes or more
with the arc flow approach.
This paper is organized as follows. We first give an overview of the IVLSFRP
in Section 2, followed by the arc flow model presented in [16] in Section 3. We
then introduce our node based formulation of the IVLSFRP in Section 4. We
provide a computational evaluation of the new model with IBM CPLEX 12.4 in
Section 5 showing the improved performance of the node flow approach. Finally,
we conclude in Section 6.
2 Liner Shipping Fleet Repositioning
We briefly describe the IVLSFRP, and refer readers to [16] for a more detailed
description, as well as a description of the full version of the LSFRP. Liner
shipping networks consist of a set of cyclical routes, called services, that visit
ports on a regular, usually weekly, schedule. Liner shipping networks are designed
to serve customer's cargo demands, but over time the economy changes and
liner shippers must adjust their networks in order to stay competitive. Liner
shippers add, remove and modify existing services in their network in order to
make changes to the network. Whenever a new service is created, or a service is
expanded, vessels must be repositioned from their current service to the service
being added or expanded.
Vessel repositioning is expensive due to the cost of fuel (in the region of hun-
dreds of thousands of dollars) and the revenue lost due to cargo flow disruptions.
Given that liner shippers around the world reposition hundreds of vessels per
 
Search WWH ::




Custom Search