# The BAYSTOW Research Project

The objective of the project is to research and develop optimization algorithms for container vessel stowage planning. The project focuses on hierarchically decomposed stowage planning algorithms that are among the currently most successful approaches. A major objective of the project is to investigate the low-level sub-problems solved by these algorithms, where individual containers are assigned to specific slots for each storage section of the vessel. Our hypothesis is that these stowage problems are under-constrained, because the large number of storage sections (typically more than 100) makes it possible to cluster containers of similar type in each section (e.g., containers with the same discharge port) which we believe makes the complexity of these problems significantly lower.

To test this hypothesis, we derived a representative model for stowing containers in under deck bays (CSPUDL) together with Ange Optimization and developed a *constrained-based local search algorithm* (LS) that we compared with an optimal *constraint programming algorithm* (CP) to solve these stowage sub-problems. In support of the hypothesis, despite of the sub-optimality of the LS approach, it was able to robustly find near optimal solutions fast (less than 1 sec.) on a large set of real stowage problems provided by *A.P. Moller-Maersk*. The CP approach was also able to find optimal solutions very fast in many cases, but for a significant fraction of cases, it had to spent unjustifiable long time on proving optimality.

The contributions of this research are two-fold. First, it shows that the low-level stowage sub-problems are characterized by having many optimal or near optimal solutions such that they can be efficiently solved using local search. However, since optimal solutions also often can be found fast, our recommendation is to run the two algorithms in parallel and grab the optimal solution if it is found within a time limit, and otherwise take the one found by the LS approach. Second, which is maybe more important, it shows that even though, both the low-level problem of assigning containers to slots in each storage section is NP-Complete and the high-level problem of distributing containers to storage sections is NP-Complete, in practice the high-level problems are much more difficult than the low-level problems.