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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ambrosino, D., and A. Sciomachen. (1998). “A Constraints Satisfaction Approach for Master Bay Plans.” In Maritime Engineering and Ports, eds Sciutto G., Brebbia C. A., WIT Press, Boston pp. 155–164.
Ambrosino, D., A. Sciomachen, and E. Tanfani. (2004). “Stowing a Containership: The Master Bay Plan problem.” Transportation Research A 38, 81–99.
Atkins W.H. (1991). Modern Marine Terminal Operations and Management, Boyle, Oakland.
Avriel, M., and M. Penn. (1993). “Exact and Approximate Solutions of the Container ship Stowage Problem.” Computers & Industrial Engineering 25, 271–274.
Avriel, M., M. Penn, N. Shpirer, and S. Witteboon. (1997). “Stowage Planning for Container Ships to Reduce the Number of Shifts.” Annals of Operations Research 76, 55–71.
Avriel, M., and M. Penn, and N. Shpirer. (2000). “Container ship Stowage Problem: Complexity and Connection to the Colouring of Circle Graphs.” Discrete Applied Mathematics 103, 271–279.
Bischoff, E.E., and M.D. Mariott. (1990). “A Comparative Evaluation of Heuristics for Container Loading.” European Journal of Operational Research 44, 267–276.
Bischoff, E.E. and M.S.W. Ratcliff. (1995). “Issues on the Development of Approaches to Container loading.” International Journal of Management Science 23(4), 377–390.
Bortfeldt, A., and H. Gehring. (2001). “A Hybrid Genetic Algorithm for the Container Loading Problem.” European Journal of Operational Research 131(1), 143–161.
Botter, R.C., and M.A. Brinati. (1992). “Stowage Container Planning: A Model for Getting an Optimal Solution.” IFIP Transactions B B-5, 217–229.
Davies, A.P., and E.E. Bischoff. (1999). “Weight Distribution Considerations in Container Loading.” European Journal of Operational Research 114, 509–527.
Dubrovsky, O., G. Levitin, and M. Penn. (2002). “A Genetic Algorithm with Compact Solution Encoding for the Container ship Stowage Problem.” Journal of Heuristics 8, 585–599.
Eley, M. (2002). “Solving Container Loading Problems by Block Arrangment.” European Journal of Operational Research 141, 393–409.
Gehring, M., and A. Bortfeldt. (1997). “A Genetic Algorithm for Solving Container Loading Problem.” International Transactions of Operational Research 4, 5/6, 401–418.
Gehring, M., M. Menscher, and A. Meyer. (1990). “Computer-based Heuristic for Packing Pooled Shipment Containers.” European Journal of Operational Research 44, 277–288.
Imai, A., E. Nishimura, S. Papadimitriu, and K. Sasaki. (2002). “The Containership Loading Problem.” International Journal of Maritime Economics 4, 126–148.
Martin, JR., SU. Randhawa, and ED.McDowell. (1988). “Computerized Containership Load Planning: A Methodology and Evaluation.” Computers & Industrial Engineering 14, 429–440.
Sciomachen, A., and E. Tanfani. (2003). “The Master Bay Plan Problem: A Solution Method Based on its Connection to the Three Dimensional bin Packing Problem.” IMA Journal of Management Mathematics 14(3), 251–269.
Thomas, B.J. (1989). Management of Port Maintenance: A Review of Current Problems and Practices. H.M.S.O, London.
Wilson, I.D. and P. Roach. (1999). “Principles of Combinatorial Optimisation Applied to Container-ship Stowage Planning.” Journal of Heuristics 5, 403–418.
Wilson, I.D. and P. Roach. (2000). “Container Stowage Planning: A Methodology for Generating Computerised Solutions.” Journal of the Operational Research Society 51(11), 248–255.
Wilson, I.D., P.A. Roach, and J.A. Ware. (2001). “Container Stowage Pre-planning: Using Search to Generate Solutions, a Case Study.” Knowledge-Based Systems 14, 3–4, 137–145.
Author information
Authors and Affiliations
Corresponding author
Additional information
This work has been developed within the research area: “The harbour as a logistic node” of the Italian Centre of Excellence on Integrated Logistics (CIELI) of the University of Genoa, Italy
Rights and permissions
About this article
Cite this article
Ambrosino, D., Sciomachen, A. & Tanfani, E. A decomposition heuristics for the container ship stowage problem. J Heuristics 12, 211–233 (2006). https://doi.org/10.1007/s10732-006-5905-1
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/s10732-006-5905-1