Adaptive beam search lookahead algorithms for the circular packing problem |
| |
Authors: | Hakim Akeb Mhand Hifi Rym M'Hallah |
| |
Affiliation: | 1. ISC Paris, Institut Supérieur du Commerce, 22 boulevard du Fort de Vaux, 75017 Paris, FranceE‐mail: hakim.akeb@u‐picardie.fr;2. Université de Picardie Jules Verne, UFR des Sciences, MIS Axe Optimization Discrète et Réoptimisation, 5 rue du Moulin Neuf, 80000 Amiens, FranceEmail: hifi@u‐picardie.fr;3. Department of Statistics and Operations Research, Kuwait University, PO Box 5969, Safat 13060, Kuwait.Email: mhallah@kuc01.kuniv.edu.kw |
| |
Abstract: | 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 the center of Ci, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms. |
| |
Keywords: | beam search binary search circular packing lookahead strategy maximum hole degree |
|
|