A heuristic simulated annealing algorithm for the circular packing problem

摘要

We study the circular packing problem (CPP) which consists of packing a set of circles of known radii into a larger containing circle without overlapping. The objective is to determine the smallest radius of the containing circle and the coordinates of the center of every packed circle. To solve CPP, we propose a heuristic simulated annealing (HSA) algorithm that incorporates heuristic neighborhood search mechanism and the gradient descent method into the simulated annealing procedure. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm and the gradient descent method can speed up searching the global optimal configuration. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithm.