Paper:
Container Loading for Nonorthogonal Objects: Detecting Collisions
Vicenç Torra* and Sadaaki Miyamoto**
*IIIA, Institut d'Investigaci'o en Intelligència Artificial - CSIC
Campus UAB s/n, 08193 Bellaterra, Catalonia, Spain
**Department of Risk Engineering, School of Systems and Information Engineering, University of Tsukuba,
Ibaraki 305-8573, Japan
This paper considers the problem of container loading. That is, the problem of locating a predefined set of objects into containers so that the number of containers is minimized. In this paper we outline our system, which includes as a distinguished aspect the possibility of considering objects that are nonorthogonal. That is, non rectangular objects are permitted to be located in the container.
[1] M. Eley, “Solving container loading problems by block arrangement,” European Journal of Operational Research, 141, pp. 393-409, 2002.
[2] E. G. Birgin, J. M. Martnez, and D. P. Ronconi, “Optimizing the packing of cylinders into a rectangular container: A nonlinear approach,” European Journal of Operational Research, 160, pp. 19-33, 2005.
[3] J. A. George, J. M. George, and B. W. Lamar, “Packing different-sized circles into a rectangular container,” European Journal of Operational Research, 84, pp. 693-712, 1995.
[4] A. Bortfeldt, H. Gehring, and D. Mack, “A parallel tabu search algorithm for solving the container loading problem,” Parallel Computing, 29, pp. 641-662, 2003.
[5] M. Eley, “A bottleneck assignment approach to the multiple container loading problem,” OR Spectrum, 25 pp. 45-60, 2003.
[6] E. E. Bischoff and M. S. W. Ratcliff, “Issues in the Development of Approaches to Container Loading,” Omega Int. J. of Management Sciences, 23:4, pp. 377-390, 1995.
[7] A. Bortfeldt and H. Gehring, “A hybrid genetic algorithm for the container loading problem,” European Journal of Operational Research, 131, pp. 143-161, 2001.
[8] E. E. Bischoff, “Three-dimensional packing of items with limited load bearing strength,” European Journal of Operational Research, 168, pp. 952-966, 2006.
[9] A. P. Davies and E. E. Bischoff, “Weight distribution considerations in container loading,” European Journal of Operational Research, 114, pp. 509-527, 1999.
[10] D. Pisinger, “Heuristics for the container loading problem,” European Journal of Operational Research, 141, pp. 382-392, 2002.
[11] H. Gehring and A. Bortfeldt, “A Genetic Algorithm for Solving the Container Loading Problem,” Int. Trans. Operational Research, 4:5/6, pp. 401-418, 1997.
[12] H. Dyckhoff, “A typology of cutting and packing problems,” European Journal of Operational Research, 44, pp. 145-159, 1990.
[13] H. Dyckhoff and U. Finke, “Cutting and Packing in Production and Distribution,” Physica, Heidelberg, 1992.
[14] G. Zachmann, “Virtual Reality in Assembly Simulation Collision Detection,” Simulation Algorithms, and Interaction Techniques, PhD Dissertation, Technischen Universitt Darmstadt, 2000.
[15] S. Miyamoto, Y. Endo, K. Hanzawa, and Y. Hamasuna, “Metaheuristic Algorithms for Container Loading Problems: Framework and Knowledge Utilization,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.11, No.1, pp. 51-60, 2006.
[16] http://people.brunel.ac.uk/ mastjjb/jeb/orlib/files/wtpack1.txt