A Heuristic Algorithm for the Unequal Circle Packing Problem

Circle packing problem, one of the NP hard problems, is of great theoretical and practical value. To solve the circle packing problem that encounters in the field of transportation of freight, a heuristic algorithm is proposed for finding a good arrangement of multiple different-sized circles within a larger rectangular container. In this algorithm, the circles are sorted by non-increasing order of radius and packed into the container one by one according to the order. Each circle should be placed inside the container by a corner placement so that the circle does not overlap any other circle and is tangent with two previously packed circles. By pseudo-placing one or more circles to be packed, two greedy methods are introduced to evaluate the benefit of a corner placement, one of which is the degree of placement, and the other is a bounded enumeration strategy that is based on the first one. At each iteration of packing in the resulting algorithm, each circle is packed into the container by a corner placementwith the highest benefit according to the bounded enumeration strategy. The experimental results are presented, showing the effectiveness of this algorithm.