Metaheuristic Algorithms for Container Loading Problems: Framework and Knowledge Utilization
Sadaaki Miyamoto*, Yasunori Endo*, Koki Hanzawa**,
and Yukihiro Hamasuna**
*Department of Risk Engineering, Faculty of Systems and Information Engineering, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan
**Master’s Program in Risk Engineering, Graduate School of Systems and Information Engineering, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305-8573, Japan
A family of automatic container loading problems is studied and algorithms are proposed. The algorithms are constructed with metaheuristics and include flat and/or vertical loading schemes, loading efficiency, stability of loaded objects, and computational requirement. Commonsense and expert knowledge incorporation is considered to combine with metaheuristics. Handling groups of objects in a metaheuristic scheme is moreover considered. Numerical examples are given.
-  A. Albano and G. Sapuppo, “Optimal allocation of two-dimensional irregular shapes using heuristic search methods,” IEEE Trans. Syst., Man, Cybern., Vol.10, No.5, pp. 242-248, 1980.
-  E. E. Bischoff and M. S. W. Ratcliff, “Issues in the development of approaches to container loading,” Omega, Vol.23, No.4, pp. 377-390, 1995.
-  A. Bortfeldt and H. Gehring, “A hybrid genetic algorithm for the container loading problem,” European J. Oper. Res., Vol.131, pp. 143-161, 2001.
-  M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness,” San Francisco: Freeman, 1979.
-  P. C. Gilmore and R. E. Gomory, “Multistage cutting stock problems of two or more dimensions,” Oper. Res., Vol.13, pp. 94-120, 1965.
-  S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, Vol.220, pp. 671-680, 1983.
-  OR library (http://mscmga.ms.ic.ac.uk)
-  S. Takahara and S. Miyamoto, “Adaptive algorithms of metaheuristics with application to optimal allocation problems,” Proc. 1999 IEEE Int. Conf. Systems, Man, and Cybernetics, Tokyo, pp. III-545–III-550, 1999.
-  S. Takahara, Y. Kusumoto, and S. Miyamoto, “An adaptive metaheuristic approach using partial optimization to non-convex polygons allocation problem,” Proc. 10th IEEE Int. Conf. Fuzzy Systems, Melbourne, 2001.
-  D. Smith, “Bin packing with adaptive search,” Proc. 1st Int. Conf. Genetic Algorithms and Their Applications, Pittsburgh, pp. 202-207, 1985.
-  Y. G. Stoyan, M. V. Novozhilova, and A. V. Kartashov, “Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem,” European J. Oper. Res., Vol.92, pp. 193-210, 1996.
-  Patent, No.11-208604, Japan, 1999.
-  S. Miyamoto, Y. Endo, S. Takahara, K. Urayama, and K. Terada, “Metaheuristic methods and system development for automatization in freight systems,” Proc. 14th Intelligent System Symposium (FAN2004), pp. 331-334, 2004.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.