A Non-Oscillating Beam-Search with a Look-ahead for the Circular Packing Problem

摘要

This paper addresses the circular packing problem (CPP) which consists in packing n circles C_i, each of known radius r_i, i∈ N={1,...,n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of each circle C_i. This problem is solved via a binary search that evaluates the solution using a non-oscillating beam search with separate beams (instead of pooled ones). This beam search guarantees a monotonic decrease of r as the beam width increases. A node of level l of the beam search tree represents a partial packing of l circles into C. The potential of each node of the tree is assessed via a look-ahead strategy. The computational results on different benchmark instances show the effectiveness of the algorithm.