A heuristic for the circle packing problem with a variety of containers

A heuristic for the circle packing problem with a variety of containers

0.00 Avg rating0 Votes
Article ID: iaor20117322
Volume: 214
Issue: 3
Start Page Number: 512
End Page Number: 525
Publication Date: Nov 2011
Journal: European Journal of Operational Research
Authors: ,
Keywords: heuristics
Abstract:

In this paper we present a heuristic algorithm based on the formulation space search method to solve the circle packing problem. The circle packing problem is the problem of finding the maximum radius of a specified number of identical circles that can be fitted, without overlaps, into a two‐dimensional container of fixed size. In this paper we consider a variety of containers: the unit circle, unit square, rectangle, isosceles right‐angled triangle and semicircle. The problem is formulated as a nonlinear optimization problem involving both Cartesian and polar coordinate systems. Our heuristic improves on previous results based on formulation space search presented in the literature. For a number of the containers we improve on the best result previously known. Our heuristic is also a computationally effective approach (when balancing quality of result obtained against computation time required) when compared with other work presented in the literature. Formulation space search consists of switching between different formulations of the same problem, each formulation potentially having different properties in terms of nonlinear optimization. As a component of our heuristic we solve a nonlinear optimization problem using the solver SNOPT.

Reviews

Required fields are marked *. Your email address will not be published.