Information Technology Reference
In-Depth Information
|
S
|
|
V
|
|
A
|
|
Θ
|
ships,
is the number of visitations,
is the number of arcs,
is the
|
t∈T
V
t
∗
|
E
|
|
number of demands,
=
is the number of visitations with either an
|
SOS
|
equipment surplus or deficit, and
is the number of SOS structures in the
graph. The EAD model is able to solve all but three of the confidential IVLSFRP
instances within 5 hours of CPU time, while the EAF model solves 3 previously
unsolved instances. Additionally, for instances with between one and eight ships,
the CPU time is significantly improved, with an average decrease in CPU time
of 138 seconds for both EAF and EAD over AF. The largest speed improvement
is on instance repo30c, where EAF and EAD are roughly 500 times faster than
AF.
Even on the instances where EAD or EAF timeout, CPLEX is able to provide
feasible solutions, unlike in the case of the AF model, where no feasible solution is
found for any instance that exceeds the memory allotment or CPU timeout. The
EAD model is able to find a solution with a 10.16% gap (to the LP relaxation)
for repo42c, a 96.41% gap on repo43c, and an 88.96% gap on repo44c. Although
EAD requires over an hour to solve several instances, it finds the optimal solution
within an hour on both repo37c and repo40c, but requires extra time to prove
optimality. On repo39c and repo40c, EAD is able to find an optimality gap of
8.31% and 10.07% within an hour, respectively.
Table 2 gives our results for the public instances in the IVLSFRP dataset. The
columns of the table are identical to Table 1. As in the case of the confidential
instances, the node flow model achieves significant performance gains, both in
the EAF and EAD cases. With the EAD model, the node flow model is able
to provide an optimal answer to every instance in the datset. The largest time
improvements are on instances repo27p, repo28p and repo29p, where both the
EAD and EAF models allow CPLEX to find the optimal solution in under a
second, but the AF model requires over 15 minutes.
6Con lu on
We introduced a novel, node flow based mathematical model for the IVLSFRP, a
fundamental problem to the operations of the world's shipping lines. We provided
two versions of the node flow model, in which we modeled equipment flows using
an arc flow approach, as well as by converting the equipment flows into demands.
Both versions of the model showed significant speedups over the arc flow model,
and were able to solve IVLSFRP instances to optimality in CPLEX that the
arc flow model cannot even load into memory. In addition, our node flow model
offers multiple orders of magnitude improvements on a number of instances in
the LSFRP dataset. For future work, we will try to apply the ideas from the
node flow model to the full LSFRP.
Acknowledgements.
We would like to thank our industrial collaborators
Mikkel Muhldorff Sigurd and Shaun Long at Maersk Line for their support and
detailed description of the fleet repositioning problem. This research is sponsored
in part by the Danish Council for Strategic Research as part of the ENERPLAN
research project.
