The master bay plan problem: a solution method based on its connection to the three-dimensional bin packing problem

摘要

This paper addresses the problem of determining stowage plans for containers in a ship, referred to as the Master Bay Plan Problem (MBPP). MBPP is NP-complete. We present a heuristic method for solving MBPP based on its relation with the three-dimensional bin packing problem (3D-BPP), where items are containers and bins are different portions of the ship. Our aim is to find stowage plans, taking into account structural and operational constraints related to both the containers and the ship, that minimize the time required for loading all containers on board. A validation of the proposed approach with some test cases is given. The results of real instances of the problem involving more than 1400 containers show the effectiveness of the proposed approach for large scale applications.