Information Technology Reference
In-Depth Information
window. Andersen's PhD thesis [2] discusses a problem similar to the LSFRP,
called the Network Transition Problem (NTP), but provides no mathematical
model or formal problem description, nor does the problem handle slow steam-
ing, empty equipment flows, or SOS opportunities.
Although tramp shipping problems, such as [5,10], maximize cargo profit while
accounting for sailing costs and port fees as in the LSFRP, they lack liner ship-
ping specific constraints, such as sail-on-service opportunities, phase-in require-
ments and strict visitation times. Airline disruption management (see [8,9]),
while also relying on time-based graphs, differs from the LSFRP in that airline
disruption management requires an exact cover of all flight legs over a planning
horizon. The LSFRP has no such requirement over visitations or sailing legs.
The primary previous work on the LSFRP in the literature is found in [17],
[18], [16] and [15], by the authors. The first work on the LSFRP, [17], solved
an abstraction of the LSFRP without cargo/equipment flows and SOS parallel
sailings using a hybrid of automated planning and linear programming called
Linear Temporal Optimization Planning (LTOP). However, LTOP and other
automated planning methods are unable to model cargo flows and are thus in-
applicable to the version of the LSFRP we solve in this work. A mathematical
model of the LSFRP with cargo and equipment flows is introduced in [18], and
CPLEX is used to solve the model. In [16], a simulated annealing algorithm is
used to solve instances that CPLEX was unable to solve. Finally, in [15] it is
shown that the late acceptance hill climbing technique from [4] does not outper-
form simulated annealing on the full LSFRP. Unlike in [18], [16] and [15], in this
work we only investigate a subset of the LSFRP that does not include flexible
time windows.
3 Arc Flow Mathematical Model
We describe the mathematical model of the LSFRP with cargo flows from [18]
and [16], in which demands are modeled using variables representing the amount
of flow of each demand on each arc in the graph.
3.1 Graph Description
We give an overview of the graph used in the model of the IVLSFRP with cargo
flows, and refer to [16] for details. The graph is based off of the idea of modeling
each visitation as a node in a graph, with arcs representing sailings between
visitations. We begin by letting
V
be the set of visitations for all vessels, and
defining
S
as the set of ships.
The overall structure of the graph involves three sets of visitations: phase-
out, phase-in, and SOS visitations. The three types of visitations represent three
disjoint sets that make up
V
. In addition to these visitations, we include a graph
sink,
τ
, which all vessels must reach for a valid repositioning. We let
V
=
V
τ
be the set of all graph visitations excluding
τ
. We now describe the arc structure
present in each of the three sets of visitations.
\
