An overview of heuristic methods for the Master Bay Plan Problem
by
Daniela Ambrosino
University of Genova - DIEM - Via Vivaldi 5
Coauthors: Davide Anghinolfi, Massimo Paolucci, Anna Sciomachen

In this work we compare different heuristics proposed in the recent literature for the problem of determining stowage plans for containership, that is the so called Master Bay Plan Problem (MBPP). MBPP is NP-complete.

The first approach is an exchange algorithm which is based on local search (LS) techniques. The second approach corresponds to an extension of LS based on the tabu search (TS) metaheuristic, which in particular exploits a wider neighbourhood structure. Finally, we use ant colony optimization (ACO) algorithm: at each iteration of the main loop any ant of a set of m artificial ants constructs a solution performing an inner loop of progressive assignment decisions. Then, a local search phase is executed in order to try to locally improve (in terms of cost and/or feasibility) the best solution found in the iteration. After that, a global pheromone update phase, corresponding to the ant colony learning mechanism, takes place and whole process is iterated. Three different stopping criteria are used.

An extensive computational experimentation related to both random instances and real size ones is reported. In particular, the performance of the proposed methods is evaluated and compared with respect to a classification of the parameters of the problem (e.g. weight, destination and size of the containers) for a 5632 TEUs containership.

Date received: March 14, 2008