Information Technology Reference
In-Depth Information
types, to sub-sections of bays (
locations
). A master plan is the intermediary result
of the hierarchical decomposition previously introduced, but it can also be seen
as a strategic plan that can be used to evaluate different loading scenarios. Given
a list of containers to load (
loadlist
) and a forecast of future loads, the multi-port
master planning problem is the problem of finding a feasible master plan that
minimizes hatch-overstowage and crane makespan (crane utilization).
It is impractical to study large optimization models that include all details of
stowage planning. On the other hand, all major aspects of the problem must be
modeled for the results to be valuable. For container types this includes 20', 40',
and reefer containers. In addition, since stability, trim, draft and stress moment
limits should not fully be ignored, some weight classes of containers must be
introduced. It is also important to take into consideration the containers already
onboard the vessel (the
release
) when arriving at the current port.
3 Related Work
The number of publications on stowage planning has grown substantially within
the last few years. Contributions can be divided into two main categories: single-
phase and multi-phase approaches. Multi-phase approaches decompose the
problem hierarchically. They are currently the most successful in terms of model
accuracy and scalability. The earliest work can be traced back to a 3-phase
heuristic [16], but the first contribution that models several major aspects of the
problem is a 2-phase approach that solves a master planning phase for multiple
ports with a branch-and-bound algorithm and uses tabu search for bay plan-
ning [17]. Other approaches that use a similar decomposition include solving
multi-port master planning with an iterative improvement approach based on
the transportation simplex method [10] and a bin-packing heuristic [19]. 3-phase
approaches include combinations of constructive heuristics, 0/1 IP, and meta-
heuristics (e.g., [1]) and heuristics combined with LS (e.g., [18]). To the best
of the authors knowledge, the model that covers the most important aspect of
stowage planning is that of Pacino et al. [13], which also represents the basis of
this research.
Single-phase approaches represent the stowage planning problem (or parts
of it) in a monolithic optimization model. Those works do not include a master
planning problem, however, for completeness we would like to point the reader to
approaches (among others) based on IP models [3,9,11], constraint programming
[2,6,12], and heuristics [5,7,8,4].
4 Large Neighborhood Search (LNS)
LNS is a search procedure which has been proved effective in solving large-scale
combinatorial optimization problems [14]. LNS is based on a destruction/
construction principle. Once an initial solution is found, part of the variable as-
signments are relaxed (
destruction
), while keeping the remaining variables fixed.
A new solution is then found by re-optimizing the assignment of the free variables,
