A decomposition heuristics for the container ship stowage problem

Author： Ambrosino Daniela Sciomachen Anna Tanfani Elena

ISSN： 1381-1231

Source： Journal of Heuristics, Vol.12, Iss.3, 2006-05, pp. : 211-233

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

In this paper we face the problem of stowing a containership, referred to as the Master Bay Plan Problem (MBPP); this problem is difficult to solve due to its combinatorial nature and the constraints related to both the ship and the containers. We present a decomposition approach that allows us to assign a priori the bays of a containership to the set of containers to be loaded according to their final destination, such that different portions of the ship are independently considered for the stowage. Then, we find the optimal solution of each subset of bays by using a 0/1 Linear Programming model. Finally, we check the global ship stability of the overall stowage plan and look for its feasibility by using an exchange algorithm which is based on local search techniques. The validation of the proposed approach is performed with some real life test cases.