Beam search-based algorithms for the circular packing problem

Résumé En Fr

In this paper, we propose to solve the circular packing problem (CPP) whose objective is to pack n different circles C(i) of known radius r(i) , i = 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 the center of the circles C(i), i = 1, ..., n. This problem is solved by applying an adaptive algorithm that combines the beam search, the local position distance and the dichotomous search strategy. Decisions at each node of the developed tree are based on the well-known maximum hole degree that uses the local minimum distance. The computational results, on a set of instances taken from the literature, show the effectiveness of the proposed algorithms.

Dans cet article, nous étudions le problème de placement circulaire. On s'intéresse au placement de n pièces circulaires C(i) , i = 1, ..., n dans la plus petite surface circulaire C. Chacune des pièces est caractérisée par son rayon ri , sa surface ainsi que le nombre de répétitions. Le but est de déterminer le rayon r de C ainsi que les coordonnées (x(i) , y(i) ), i = 1, ..., n, des pièces circulaires C(i) placées. Nous proposons un algorithme adaptatif combinant la recherche par faisceaux, la distance inter-circulaire ainsi qu'une recherche dichotomique sur un intervalle bien spécifique. La méthode a été testée sur un ensemble d'instances de la littérature. Les résultats obtenus dominent les meilleurs résultats de littérature.