TWO MIXED INTEGER PROGRAMMING MODELS AND THEIR RELAXATIONS FOR THE MULTI-PORT MASTER BAY PLAN PROBLEM

In this paper we extend the problem of determining how to stow a given set of containers of different types into the available locations of a containership, that is, the so-called Master Bay Plan Problem (MBPP), to the Multi-Port Master Bay Plan Problem (MP-MBPP). In the MP-MBPP the whole route of the ship is investigated; in particular, at each port of the route different sets of containers must be loaded for being shipped to next ports. Note that, differently from MBPP, in MP-MBPP at each port the sequence of two different handling operations affects the effectiveness of stowing plans: first, the import containers must be unloaded from the ship, then the export containers can be loaded. We first introduce two exact mixed integer programming (MIP) formulations for the MP-MBPP; successively, we propose two heuristic approaches based on the solution of different relaxed formulations of the proposed MIP model. We report the computational tests performed on both random instances and real size ones which show the effectiveness of the models and the related proposed resolution methods.