Model and algorithm for container ship stowage planning based on bin-packing problem

Abstract

In a general case, container ship serves many different ports on each voyage. A stowage planning for container ship made at one port must take account of the influence on subsequent ports. So the complexity of stowage planning problem increases due to its multi-ports nature. This problem is NP-hard problem. In order to reduce the computational complexity, the problem is decomposed into two sub-problems in this paper. First, container ship stowage problem (CSSP) is regarded as “packing problem”, ship-bays on the board of vessel are regarded as bins, the number of slots at each bay are taken as capacities of bins, and containers with different characteristics (homogeneous containers group) are treated as items packed. At this stage, there are two objective functions, one is to minimize the number of bays packed by containers and the other is to minimize the number of overstows. Secondly, containers assigned to each bays at first stage are allocate to special slot, the objective functions are to minimize the metacentric height, heel and overstows. The taboo search heuristics algorithm are used to solve the subproblem. The main focus of this paper is on the first subproblem. A case certifies the feasibility of the model and algorithm.

Keywords

container ship / stowage / bin-packing problem / heuristics algorithm

References

[1] Avriel M, Penn M, Shpirer N., Wittebon S. Stowage planning for container ships to reduce the number of shifts [J]. Annals of Operations Research, 1998, 76: 55-71

[2] Wilson I D, Roach P A. Principles combinatorial optimization applied to container-ship stowage planning [J]. Journal of Heuristics, 1999, 5: 403-418

[3] Avriel M, Penn M, Shpirer N. Container ship stow-age problem: complexity and connection to the coloring of circle graphs [J]. Discrete Applied Mathematics, 2000, 103: 271-279

[4] DILLINGHAM J T, PERAKIS A N. Application of artificial intelligence in the marine industry [A]. Fleet Management Technology Conference[D]. Boston, 1986.

[5] BOTTER R C, BRINATI M A. Stowage container planning: a model for getting an optimal solution [A]. ICCAS'92[C]. North Holland, 1992: 217–229.

[6] Xie Jinxing, Xing Wenxun. Modern optimization algorithm [M]. 2000, Beijing: Tsinghua University Press, (in Chinese)

[7] Jonathan J. Shields. Container ship stowage: a computer-aided preplanning system [J]. Marine Technology, 1984, 21: 370-383

[8] Kemp S E, Roach P A, Ware A J, Wilson J D. Artificial intelligence for automatic container stowage planning optimization [J]. HANSA-Schiffahrt-Schiffbau-Hafen, 2004, 141(4): 22-26

[9] Sartaj S. Data structures, algorithms, and applications in C++ [M]. 1999, Beijing: China Machine Press, (in Chinese)

[10] Xing Wenxun. A bin-packing problem with over-sized items [J]. Operations Research Letters, 2000, 30: 83-88

[11] GAREY M, GRAHAM K, JOHNSON D, YAO A. Resource constrained scheduling as generalized bin-packing [J]. Journal of Combinatorial Theory, 1976, Series A: 257–298.

[12] JOHNSON D, DEMERS A, ULLMAN J, GAREY M, GRAHAM R. Worst-case performance bounds for simple one-dimensional packing algorithms [J]. SIAM Journal on Computing, 1974: 299–325.