An application of Hooke and Jeeves Method as a Constructive Heuristic for the Ellipse Packing Problem

Abstract

Cutting and packing problems appear in many industrial applications, such as textile, automotive, transportation, etc.. This paper presents a constructive heuristic developed for cutting and packing problems, restricted to the case where a number of non-identical ellipses in an irregular polygon. This problem is related to the gem cut from crude material. The 3D Gems technology proposed in [1] aims to maximize the volumetric use of the gem, taking into account the final market value expected, respecting the industrial standards. The optimization of the ellipses inside the polygon is performed by the Hooke e Jeeves method [2], [3]. Packed ellipses are tangent to the vertexes of a master ellipse, initially positioned at the center of the polygon. Superposition restrictions are imposed and checked at each stage. R2 transformations are applied, which raise parametric ellipse equations. Results illustrate that the proposed heuristic can be applied to polygons with varying shapes, either convex or concave, due to the type of search which is performed in the interior of the polygon. The constructive heuristic was able to find the optimal solutions for the polygons tested.