Fast Generation of Container Vessel Stowage Plans: Using mixed integer programming for optimal master planning and constraint based local search for slot planning

Containerization has changed the way the world perceives shipping. It is now possible to establish complex international supply chains that have minimized shipping costs. Over the past two decades, the demand for cost efficient containerized transportation has seen a continuous increase. In order to answer to this demand, shipping companies have deployed bigger container vessels, that nowadays can transport up to 18,000 containers and are wider than the extended Panama Canal. Like busses, container vessels sail from port to port through a fixed route loading and discharging thousands of containers. Before the vessel arrives at a port, it is the job of a stowage coordinator to devise a stowage plan. A stowage plan is a document describing where each container should be loaded in the vessel once terminal operations commence. When creating stowage plans, stowage coordinators must make sure that the vessel is stable and seaworthy, and at the same time arrange the cargo such that the time at port is minimized. Moreover, stowage coordinators only have a limited amount of time to produce the plan. This thesis addresses the question of whether it is possible to automatically generate stowage plans to be used by stowage coordinators, and it advocates that the quality of the stowage plans and the time in which they can be generated is of the outmost importance for practical usage. We introduce a detailed description of a representative problem of the computational complexity of stowage planning that has enough detail to allow professionals from the industry to evaluate its solutions. A 2-phase hierarchical decomposition of the problem is presented. In the first phase, the problem of distributing containers to sections of the vessel is solved, and it is here that the seaworthiness of the solution is evaluated. In the second phase, the assignment of containers is refined to specific positions within the ship and lower level constraints are handled. The approach has been implemented with a combination of operations research and artificial intelligence methods, and has produced promising results on real test instances provided by a major liner shipping company. Improvements to the modeling of vessel stability and an analysis of its accuracy together with an analysis of the computational complexity of the container stowage problem are also included in the thesis, resulting in an overall in-depth analysis of the problem.