A 3D-BPP approach for optimising stowage plans and terminal productivity

This paper addresses the problem of determining stowage plans for containers in a ship, that is the so-called master bay plan problem (MBPP). MBPP is NP-complete [Botter, R.C., Brinati, M.A., 1992. Stowage container planning: A model for getting an optimal solution. IFIP Transactions B (Applications in Technology) B-5, 217-229; Avriel, M., Penn, M., Shpirer, N., 2000. Container ship stowage problem: Complexity and connection to the colouring of circle graphs. Discrete Applied Mathematics 103, 271-279]. 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 the only bin is the ship. We look for stowage plans that take into a proper account structural and operational constraints, related to both the containers and the ship, and maximise some important terminal performance indexes, such as the effective and mean net crane productivity. Our aim is to evaluate how stowage plans can influence the performance of the quay. A validation of the proposed approach with some test cases related to containership, docks at the port of Genoa (Italy) is given. The results of real instances of the problem and the comparison with a validated heuristic for MBPP, show the effectiveness of the proposed approach in producing stowage plans that minimise the total loading time and allow an efficient use of the quay equipment. (c) 2006 Elsevier B.V. All rights reserved.