Simulated Annealing Applied to the Simultaneous Placement of Multiple Polygons 2004-01-3272

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.