A new approach to packing non-convex polygons using the no fit polygon and meta-heuristic and evolutionary algorithms

Citation

Burke E & Kendall G (2002) A new approach to packing non-convex polygons using the no fit polygon and meta-heuristic and evolutionary algorithms. In: Parmee I (ed.) Adaptive Computing in Design and Manufacture V. London: Springer, pp. 193-204. http://link.springer.com/chapter/10.1007%2F978-0-85729-345-9_17; https://doi.org/10.1007/978-0-85729-345-9_17

Abstract
Earlier work by the authors has presented a method for packing convex polygons, using a construction known as the no fit polygon. Although the method was shown to be successful, it could only deal with convex polygons. This paper addresses the issue by showing how a non-convex, no fit polygon algorithm can (and should) produce better quality solutions. We demonstrate the approach on two test problems that the authors have used in previous work. The new algorithm does, however, have an increased computational complexity. We tackle this by presenting an algorithm that allows the non-convex, no fit polygon to be approximated. This means that much more of the search space can be considered and computational results show that better quality solutions can be achieved, in less time than when using the full no fit polygon algorithm.