Program > By speaker > Roberti Roberto

Lower Bounds for the Container Ship Stowage Planning Problem
Roberto Roberti  1, *@  , Dario Pacino  1@  
1 : Technical University of Denmark  -  Website
Anker Engelunds Vej 1 Building 101A 2800 Kgs. Lyngby -  Denmark
* : Corresponding author

In this talk, we deal with the problem of finding an optimal stowage plan for containers in a container ship. Containers on board are placed in stacks, located in many bays. The container ship follows a predefined route visiting a set of ports, and, at each port, containers destined to that port are unloaded, while containers destined to the next ports are loaded. As containers can be accessed only from the top of the stack, a number of shifting operations (i.e., operations of unloading/reloading a container destined to one of the next ports to access a container destined to the current port) need to be performed. Many operational constraints have to be satisfied to provide a realizable stowage plan, but we focus on the most basic version of the problem, called the Container Ship Stowage Planning Problem (CSSPP), as introduced by Avriel and Penn, Computers and Industrial Engineering (1993).

Different heuristic approaches for the CSSPP have been proposed in the literature, but very little has been done in terms of lower bounds and exact methods for the problem. To the best of our knowledge, only two compact formulations have been proposed so far. We introduce alternative formulations and analyze the lower bounds that can be achieved from the corresponding linear relaxations. Promising computational results on real-life instances with different features will also be presented.


Online user: 1