×

Adaptive beam search lookahead algorithms for the circular packing problem. (English) Zbl 1220.90103

Summary: This paper addresses the circular packing problem (CPP), which consists in packing \(n\) circles \(C_{i}\), each of known radius \(r_{i}, i\in N=\{1, \ldots , 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 \(C_{i}, i\in 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 \(\ell , \ell =1, \ldots , n\), of the beam search tree corresponds to a partial packing of \(\ell \) 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.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI

References:

[1] Akeb, A beam search based algorithm for the circular packing problem, Computers and Operations Research 36 pp 1513– (2009) · Zbl 1177.90330
[2] Birgin, Optimizing the packing of cylinders into a rectangular container, European Journal of Operational Research 160 pp 19– (2005) · Zbl 1067.90133
[3] Birgin, Minimizing the object dimensions in circle and sphere packing problems, Computers and Operations Research 35 pp 2357– (2008) · Zbl 1177.90332
[4] Castillo, Solving circle packing problems by global optimization, European Journal of Operational Research 191 pp 786– (2008)
[5] Hifi, A best-local position procedure-based heuristic for the two-dimensional layout problem, Studia Informatica Universalis 2 pp 33– (2002)
[6] Hifi, A dynamic adaptive local search based algorithm for the circular packing problem, European Journal of Operational Research 183 pp 1280– (2007) · Zbl 1135.90037
[7] Hifi, Adaptive and restarting techniques-based algorithms for circular packing problems, Computational Optimization and Applications 39 pp 17– (2008) · Zbl 1147.90390
[8] Huang, Greedy algorithms for packing unequal circles into a rectangular container, Journal of the Operational Research Society 56 pp 539– (2005) · Zbl 1095.90095
[9] Huang, New heuristics for packing unequal circles into a circular container, Computers and Operations Research 33 pp 2125– (2006) · Zbl 1086.90063
[10] Mladenović, Reformulation descent applied to circle packing problems, Computers and Operations Research 32 pp 2419– (2005) · Zbl 1066.90092
[11] Stoyan, Mathematical model and solution method of optimization problem of placement of rectangles and circles taking into account special constraints, International Transactions in Operational Research 5 pp 45– (1998) · Zbl 0910.90240 · doi:10.1016/S0969-6016(98)00003-3
[12] Sugihara, Disk packing for the estimation of the size of wire bundle, Japan Journal on Industrial and Applied Mathematics 21 pp 259– (2004) · Zbl 1126.52300
[13] Wang, An improved algorithm for the packing of unequal circles within a larger containing circle, European Journal of Operational Research 141 pp 440– (2002) · Zbl 1081.90593
[14] Wäscher, An improved typology of cutting and packing problems, European Journal of Operational Research 183 pp 1109– (2007) · Zbl 1278.90347
[15] Zhang, An effective hybrid algorithm for the problem of packing circles into a larger containing circle, Computers and Operations Research 32 pp 1941– (2005) · Zbl 1068.90095
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.