Information Technology Reference
In-Depth Information
First, they are made under time pressure just hours before the vessel calls the
port. Second, deep-sea vessels are large and often require thousands of container
moves in a port. Third, complex interactions between low-level stacking rules and
high-level stress limits and stability requirements make it dicult to minimize
the makespan of cranes and, at the same time, overstowage. Fourth, containers to
be loaded at later ports must be taken into consideration to minimize potential
negative impacts of the current stowage plan.
In previous work [13], we presented a hierarchical decomposition approach to
stowage planning. The decomposition solves the problem in two phases. First, the
multi-port master planning
phase finds a distribution of container types to sub-
sections of the vessel. It is here that high-level stability constraints are satisfied,
the crane utilization is maximized, and
hatch-overstowage
(overstowage between
on-deck and below-deck containers) is minimized. The master planning solution
of the first port, the port we are making the plan for, becomes the input of the
second phase,
slot planning
. In the second phase, the container types assigned to
a vessel sub-section are assigned a specific positions following the stacking rules.
This phase minimizes overstowage and includes a number of heuristic rules for
improving the robustness of the plan.
The work presented in this paper focuses on the multi-port master planning
problem. In [13] an IP model for these problems was presented, which was solved
heuristically by relaxing the integrality constraints of some of the decision vari-
ables. The contribution of this paper is twofold. First we propose a different
heuristic approach, Large Neighborhood Search (LNS), that can find integer so-
lutions to the multi-port master planning problem within the 10 minutes time
limit proposed in [13]. Second, we propose a simple warm start procedure that
allows to find feasible solutions for all instances. This research is motivated by
the results published in [13] where it is possible to see that integer solutions to
the multi-port master planning problem can lead to better stowage plans.
The remainder of this paper is organized as follows. Section 2 presents the
multi-port master planning problem, followed by Section 3 with a review of re-
lated works. Section 4 describes the solution approach, which is then evaluated in
Section 5. Conclusions and proposals for future work are presented in Section 6.
2 The Multi-port Master Planning Problem
The most common ISO containers are either 20', 40', or 45' long. Other special
types exist, such as
High-cube
containers (higher than a standard container),
pal let-wide
containers (slightly wider),
reefer
containers (refrigerating units that
must be placed near power plugs), and
IMO
containers for dangerous cargo.
The capacity of a container ship is given in Twenty-foot Equivalent Units
(TEU). As shown in Figure 1, the cargo space of a vessel is divided into sections
called
bays
, and each bay is divided into an
on-deck
and a
below-deck
part by a
number of
hatch-covers
, which are flat, leak-proof structures. Each bay consists
of a row of
container stacks
divided into
slots
that can hold a 20' ISO container.
Figure 2 (a) and (b) show the container slots of a bay and stack, respectively.
