Optimizing Allocation of Two Dimensional Irregular Shapes using an Agent Based Approach
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:61064", author = "Ramin Halavati and Saeed B. Shouraki and Mahdieh Noroozian and Saman H. Zadeh", title = "Optimizing Allocation of Two Dimensional Irregular Shapes using an Agent Based Approach", 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.", volume = "1", number = "11", pages = "552-4", }
