Optimizing Allocation of Two Dimensional Irregular Shapes using an Agent Based Approach

Authors: Ramin Halavati, Saeed B. Shouraki, Mahdieh Noroozian, Saman H. Zadeh

Abstract:

Packing problems arise in a wide variety of application areas. The basic problem is that of determining an efficient arrangement of different objects in a region without any overlap and with minimal wasted gap between shapes. This paper presents a novel population based approach for optimizing arrangement of irregular shapes. In this approach, each shape is coded as an agent and the agents' reproductions and grouping policies results in arrangements of the objects in positions with least wasted area between them. The approach is implemented in an application for cutting sheets and test results on several problems from literature are presented.

Keywords: Optimization, Bin Packing, Agent Based Systems.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1078394

References:

[1] Freeman H. and Shapira R. Determining the minimum area encasing rectangle for an arbitrary closed curve. Communications of the ACM, pp 409-413, 1975.
[2] Adamowica M. and Albano A. Nesting two dimensional shapes in rectangular modules. Computer Aided Design, pp 27-33, 1976.
[3] Dori D. and Ben-Bassat M.. Efficient nesting of congruent convex figures. Communications of the ACM, pp 228- 235, 1984.
[4] Qu W. and Sandersc J. A nesting algorithm for irregular parts and factors affecting trim losses. International Journal of Production Research, pp 381-397, 1987.
[5] Dowsland K. and Dowsland W. Heuristic approaches to irregular cutting probelms. Working Paper EBMS, 1993.
[6] Albano A. and Sapuppo G. Optimal allocation of two dimensional irregular shapes using heuristic search method. IEEE Transactions on Systems, Man, and Cybernetics, pp 242-248, 1980.
[7] Blazewicz H. P., Walkowiak J. Using a tabu search approach for solving the two-dimensional irregular cutting problem. Annals of Operations Research, pp 313-327, 1993.
[8] Sakait J. and Hae C. Two-dimensional packing problems using genetic algorithms. Engineering with Computers, pp 206-213, 1998.
[9] Keishi S. N., Yoji S. and K. The multi-bsg: stochastic approach to an optimal packing of convex-rectilinear blocks. ICCAD98, pp 267-274, January 1998.
[10] Maggie Z. and Wayne W. Arbitrary rectilinear packing based on sequence pair. ICCAD98, pp 257-266, 1998.
[11] Chen P., Fu Z., Lim A., and Rodrigues B., Two dimensional Packing for Irregular Shaped Objects, In proceedings of the thirty-sixth Hawaii International Conference on System Sciences (HICSS-36) 2003, Big Island, Hawaii, USA.
[12] Halavati R., Shouraki S.B., Zedeh S.H., Lucas C., Zamin, an Agent Based Artificial Ecosystem, Proceedings of Forth Hybrid Intelligent Systems Conference (HIS'04) 2004, Kitakyushu, Japan.
[13] Jakobs S., On genetic algorithms for the packing of Polygons, European Journal of Operations Research 88, 165-181, 1996.
[14] Ratanapan K. and Dagli C. H., An object-based evolutionary algorithm for solving irregular nesting problems. In: Proceedings for Artificial Neural Networks in Engineering Conference (ANNIE '97), vol. 7, ASME Press, New York, pp. 383-388, 1997.
[15] Ratanapan K. and Dagli C. H., An object-based evolutionary algorithm: the nesting solution. In: IEEE (eds.) Proceedings of the International Conference on Evolutionary Computation 1998, ICEC '98, IEEE, Piscataway, NJ, USA, pp. 581-586, 1998.
[16] 7. Dighe R. and Jakiela M. J., Solving Pattern Nesting Problems with Genetic Algo-rithms Employing Task Decomposition and Contact Detection. Evolutionary Com-putation 3, 239-266, 1996.
[17] Burke E. and Kendall G., Applying Simulated Annealing and the No Fit Polygon to the Nesting Problem. Proceedings of the World Manufacturing Congress, Durham, UK, pp. 27-30, 1999.
[18] Hopper E, Two-dimensional Packing utilizing Evolutionary Algorithms and other Meta-Heuristic Methods, PHD Thesis, University of Wales, Cardiff, 2000.
[19] Pasha A., Geometric bin packing algorithm for arbitrary shapes, MSThesis, Center for Intelligent Machines and Robotics, Department of Mechanical and Aerospace Engineering,University of Florida, 2003.
[20] Fujiyoshi K, Murata H, Arbitrary convex and concave rectilinear block packing using sequence-pair, Proceedings of the 1999 international symposium on Physical design.