EXACT AND APPROXIMATE SOLUTIONS OF THE CONTAINER SHIP STOWAGE PROBLEM

This paper deals with a stowage plan for containers in a container shi p. Containers on board a container ship are placed in stacks, located in many bays. Since the access to the containers is only from the top of the stack, a common situation is that containers designated for por t i must be unloaded and reloaded at port I (before J) in order to acc ess containers below them, designated for port I. This operation is ca lled ''shifting''. A container ship calling many ports, may encounter a large number of shifting operations, some of which can be avoided by efficient stowage planning. In general, the stowage plan must also ta ke into account stability and strength requirements, as well as severa l other constraints on the placement of containers. In this paper we d eal with stowage planning in order to minimize the number of shiftings , without considering stability constraints. First, a 0-1 binary linea r programming formulation is presented that can find the optimal solut ion for stowage in a single rectangular bay of a vessel calling a give n number of ports, assuming that the number of containers to ship is k nown in advance. This model was successfully implemented using the GAM S software system. It was found, however, that finding the optimal sol ution using this model is quite limited, because of the large number o f binary variables needed for the formulation. For this reason, severa l alternative heuristic algorithms were developed. The one presented h ere is based on a ''reduced'' transportation matrix. Containers with t he same source and destination ports are stowed in full stacks as much as possible, and only the remaining containers are allocated by the b inary linear programming model. This approach often allows the stowage planning of a much larger number of containers than using the exact f ormulation.