A 3-Phase Randomized Constraint Based Local Search Algorithm for Stowing Under Deck Locations of Container Vessel Bays
TR-2010-123, Authors: Dario Pacino and Rune Møller Jensen
Dario Pacino Rune Møller Jensen
January 2010
Abstract
Even though containerized shipping is an eco-friendly mode of transportation and millions of containers are stowed every week, container vessel stowage is an all but neglected combinatorial optimization problem. The currently most successful approaches use hierarchical decompositions of the problem. The sub-problems of these decompositions consist of assigning containers to slots in individual vessel bays and for automated stowage systems to be useful for stowage coordinators they each must be solved within a few seconds. In this article, we define to our knowledge the most accurate representative model to date of these problems that we have developed in close collaboration with a larger liner shipping company since 2005. We introduce a 3-phase randomized constraint based local search algorithm to solve the problems. The performance of our algorithm has been compared to a complete and highly competitive constraint programming approach that we have developed in a parallel project on a large benchmark suite extracted from real stow-plans from our industrial partner. Our experimental results show that our approach robustly finds optimal or near optimal solutions within a fraction of a second. Our results support the hypothesis that these sub-problems due to a high-level goal of clustering similar containers in a bay often are under-constrained and thus particularly suited for local search.
Technical report [TR-2010-123] in IT University Technical Report Series, January 2010.
Available as PDF.