Information Technology Reference
In-Depth Information
(a) A non-fixed time graph.
(b) A fixed time graph.
Fig. 2.
Subsets of an LSFRP graph with potential vessel paths (red, blue)
Fig. 3.
Sequential demand delivery in a multiple demand destination problem
First, consider the non-fixed time case in Figure 2(a). The red path (
a,b,c,d
)
and blue path (
a,c,b,d
) show two potential voyages of a vessel. On the red path,
demand (
a, c
)isloadedwhilethevesselisat
a
, and then the vessel continues to
b
, where it loads (
b,d
). Thus, on the red path both demands are loaded on the
vessel simultaneously. On the blue path, the vessel first loads the (
a, c
) demand,
sails to
c
where it is delivered, and continues to
b
where it loads (
b,d
). In this
case, the demands are loaded sequentially. Now consider the fixed time case in
Figure 2(b), in which the time when
b
occurs is known in advance. The red path
visits nodes
a,b,c,d
, and demand (
a, c
)and(
b,d
) are on the ship simultaneously
at
b
. In fact, there is no path in the fixed time case where (
a, c
)and(
b,d
)canbe
loaded sequentially; they are either both on the ship or only (
a, c
) is on the ship.
In the LSFRP, a single demand can be delivered to any visitation in a set of
destinations. These destinations all correspond to a single real-world port being
visited by different services at different times. The arc flow model takes these
multiple destinations into account by simply having each destination visitation of
a demand act as a sink for that demand. This is advantageous for the model, since
modeling each origin-destination pair individually would require many variables.
However, in the node flow model, multiple destinations can cause a situation in
which certain incoming arcs of nodes are over-constrained. This could result in
the optimal solution not being found.
Example 2.
Consider Figure 3, which shows a graph with the vessel path
a,b,e,f
shown with red, and the demands
. Since it is possible for
both demands to be flowing on arc (
e,f
), a constraint must be posted ensuring
that
x
(
a,{b,f}
)
+
x
(
e,{f}
)
{
(
a,
{
b,f
}
)
,
(
e,
{
f
}
)
}
u
d
s
. When a vessel travels on the path shown, the
first demand, rather than being delivered to
f
, is dropped off at
b
. The vessel then
continues to
e
where it loads the second demand. Consider the case where the
capacity of the vessel is 50 TEU and both demands have 50 TEU available. Due
to the constraint we must post on arc (
e,f
), we can only take a maximum of 50
TEU of both demands, even though it is possible to carry both demands in full.
≤
