The optimal packing of arbitrarily-shaped polygons using simulated annealing and polynomial-time cooling schedules Original Research Article

A common instance of geometric packing in manufacturing is the profile nesting problem which involves an optimum arrangement of shapes on a sheet of material in order to reduce material costs. The objectives of this paper are to demonstrate the effect of a polynomial-time cooling schedule on the computational performance of the algorithm, introduce variable penalty methods, implement an efficient overlap computation technique based upon existing methods and suggest generalized rules to construct move sets. The new approach has been validated against existing analytical results for packing circles in a square. The cases solved include the optimal packing of arbitrary simple polygons (including ‘interlocking shapes’) in a bounding rectangular area.