This content is not included in
your SAE MOBILUS subscription, or you are not logged in.
Simulated Annealing Applied to the Simultaneous Placement of Multiple Polygons
Technical Paper
2004-01-3272
ISSN: 0148-7191, e-ISSN: 2688-3627
Annotation ability available
Sector:
Language:
English
Abstract
This work deals with the problem of minimizing the waste of space of a placement of a set of two-dimensional objects inside a two-dimensional container. We address this problem with a heuristic approach based on simulated annealing, which is a probabilistic heuristic inspired on the physico-chemical processes that take place during the recrystalisation of a metal. We avoid the traditional “external penalisation” approach by applying the Minkowski sum algorithm from computational geometry to determinate collision-free regions inside the container to place an item. This gives a more universal character to the proposed algorithm, as external penalisation relies on arbitrary parameters that affect greatly the performance of the optimisation algorithm. Our algorithm is suited to non-convex items and non-convex containers, and it can be easily adapted to related problems, such as minimizing the dimensions of the container.
ABOUT THE AUTHOR - A short biographical section may be included to provide readers with background information and experiences of the main author. If desired, the presenting author may also include his/her mailing address and telephone number for future reference. This section is not to exceed 100 words and is applicable to presenting authors only.
Recommended Content
Authors
Citation
de Castro Martins, T. and de Sales Guerra Tsuzuki, M., "Simulated Annealing Applied to the Simultaneous Placement of Multiple Polygons," SAE Technical Paper 2004-01-3272, 2004, https://doi.org/10.4271/2004-01-3272.Also In
References
- Dowsland; K.A. Dowsland, W.B. Packing problems, in European J. Oper. Res 56 2 14 1992
- Daniels, K. Containment algorithms for nonconvex polygons with applications to layout Ph.D. thesis Harvard University Cambridge, MA 1995
- Kirkpatrick; S. Gelatt; C. Vecchi, M. Optimisation by Simulated Annealing Science n. 220 671 680 1983
- Agarwal; P. K. Flato; E. Halperin, D. Polygon Decomposition for Efficient Construction of Minkowski Sums European Symposium on Algorithms 20 31 2000