Algorithmic Intelligence logo
Skip to content empty

Last updated on 2020-08-20Projects > Generating Optimal Stowage

Generating Optimal Stowage 

This research activity under the Constraint-Based Stowage Planning Research Project is an optimal constraint programming (CP) model implemented in Gecode for stowing containers in under-deck vessel sections.

It is to our knowledge the first application of CP to stowage planning using state-of-the-art techniques such as extensive use of global constraints, viewpoints, static and dynamic symmetry breaking, decomposed branching strategies, and early failure detection. The decision variables and some constraints are illustrated in the left figure. The top right graph sohws the impact of the different techniques on the fraction of instances solved within one second.

CP is often more efficient for finding feasible solutions than optimal solutions. However, by adding a number of lower-bound estimators, our CP approach is able to outperform an integer programming and column generation approach on a large benchmark suite provided by our industrial collaborators A.P. Moller-Mærsk and Ange Optimization. Since a complete model of this problem includes even more logical constraints, we believe that stowage planning is a new application area for CP with a high impact potential.

The approach has been used to provide optimality gaps for our 3-phase local search algorithm to solve these problems.

Related Publications

Generating Optimal Stowage Plans for Container Vessel Bays , A. Delgado, R.M. Jensen, and C. Schulte, In Proceedings of the 15th International Conference on Principles and Practice of Constraint Programming (CP-09), Springer, LNCS Series, Vol. 5732, pages 6-20, 2009.



Find this page Online