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 Ci, each of known radius ri, 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 (xi, yi) of each circle Ci. 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.