=Paper=
{{Paper
|id=Vol-1975/paper30
|storemode=property
|title=An Algorithm for Packing Circles of Two Types in a Fixed Size Container with Non-Euclidean Metric
|pdfUrl=https://ceur-ws.org/Vol-1975/paper30.pdf
|volume=Vol-1975
|authors=Anna Lempert,Alexander Kazakov,Quang Mung Le
|dblpUrl=https://dblp.org/rec/conf/aist/LempertKL17
}}
==An Algorithm for Packing Circles of Two Types in a Fixed Size Container with Non-Euclidean Metric==
https://ceur-ws.org/Vol-1975/paper30.pdf
An Algorithm for Packing Circles of Two Types
in a Fixed Size Container with Non-Euclidean
Metric
Alexander L. Kazakov1 , Anna A. Lempert1 , and Quang Mung Le2
1
Matrosov Institute for System Dynamics and Control Theory SB RAS, Irkutsk,
Russia,
{kazakov,lempert}@icc.ru,
2
Irkutsk National Research Technical University, Irkutsk, Russia,
quangmungle2010@gmail.com
Abstract. The paper deals with the problem of optimal packing of two
sets of circles (2-D spheres) into a simply connected container. The num-
ber of circles is given. The radii of these circles are equal within each set,
but, generally speaking, they differ between sets. There are two differ-
ent statements of a such problem. The simplest one is when the circles
of a larger radius are located first, and then smaller circles are packed
into the gaps. Solving of a such problem, in fact, reduces to a two-fold
solution of the equal circles packing problem. However, the procedure is
complicated by the fact that in the second solution the container will be
a multiply connected set. We consider a more complex formulation: it
is required to maximize the radii of the circles when their ratio is fixed.
The circle packing problem is usually studied in the case when the dis-
tance between points is Euclidean and even then belongs to the class of
NP-hard problems. We assume that the distance is determined by means
of some special metric, which, generally speaking, is not Euclidean. The
special numerical algorithm is suggested and implemented. It based on
optical-geometric approach, which is developed by the authors in recent
years and previously used only for packing circles of equal radius. The
results of computational experiment are presented and discussed.
Keywords: circle packing problem, unequal circles, non-Euclidean space,
numerical algorithm, computational experiment.
Introduction
Packing problems constitute a set of NP-hard optimization problems, which
appear in many fields of human activity such as industrial engineering, transport
and infrastructural logistics, circular cutting, computer science [5, 6]. The circle
packing problem has a long history, see [8, 16, 21]. The aim is to pack a certain
number of circles, each one with a maximal radius (not necessary the same for
each circle) inside a container. The shape of the container may be “simple” like
a circle, a square, a rectangular, or, for example, consists of combination of line
and arc segments.
In this paper we address the problem of packing two sets of circles in a
simply connected container. There are two approaches that have been used in
the literature. The first is an extension of the classical circle packing problem,
where we continue packing smaller circles in the empty rest of the container
after packing greater ones. Obviously, the density of the next package is always
greater in comparison with the previous one. It was F.L. Toth, who in 1958
considered this statement and proved that when the plane is filled with circles
of two different sizes, the gap space can not be less than 86.69% [25] (Chapter
6), [26].
The second approach is packing of circles with different sizes, when we fix
the relation of radii of the circles. This problem is more popular than the first
one and has been extensively considered in the literature.
Stoyan and Yaskov [20] present a mathematical model for the nonidentical
circles packing in the form of nonlinear global optimization problem and solve
it using a combination of branch-and-bound and the reduced gradient method.
The results of packing of 100 circles are shown.
Wang et al. [27] propose an approved algorithm – the quasi-physical quasi-
human algorithm, where the quasi-physical part is an analogy to the physical
model in which a number of smooth cylinders are packed inside a container and
a quasi-human strategy is then proposed to trigger a jump for a stuck object
in order to get out of local minima. Zhang and Deng [29] generalize the model
of [27] and use a hybrid approach consisting of simulated annealing to explore the
neighborhood of the current solution, and tabu search to implement the jumps.
Zeng et al. [28] propose the algorithm, which adapts the Tabu Search procedure
of Iterated Tabu Search algorithms and proposes a Tabu Search and Variable
Neighborhood Descent (TS-VND) procedure.
Pinter and Kampas [17] design numerical algorithms using Lipschitz Global
Optimizer (LGO) software. In [5] the authors apply various global optimization
techniques with a posteriori strategy that includes the rules of initial arrange-
ment and swapping all pairs of adjacent sized circles. Lopez and Beasley [13]
offer a heuristic algorithm that consist of optimization and improvement phases.
For the first phase the formulation space search method with a mixed Carte-
sian/Polar formulation is used, and for the second one a swapping process aim-
ing to improve the solution obtained in the first phase is suggested. In [14] FSS
algorithm for the problem of packing unequal circles inside a fixed size circular
container is presented. The survey of publications could be continued because
there are a lot of notable publications. Some record numerical results are avail-
able on www.packomania.com [19].
Note that the most of known results are obtained for the case when covered
areas or containers are subsets of the Euclidean plane or a multi-dimensional
Euclidean space. In the case of a non-Euclidean metric, covering and packing
problems are relatively poorly studied. Here we could mention the works by
Coxeter [7] and Boroczky [3], which deal with congruent circles packing problems
for multidimensional spaces of a constant curvature and McEliece and Rumsey
[15], who use the Hamming Metric. Besides above, this problem was studied in
a series of papers by Szirmai [22–24]. The circle packing problem with special
non-Euclidean metric in the case of equal circles was considered in [11].
In this paper, we expand a technique proposed in [9,10] for solving the prob-
lem of packing two sets of circles in a simply connected container when the
distance between two points is defined as minimal time of moving from one of
them to another. The suggested algorithm includes a random generation method
for determining the initial positions of the circles centers; an optical-geometrical
method based on the fundamental physical principles of Fermat and Huygens,
which makes it possible to use the non-Euclidean metric [9]; K-means method
for refinding the positions of the circles centers [1].
1 Formulation
Let X is a metric space, P is closed simply connected set, Ci are congruent
circles, si = (xi , yi ), are centers of Ci , i = 1, ..., n + m. Let first n circles have
radius R1 and other m have radius R2 = k1 R1 , k ∈ N. It is necessary to find
vector s = (s1 , ..., sn+m ) ∈ R2(n+m) , which provides the packing of the given
number of circles with maximum radius R1 (and R2 as well) in P .
The distance between the points of the space X is determined as follows [9]:
Z
dG
ρ(a, b) = min , (1)
G∈G(a,b) f (x, y)
G
where G(a, b) is the set of all continuous curves, which belong X and connect the
points a and b, 0 < α ≤ f (x, y) ≤ β is continuous function defined instantaneous
speed of movement at every point of P .
Thus, we formulate the following problem:
R1 → max (2)
1
R2 = R1 , k ∈ N (3)
k
ρ(si , sj ) ≥ 2R1 , ∀i, j = 1, n, i 6= j (4)
ρ(si , sj ) ≥ 2R2 , ∀i, j = n + 1, n + m, i 6= j (5)
ρ(si , sj ) ≥ R1 + R2 , ∀i = 1, n, ∀j = n + 1, n + m (6)
ρ(si , ∂P ) ≥ R1 , ∀i = 1, n (7)
ρ(sj , ∂P ) ≥ R2 , ∀j = n + 1, n + m (8)
si ∈ P, ∀i = 1, n + m (9)
Here ∂P is the boundary of the set P , ρ(si , ∂P ) is the distance from a point to
a closed set.
The objective, Eq. (2), maximizes the radius associated with the circles.
Eq. (3) fixes the ratio of radii. Inequalities (4)–(6) ensure that no circles overlap
each other. Inequalities (7)–(9) are the constraints which ensure that every circle
is fully inside the container.
Before we propose an algorithm, for any vector s define the sets
Pi = {p ∈ P : ρ(p, si ) ≤ αρ(p, sq ), i = 1, ..., n + m} , where (10)
1, i, q = 1, ..., n or i, q = n + 1, ..., n + m
α = k, i = n + 1, ..., n + m, q = 1, ..., n .
1
k , i = 1, ..., n, q = n + 1, ..., n + m
In the literature, if α ≡ 1 such sets are called Dirichlet cells [18] for points si on
n+m
S
the set P . It’s obvious that P = Pi .
i=1
2 Solution Method
In this section, the authors propose a heuristic method for solving problem
(2),(9), based on the analogy between the propagation of the light wave and
finding the minimum of the functional integral (1). This analogy is a consequence
of physical principles of Fermat and Huygens. The first principle says that the
light in its movement chooses the route that requires to spend a minimum of
time. The second one states that each point reached by the light wave, becomes
a secondary light source. This approach is described more detail in [9, 10, 12].
The essence of the algorithm is as follows.
At first, we consistently separate the given set P into segments with respect to
the randomly generated initial set of circles centers based on Voronoi diagrams.
It’s required to initiate synchronously the light waves from the points s̄i , i =
1, ..., n + m, and to find such points of P , which are simultaneously reached by
two or more waves.
At second, we find the center of packed circle with maximum radius for each
segment. It’s required to carried out the construction of the light wave front,
started from the border ∂Pi for each Pi to the time when the front degenerate
into a point.
Then we construct the segmentation for the new found centers.
Algorithm of Two Types Circles Packing
1. Randomly generate an initial solution s = (s1 , ..., sn+m ), which satisfies the
constraint (9). The radii R1 and R2 are assumed to be zero.
2. The set P is divided into subsets Pi , i = 1, ..., n + m, according to the
definition (10). To do this, we initiate light waves from points si by the
authors’ algorithm proposed in [9]. Note, that because of unequal radii we
have to deal with the “fast” and “slow” waves. It’s the main difference from [9].
3. For each Pi , i = 1, ..., n, find the point s̄i ∈ Pi that
ρ(s̄i , ∂Pi ) = max ρ(p, ∂Pi ).
p∈Pi
For this we initiate the light waves propagating from the boundary of ∂Pi of
every segment Pi in the inner area and construct the wave fronts until they
converge at a point:
(a) Boundary ∂Pi is approximated by the points Ak , k = 1, q.
(b) At each point Ak , we construct a tangent and a normal vector directed
to the interior of Pk . Then postponing along the normal vector a segment
of length f (Ak )∆t, we obtain the points Bk of the new wave front. Here
∆t is time step.
(c) The Bezier curve is constructed using the points Bk .
Steps (a)–(c) are being carried out until the constructed front becomes
a nonclosed line or a point.
If the constructed front is nonclosed line, then the solution is the “middle”
of the line, namely the point the distance from which to the ends of line
is the same.
If the constructed front consists of one point, then this point is the
solution.
As a result, for each Pi , i = 1, ..., n+m, we find the coordinates of the packed
circle center s̄i and its maximum radius ri .
4. Calculate R1 = min ri and R2 = min ri .
i=1,...,n i=n+1,...,n+m
Steps 2-4 are repeated until the R1 (and R2 as well) increases, then vector
s̄ is memorized as a current solution of the problem (2)–(9) if it is greater
than the maximum value of the previously found radii.
5. The counter of an initial solution generations Iter is incremented. If Iter
becomes equal some preassigned value, then the algorithm is terminated.
Otherwise, go to step 1.
3 Numerical Experiment
Testing of the algorithm proposed in the previous section was carried out using
the PC of the following configuration: Intel (R) Core i7-5500U (2.4 GHz, 8 GB
RAM) and Windows 10 operating system. The algorithm is implemented in C#
using the Visual Studio 2013.
Example 1. This example illustrates how the proposed in the previous section
algorithm works in the case of the Euclidean metric f (x, y) ≡ 1. Here the radius
of large circles is twice the radius of small ones. The number of circles is given and
we maximize the radius. The number of random generations of initial positions is
five. Fig. 1 shows the best solutions in Table 1. Here and further n is a number
of large circles, m is a number of small circles, R is the best radius of large
circles, D is density of packing, Reql and Deql is the radius of equal circles and
density respectively given in [19], t is time of calculation. It is easy to see that
the problem has an infinite set of solutions that can be obtained from the one
shown in the fig. 1 using the rotation operator.
Here we can see that the radii of the big circles are expected to be greater
than in the case of equal circles. As for the density, we can say that it is, as a rule,
Fig. 1. Computational results for packing of an unit circle
smaller than for equal circles. This is due to the presence of a strict condition
on the ratio of radii (3). But for several cases (for example, 3 big and 3 small
circles) density becomes grater than for equal circles, because small circles fill in
the gaps left after packing big ones.
Example 2. This example considers the case when the metric is given by the
formula (1), where f (x, y) = υ0 (1 + ky), υ0 , k are given constants (here υ0 =
1, k = 0.1). This means that the speed of wave propagation increases linearly
with the coordinate y. Borovskikh [4] proved that in this case the wave fronts
also have the form of a circle, as in the Euclidean metric, but the source of the
wave (the center of the circle) is displaced. Note that the circles located lower
(see fig. 2) visually seem to be grater, however they have the same radii. Bold line
shows circles of smaller radius. The computational domain has a size of 100x100
cu. Recall that the radius (R) here means the time of moving from center to the
boundary of the circle. The computational results are presented in Table 2.
Table 1. Computational results for packing of an unit circle
nm R D(%) Cordinates of centers Cordinates of centers Reql Deql
of big circles of small circles %
1 1 0,66018 54,74844 (0,84;1,30) (1,56;0,62) 0,500 50,00
1 2 0,62830 60,50988 (1,32;1,36) (0,92;0,46) (0,46;0,92) 0,464 64,62
1 3 0,60198 64,42109 (0,78;0,90) (1,66;1,40) (1,70;0,78) 0,414 68,63
(1,08;1,78)
1 4 0,56407 64,58853 (0,68;1,10) (1,70;0,80) (1,20;1,80) 0,370 68,63
(1,68;1,44)(1,24;0,42)
2 1 0,48100 53,77443 (0,74;1,46)(1,38;0,70) (0,56;0,62) 0,464 64,62
2 2 0,48100 58,50056 (0,70;0,80)(1,42;1,46) (0,64;1,66)(1,52;0,54) 0,414 68,63
2 3 0,48100 63,70911 (0,60;1,10)(1,58;0,98) (0,94;0,40)(1,48;1,68) 0,370 68,52
(0,94;1,82)
2 4 0,476308 66,00437 (1,54;1,34)(0,64;0,90) (0,56;1,64)(1,04;1,86) 0,333 66,67
(1,66;0,62) (1,24;0,38)
3 1 0,43833 63,43109 (1,62;0,98)(0,98;1,62) (0,36;1,30) 0,414 68,63
(0,74;0,70)
3 2 0,43833 67,34427 (0,64;0,78)(1,54;0,78) (0,42;1,46) (1,78;1,44) 0,370 68,52
(1,10;1,64)
3 3 0,42208 68,28399 (1,18;1,62)(0,6;0,94) (0,50;1,60) (0,92;0,34) 0,333 66,67
(1,48;0,72) (1,82;1,36)
3 4 0,42027 68,40442 (0,58;0,88)(1,44;0,68) (1,88;1,14) (0,88;0,34) 0,333 77,77
(1,04;1,64) (1,70;1,58)(0,42;1,48)
4 1 0,38032 62,82039 (1,46;1,56) (0,68;0,66) (1,08;1,10) 0,370 68,52
(1,58;0,76) (0,62;1,46)
4 2 0,380261 66,21092 (1,68;0,98) (1,04;0,52) (1,08;1,10)(0,44;0,66) 0,333 66,67
(1,24;1,68)(0,52;1,28)
4 3 0,36819 65,03290 (0,76;0,60) (1,42;1,58) (1,88;1,24) (0,32;0,96) 0,333 77,77
(1,56;0,72) (0,64;1,48) (1,08;1,10)
4 4 0,360414 66,75409 (0,88;0,54) (1,22;1,70) (1,08;1,12) (0,34;0,82) 0,303 73,25
(1,68;0,94) (0,56;1,36) (1,44;0,38)(1,98;1,52)
Example 3. Here we construct f (x, y) by following rule.
(x−2.5)2 +(y−2.5)2 0, a1 (x, y) ≥ 0.8,
a1 (x, y) = 1+(x−2.5)2 +(y−2.5)2 , f1 (x, y) =
a1 (x, y),
2
(x−2.5) +(y−7.5) 2 0, a2 (x, y) ≥ 0.8,
a2 (x, y) = 1+(x−2.5) 2
+(y−7.5)2
, f2 (x, y) =
a2 (x, y),
2
(x−7.5) +(y−2.5) 2 0, a3 (x, y) ≥ 0.8,
a2 (x, y) = 1+(x−7.5) 2
+(y−2.5)2
, f3 (x, y) =
a3 (x, y),
2
(x−7.5) +(y−7.5) 2 0, a4 (x, y) ≥ 0.8,
a3 (x, y) = 1+(x−7.5) 2
+(y−7.5)2
, f4 (x, y) =
a4 (x, y),
F (x, y) = f1 (x, y) + f2 (x, y) + f3 (x, y) + f4 (x, y),
0.4, 0 < F (x, y) ≤ 0.4,
f (x, y) = F (x, y),
0.8, F (x, y) = 0.
Fig. 2. Computational results for packing in convex polygon with linear metric
Such metrics are used in infrastructure logistics if one needs to locate several
facilities on a hilly country or in the field of security [2]. Here speed of movement
depends on the angle of ascent or descent. Therefore the wave fronts are strongly
distorted.
The container in this case is a non-convex polygon. Radius of large circles is
3 times larger than the radius of small ones.
Fig. 3 shows the solutions associated with Table 3 in the case where the form
of the wave fronts is unknown.
Note that, as in the previous example, in the given metric presented on Fig. 3
the thin “circles” have the same radius R and the bold “circles” have the radius
R/3.
Tables 2 and 3 confirm the obvious fact: when the number of large circles does
not change, the best radii decrease with increasing the number of small circles.
However, the packing density does not depend on the change in the number
of small circles and it wasn’t evident. Note, that the total time for solving the
problem is relatively small.
Table 2. Computational results for packing in convex polygon with linear metric
n m R D(%) t(min)
1 1 5,71273 72,15879 3,54
1 2 4,93006 55,73511 4,1
1 3 4,66858 63,09503 5,5
2 1 4,00897 63,04233 6,54
2 2 3,91279 56,01616 8,25
2 3 3,68772 60,00351 9,25
3 1 3,33333 60,47042 10,54
3 2 3,27838 61,83032 14,10
3 3 3,14662 59,31846 16,49
Table 3. Computational results for packing in non-convex polygon
n m R D(%) t(min)
1 1 59,80078 56,76873 1,23
1 2 51,64214 47,77585 4,07
1 3 51,33696 54,74681 2,31
2 1 39,07394 46,58194 4,37
2 2 39,07394 48,10322 5,13
2 3 38,83765 54,43867 6,04
3 1 34,57107 56,38359 8,42
3 2 34,31981 59,09874 8,22
3 3 34,31981 64,58694 10,27
4 Conclusion
Optimal packing and covering problems are known to be a particular class of
clasterization problems, as all points inside a circle enjoy the same obvious prop-
erty: they are closer to the center of the respective circle, compared to the centers
of the other circles in the covering. In other words, each a circle can be regarded
as a cluster, described by its center and radius.
In this paper, we address a problem of optimal packing of two sets of circles
(2-D spheres) into a simply connected container. The cardinality of these sets is
prescribed, and the ratio of radii of circles of two collections is assumed to be
fixed. The goal is to maximize the radii of the packed circles. In this formulation,
the problem is rather complicated and, even if all the radii are equal to each
other, belongs to the class of NP-hard problems.
We operate with a specific, not necessary Euclidean, distance function. The
feature of this metric, arising in certain practical problems of logistics, is as
follows: the physical distance is replaced by the time, required for reaching one
point from another.
In our previous work [11], a computational algorithm was developed for opti-
mal packing of circles with equal radii, based on an “optical-geometric approach”.
Here a modification of this approach is proposed to take into account the fea-
Fig. 3. Computational results for packing in non-convex polygon
tures of the general problem. The approach employs a rather simple idea: circles
are regarded as certain wave fronts; the smaller radius of a circle – the slower the
wave’s expansion. Note that a practical implementation of this idea occurred to
be quite technically laborious. Nevertheless, we managed to elaborate an efficient
software implementation of the proposed algorithm.
A series of test cases for both Euclidean and a specific non-Euclidean metrics
is implemented and analyzed. The results prove the applicability of the proposed
approach.
Future efforts in this direction can be connected both with application to
problems of logistics (for example, simultaneous placement of logistic centers of
two types), and with a further extension of the mathematical formulation, for
example, towards increasing a number of sets of packed circles with different
radii.
Acknowledgements. The reported study was particulary funded by Russian
Foundation of Basic Research according to the research projects No. 16-31-00356
and No. 16-06-00464.
References
1. Anil, K., Richard, C.: Algorithms for clustering data. New Jersy: Prentice Hall
(1988)
2. Bashurov, V., Filimonenkova, T.: Matematicheskie modeli bezopasnosti (in Rus-
sian). Nauka, Novosibirsk (2009)
3. Boroczky, K.: Packing of spheres in spaces of constant curvature. Acta Mathemat-
ica Academiae Scientiarum Hungarica 32(3), 243–261 (1978)
4. Borovskikh, A.: The two-dimensional eikonal equation. Siberian Mathematical
Journal 47(2), 813–834 (2006)
5. Castilo, I., Kampas, F., Pinter, J.: Solving circle packing problems by global opti-
mization: Numerical results and industrial applications. European Journal of Op-
erational Research 191(3), 786–802 (2008)
6. Conway, J., Sloane, N.: Sphere Packing. Lattices and Groups. Springer science and
Business Media, New York (1999)
7. Coxeter, H.S.M.: Arrangements of equal spheres in non-euclidean spaces. Acta
Mathematica Academiae Scientiarum Hungarica 5(3), 263–274 (1954)
8. Hifi, M., M’Hallah, R.: A literature review on circle and sphere packing problems:
Models and methodologies. Advances in Operations Research 2009, 1–22 (2009)
9. Kazakov, A., Lempert, A.: An approach to optimization in transport logistics.
Automation and Remote Control 72(7), 1398–1404 (2011)
10. Kazakov, A., Lempert, A.: On mathematical models for optimization problem of
logistics infrastructure. International Journal of Artificial Intelligence 13(1), 200–
210 (2015)
11. Kazakov, A., Lempert, A., Nguyen, H.: The problem of the optimal packing of the
equal circles for special non-euclidean metric. Communications in Computer and
Information Science 661, 25–68 (2017)
12. Lempert, A., Kazakov, A., Bukharov, D.: Mathematical model and program system
for solving a problem of logistic object placement. Automation and Remote Control
76(8), 1463–1470 (2015)
13. Lopez, C., Beasley, J.: Packing unequal circles using formulation space search.
Computers and Operations Research 40(5), 1276–1288 (2013)
14. Lopez, C., Beasley, J.: A formulation space search heuristic for packing unequal
circles in a fixed size circular container. European Journal of Operational Research
251(1), 64–73 (2016)
15. McEliece, R., Rumsey, H.: Sphere-packing in the hamming metric. Bull. American
Math. Soc. 75, 32–34 (1969)
16. Peikert, R., Wiirtz, M., Monagan, C., Groot, C.: Packing circles in a square: A
review and new results. System Modelling and Optimization. Lecture Notes in
Control and Information Sciences 180, 45–54 (1992)
17. Pinter, J., Kampas, F.: Nonlinear optimization in mathematica with math opti-
mizer professional. Mathematician Education and Research 10(2), 1–18 (2005)
18. Preparata, F., Shamos, M.: Computational Geometry. An Introduction. Springer-
Verlag, New York (1985)
19. Specht, E.: Packomania. http://www.packomania.com/, accessed: 2015-10-28
20. Stoyan, Y., Yaskov, G.: Mathematical model and solution method of optimization
problem of placement of rectangles and circles taking into account special con-
straints. International Transactions in Operational Research 5(1), 45–57 (1998)
21. Szabo, P., Markot, M., Csendes, T., Specht, E., Casado, L.: New approaches to
circle packing in square with program codes. Springer US, New York (2007)
22. Szirmai, J.: The optimal ball and horoball packings of the coxeter tilings in the
hyperbolic 3-space. Beitr. Algebra Geom. 46(2), 545–558 (2005)
23. Szirmai, J.: The optimal ball and horoball packings to the coxeter honeycombs in
the hyperbolic d-space. Beitr. Algebra Geom. 48(1), 35–47 (2007)
24. Szirmai, J.: A candidate for the densest packing with equal balls in thurston ge-
ometries. Beitr. Algebra Geom. 55(2), 441–452 (2014)
25. Toth, F.: Lagerungen in der ebene auf der kugel und im raum (in German).
Springer-Velag, Berlin (1985)
26. Toth, F.: Densest packing of translates of the union of two circles. Discrete and
Computational Geometry 1, 307–314 (1986)
27. Wang, H., Huang, W., Zhang, Q., Xu, D.: An improved algorithm for the packing of
unequal circles within a larger containing circle. European Journal of Operational
Research 141(2), 440–453 (2002)
28. Zeng, Z., Yu, X., He, K., Huang, W., Fu, Z.: Iterated tabu search and variable
neighborhood descent for packing unequal circles into a circular container. Euro-
pean Journal of Operational Research 250(2), 615–627 (2016)
29. Zhang, D., Deng, A.: An effective hybrid algorithm for the problem of packing
circles into a larger containing circle. Computers & Operations Research 32(8),
1941–1951 (2005)