=Paper=
{{Paper
|id=Vol-1839/MIT2016-p30
|storemode=property
|title= Congruent circles packing and covering problems for multi-connected domains with non-Euclidean metric, and their applications to logistics
|pdfUrl=https://ceur-ws.org/Vol-1839/MIT2016-p30.pdf
|volume=Vol-1839
|authors=Alexander Kazakov,Anna Lempert,Pavel Lebedev
}}
== Congruent circles packing and covering problems for multi-connected domains with non-Euclidean metric, and their applications to logistics==
https://ceur-ws.org/Vol-1839/MIT2016-p30.pdf
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
Congruent Circles Packing and Covering
Problems for Multi-Connected Domains with
Non-Euclidean Metric, and Their Applications to
Logistics
1 1 2
Alexander Kazakov , Anna Lempert , and Pavel Lebedev
1
Matrosov Institute for System Dynamics and Control Theory SB RAS,
Lermontov str., 134, 664033 Irkutsk, Russia
{kazakov,lempert}@icc.ru,
2
Krasovskii Institute of Mathematics and Mechanics of UB RAS,
S. Kovalevskaja st., 16, 620219 Ekaterinburg, Russia
pleb@yandex.ru
Abstract. The article is devoted to optimal covering and packing prob-
lems for a bounded set in a two-dimensional metric space with a given
amount of congruous circles. Such problems are of both theoretical in-
terest and practical relevance. For instance, such statements appear in
logistics when one needs to locate a given number of commercial or social
facilities. A numerical algorithm based on fundamental physical princip-
les due to Fermat and Huygens is suggested and implemented. It allows us
to solve the problems for the cases of non-convex sets and non-Euclidean
metrics. The results of numerical experiments are presented and dis-
cussed. Calculations show the applicability of the proposed approach its
high e ciency for covering of a convex set in the Euclidean space by a
su ciently large amount of circles.
Keywords: circles covering problem, circles packing problem, non-Eucli-
dean metric, optical-geometric approach, logistics, facilities, numerical
algorithm, computational experiment.
1 Introduction
The facility location problem is a branch of mathematical modeling concerned
with the optimal placement of facilities to minimize various negative factors.
The Supply Chain Management Terms and Glossary de nes facilities as An
installation, contrivance, or other thing which facilitates something; a place for
doing something: Commercial or institutional buildings, including o ces, plants
and warehouses. There is a number of papers devoted to the problem, see e.g.
[11, 12, 37]. However, the known publications are usually concerned with certain
particular cases. At the same time, we are aimed at a systemic solution of this
problem at the level of regional, national and international transport and logistics
systems (TLS).
334
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
In connection with the above, we develop a multi-stage technology for study-
ing complex systems. On the rst stage, we solve the problem of optimal place-
ment of infrastructure logistic facilities, assumed the absence of these objects
in the considered region. For example, there may be cellular towers of a certain
operator, ATMs of particular bank, etc. This problem is reduced to special mod-
i cations of two well-known mathematical problems: covering of a bounded set
in a two-dimensional space with non-Euclidean metric by equal circles. On the
second stage, we solve the problem of optimal placement of additional logistics
facilities in terms of cooperation and competition. The third stage assumes de-
signing of a proper communication system for the above de ned objects. On the
nal stage, we treat the problem of communications' support in order to keep
them in satisfactory conditions. Note that, though the developed approach op-
erates with a variety of mathematical models, the key part is played by covering
and packing problems.
The covering problem is to locate congruent geometric objects in a metric
space so that its given area lies entirely within their union. This theoretical
problem is widely used in solving practical tasks in various elds of human
activity. Examples of such tasks are placement of cell towers, rescue points,
police stations, ATMs, hospitals, schools [4, 7, 12, 15], designing energy-e cient
monitoring of distributed objects by wireless sensor networks [2, 8, 13, 14] etc.
Algorithms for covering of simply connected sets by congruent circles employing
quasi-dierentiability of the objective function are presented in [18], heuristic and
metaheuristic methods can be found in [1, 3, 28, 38], algorithms of integer and
continuous optimization are proposed by [27, 29, 30]. A modi cation of feasible
directions' method appears in [32], where optimal coverings are given for dierent
n ≤ 100.
The optimal circle packing problem is to place objects of a prescribed form
in a given container. Apparently, the most popular statement here is optimal
packing two-dimensional spheres (circles, discs) in a convex set. For example,
the authors of [9, 26, 33] consider the following problem: maximize the radius of
a given number n of congruent circles packed in a unit square. The number of
circles varies between 1 and 200. Papers [16,17,25] address the problem of packing
a family of equal circles of unit radius in a great circle. The results for number
of packing elements up to 81 are obtained. Birgin and Gentil [5] consider the
problem of packing equal circles of unit radius in a variety of containers (circles,
squares, rectangles, equilateral triangles and strips of xed height) in order to
minimize the size of the latter.
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 [10] and Boroczky [6], which deal with congruent circles packing prob-
lems for multidimensional spaces of a constant curvature (elliptic and hyperbolic
cases) and assess the maximum packing density. Besides above, this problem was
studied in a series of papers by Szirmai. In [34, 35] we nd a method to deter-
335
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
mine the data and the density of certain optimal ball and horoball packings
with Coxeter tiling for hyperbolic 3-, 4- and 5-D spaces, based on a projective
interpretation of hyperbolic geometry. The goal of [36] is to extend the problem
of nding the densest geodesic ball (or sphere) packing to dierent 3-D homo-
geneous geometries.
A detailed description of the proposed research technology for transport and
logistics systems (including the developed software) is the subject of an extra
publication. In the present paper, we are focused on mathematical modeling
and their numerical implementation. The study follows our previous works on
mathematical apparatus for problems of domestic logistics. In particular, in [19
23] we elaborate numerical algorithms based on optical-geometric analogy.
2 Mathematical models
Assume we are given a bounded domain containing a collection of disjoint pro-
hibited areas, i.e. subdomains, where any activity (including passing through
them) is banned. Suppose, the number of consumers is large enough, so that we
can regard them as continuously distributed over the domain.
It is required to locate a given number of logistic centers so that, at rst,
they can serve the maximum possible proportion of the domain, at second, their
service areas do not overlap, and, nally, the maximum time of delivery to the
mostly distant consumer coincides for all logistics centers.
A mathematical model of the logistic problem is as follows.
Assume we are given a metric space X , a bounded domain D ⊂ X , compact
sets Bk ⊂ D, k = 1, ..., m (prohibited domains), and n of logistic centers Sn =
{si } with coordinates si = (xi , yi ), i = 1, ..., n. Let 0 ≤ f (x, y) ≤ β be a
continuous function, which makes sense of the instantaneous speed of movement
at every point of D . Note that f (x, y) = 0 ⇔ (x, y) ∈ Bk , k = 1, ..., m. Then,
instead of D , we can consider closed multiply-connected set P :
m
!
[
P = cl D \ Bk ⊂ X ⊆ R2 . (1)
k=1
Here cl is the closure operator.
The distance in space X is determined as follows:
Z
dΓ
ρ(a, b) = min , (2)
Γ ∈G(a,b) f (x, y)
Γ
where G(a, b) is the set of all continuous curves, which belong to X and connect
the points a and b. In other words, the shortest route between two points is a
curve, that requires to spend the least time.
∗ ∗
We are to nd a location Sn = {si }, which brings maximum to the expression
ρ (si , (Sn \{si }))
R∗ = min min , ρ(si , ∂P ) . (3)
i=1,n 2
336
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
Here, ∂P is the boundary of the set P and ρ(si , ∂P ) is the distance from a point
to a closed set,
ρ(si , ∂P ) = min ρ(si , x) . (4)
x∈∂P
One can reformulate (3) as follows: maximize the radius of equal circles, which
can be located so that they overlap each other and the boundary of the set P
only at their boundary points. In other words, a solution to the logistic problem
is equivalent to an optimal packing circles of equal radius in a multiply-connected
set with metric (2).
Along with (3), we consider another problem: place a predetermined number
of logistic centers so that, at rst, all consumers are serviced, secondly, the
maximum time of delivery to the mostly distant consumer is the same for all
logistic centers, and the time of delivery is minimal.
Let M ⊂ X be a given bounded set with continuous boundary, m be an
amount of logistic centers Pm = {Ok }, and Ok = (xk , yk ), k = 1, ..., m, be their
coordinates.
Our second goal is to nd a partition of M on m segments Mk , k = 1, ..., m,
∗ ∗
and the location of the centers Pm = {Ok }, which provide minimum for
R∗ = max ρ (Ok , ∂Mk ) . (5)
k=1,m
The formulated logistic problem is equivalent to optimal covering of the set M
with the metric (2) by circles of equal radia.
3 Numerical methods
In this section, the authors propose methods for solving problems (2),(3) and
(2),(5), based on the analogy between the propagation of the light wave and
nding the minimum of the functional integral (2). This analogy is a consequence
of physical laws of Fermat and Huygens. The rst 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 [19, 20, 22, 23].
The essence of the algorithm is as follows. We consistently divide the given
set (P or M ) into segments with respect to the randomly generated initial set of
circles centers based on Voronoi diagrams; then nd the best center covering or
packaging circle for each segment; nally construct segmentation for the found
centers.
An algorithm for circles covering constructing
1. Randomly generate an initial coordinates of the circles centers Ok , k = 1, m.
Coordinate coincidences are not allowed.
2. From Ok , k = 1, m we initiate the light waves using the algorithm [19]. It
allows us to divide set M on m segments Mk and to nd their boundaries
∂Mk , k = 1, m.
337
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
3. Boundary ∂Mk of segment Mk is approximated by the closed polygonal line
with nodes at the points Ai , i = 1, q .
4. From Ai , i = 1, q we initiate the light waves using the algorithm [19] as well.
5. Every point (x, y) ∈ Mk , rst reached by one of the light waves is marked
(here and further we assume using an analytical grid for x and y ). We mem-
orize time T (x, y) which is required to reach (x, y).
6. Find Ōk = arg max T (x, y). Then, the minimum radius of circle which covers
(x,y)∈Mk
Mk , is given by
Rk min = max ρ(Ōk , Ai ) .
i=1,q
Steps 36 are carried out independently for each segment Mk , k = 1, m.
7. Find Rmin = max Rk min . Then go to step 2 with Ok = Ōk , k = 1, m.
k=1,..m
Steps 27 are being carried out while Rmin is decreasing, then the current
covering
m
[
Pm = Ck (Ōk , Rmin )
k=1
is memorized as a solution.
8. The counter of an initial coordinates generations Iter is incremented. If Iter
becomes equal some preassigned value, then the algorithm is terminated.
Otherwise, go to step 1.
An algorithm for circles packing constructing
1. Randomly generate an initial coordinates of the circles centers si , si ∈ P ,
i = 1, n. Radius R is assumed to be zero.
2. Domain P is divided on segments Pi , i = 1, ..., n, as well as in the algorithm
above.
3. 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 until they
converge at a point. Denote this point by s̄i and calculate ri = ρ(s¯i , ∂Pi ) by
(4), i = 1, n.
4. Calculate R = min ri .
i=1,...,n
Steps 2-4 are being carried out until R is increasing, then the current vector
S̄n = {s̄i } is memorized as a solution.
5. The counter of an initial coordinates generations Iter is incremented. If Iter
becomes equal some preassigned value, then the algorithm is terminated.
Otherwise, go to step 1.
4 Computational experiment
Example 1. This example illustrates algorithm for circles covering constructing
in the case of the Euclidean metric f (x, y) ≡ 1. We solve the equal circle covering
problem in unit square. The number of circles is given and we maximize the
338
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
radius. The results are presented in table 1. Here Rmin is the best radius of
covering obtained by the presented algorithm for circles packing constructing,
∆R = RKnown − Rmin , t is time of calculation, Iter = 25.
Note, that the RKnown results were obtained from [31].
Table 1. Comparison of the results of covering equal of circles in the unit square
n RKnown Rmin ∆R t(sec)
10 0.218233512793 0.218233693441 0.000000180648 43.477
15 0.179661759933 0.180281054179 0.000619294246 47.611
20 0.152246811233 0.152426892598 0.000180081365 51.683
25 0.133548706561 0.134470667521 0.000921960960 54.835
30 0.122036868819 0.123001449585 0.000964580766 58.984
40 0.108376286825 67.221
50 0.095904051463 73.508
75 0.078877824148 88.141
100 0.068332659403 128.342
150 0.05554107666 144.831
500 0.03082452774 408.707
Blank lines in table 1 means no known results for the corresponding n. It is
easily seen that in comparison with known results, the results obtained by the
authors, a little bit worse, but the deviation of circles radius does not exceed
0.1%. The total time for solving the problem is relatively small even for n = 500.
It can be concluded that the proposed algorithm, despite the fact that it is,
strictly speaking, not directly suitable for the covering problem in the Euclidean
metric, shows reasonably good results here.
Example 2. This example shows a comparison of the results of the authors with
the results from [24] and [31] for the packing of equal of circles in the unit square
in the Euclidean metric f (x, y) ≡ 1 (table 2).
It is easy to see that, as in example 1, the results obtained by the authors,
is slightly worse, but the deviation of radius of packed circles from the optimal
is low. Furthermore, when n = 1, 500 we found a solution which improves the
known one. At the same time, the total time for solving the problem is relatively
small even for n = 3000 (for example, compared with the FSS-algorithm [24]).
Example 3. Let now M = {(x, y): (x − 6)2 + (y − 6)2 ≤ 42 } and
(x − 4.5)2 + (y − 6)2
f (x, y) = + 0.5.
(x − 4.5)2 + (y − 6)2 ) + 1
∗
It is required to nd the covering Pn with minimal radius R and n = 8.
The resulting approximation of coordinate of covering circles centers is fol-
lowing
S8 ≈ {(3.610, 4.375), (3.725, 7.750), (5.603, 9.748), (6.0, 8.745) ,
339
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
Table 2. Comparison of the results of packing equal of circles in the unit square
n Packomania FSS-Algorithm Proposed Algorithm
RKnown Rmax ∆R t Rmax ∆R t
50 0,071377104 0,071376623 0,000000481 276 0,070578606 0,000798498 88
75 0,058494535 0,058091304 0,000403232 621 0,057954653 0,000539883 217
100 0,051401072 0,051272763 0,000128308 1317 0,050269024 0,001132048 376
150 0,042145465 0,041976579 0,000168887 4107 0,041309389 0,000836076 895
200 0,036612799 0,025722283 0,010890516 8790 0,035969127 0,000643672 1457
250 0,032876318 0,030028915 0,002847403 18111 0,032102759 0,000773559 2246
300 0,030219556 0,029447787 0,000771768 3254
500 0,023455498 0,000974943 0,022480556 133443 0,022846434 0,000609065 8725
1500 0,013157896 0,013163195 -0,000005299 31713
3000 0,009674511 0,009243172 0,000431339 217489
(6.115, 7.125), (6.918, 3.375), (7.628, 8.875), (9.156, 6.0)} .
∗
Radius Rmin ≈ 1.8134. Set M (bold line), covering P8 (thin line) and coor-
dinates of circles centers S8 (dots) are shown at g. 1.
Example 4. Here set M and function f (x, y) are the same as in the example 3.
∗
It is required to nd the packing Un with maximum radius R and n = 8.
The resulting approximation of circles centers coordinate is following
O8 ≈ {(3.7997, 5.852), (6.547, 6.4971), (4.802, 6.2009), (8.5778, 5.132),
(3.7201, 7.6607), (6.7970, 3.3827), (4.9825, 4.8146), (5.7846, 8.7356)}.
∗
Radius Rmax ≈ 0.8787. Set M (bold line), packing U8 (thin line) and coor-
dinates of circles centers O8 (dots) are shown at g. 2.
5 Conclusions
We raised two classical problems of continuous optimization: optimal covering
and optimal packing with equal 2-D spheres (circles, discs) for a bounded subset
of a metric space. Practically, the addressed issues appear in logistics (so-called
facility location problems), communication, security, energy management etc.
The developed numerical algorithms, based on fundamental physical principles
by Fermat and Huygens (an optical-geometrical approach), prove themselves
rather e cient for covering and packing problems with non-convex sets, even
if the metric is non-Euclidean: numerical simulation con rms that the designed
approach is relevant. At the same time, in the case of Euclidean metric and a
su ciently large number of covering circles, our algorithms are shown to be com-
petitive, compared to known approaches. The latter observation was pleasantly
unexpected.
The obtained results could be further extended to multiply covering prob-
lems. This would be a subject of our future study.
340
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
12
y
10
8
6
4
2
x
0
−2 0 2 4 6 8 10 12 14
Fig. 1. Covering by 8 circles
Acknowledgments. The study is partially supported by the Russian Founda-
tion for Basic Research, projects nos 16-31-00356, 16-06-00464.
References
1. Al-Sultan, K., Hussain, M., Nizami, J.: A genetic algorithm for the set covering
problem. Journal of the Operational Research Society 47(5), 702709 (1996)
2. Astrakov, S., Erzin, A.: E cient band monitoring with sensors outer positioning.
Optimizat. J. Math. Program and Operat. Res. 62(10), 13671378 (2013)
3. Azimi, Z., Toth, P., Galli, L.: An electromagnetism metaheuristic for the unicost
set covering problem. European Journal of Operational Research 205(2), 290300
(2010)
4. Balazs, B., Endre, P., Balazs, L.: Optimal circle covering problems and their ap-
plications. CEJOR 23, 815832 (2015)
5. Birgin, E., Gentil, J.: New and improved results for packing identical unitary radius
circles within triangles, rectangles and strips. Computers and Operations Research
37(7), 13181327 (2010)
6. Boroczky, K.: Packing of spheres in spaces of constant curvature. Acta Mathemat-
ica Academiae Scientiarum Hungarica 32(3), 243261 (1978)
7. Brusov, V., Piyavskii, S.: A computational algorithm for optimally covering a plane
region. Computational Mathematics and Mathematical Physics 11(2), 1727 (1971)
8. Cardei, M., Wu, J., Lu, M.: Improving netwotk lifetime using sensors with ad-
justible sensing ranges. Int. J. Sensor Networks 1(1-2), 4149 (2006)
341
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
y
10
9
8
7
6
5
4
3
x
2
0 2 4 6 8 10 12
Fig. 2. Packing of 8 circles
9. Casado, L., Garcia, I., Szabo, P., Csendes, T.: Packing equal circles in a square ii.
new results for up to 100 circles using the tamsass-pecs algorithm. In: Giannessi,
F., Pardalos, P., Rapcsac, T. (eds.) Optimization Theory: Recent Developments
from Matrahaza, vol. 59, pp. 207224. Kluwer Academic Publishers, Dordrecht
(2001)
10. Coxeter, H.S.M.: Arrangements of equal spheres in non-euclidean spaces. Acta
Mathematica Academiae Scientiarum Hungarica 5(3), 263274 (1954)
11. Dileep, R.: Logistics of facility location and allocation. Marcel Dekker, Inc., New
York (2001)
12. Drezner, Z.: Facility location: A survey of applications and methods. Springer-Verl,
New York (1995)
13. Erzin, A., Astrakov, S.: Min-density stripe covering and applications in sensor
networks. Lecture Notes in Computer Science 6784(3), 152162 (2011)
14. Erzin, A., Plotnikov, R.: Wireless sensor network's lifetime maximization problem
in case of given set of covers. Lecture Notes in Computer Science 6786(5), 4457
(2011)
15. Galiev, S., Karpova, M.: Optimization of multiple covering of a bounded set with
circles. Computational Mathematics and Mathematical Physics 50(4), 721732
(2010)
16. Goldberg, M.: Packing of 14, 16, 17 and 20 circles in a circle. Mathematics Magazine
44(3), 134139 (1971)
17. Graham, R., Lubachevsky, B., Nurmela, K., Ostergard, P.: Dense packings of con-
gruent circles in a circle. Discrete Mathematics 181(1-3), 139154 (1998)
342
Mathematical and Information Technologies, MIT-2016 — Mathematical modeling
18. Jandl, H., Wieder, .: A continuous set covering problem as a quasidierentiale
optimization problem. Optimizat. J. Math. Program and Operat. Res. 19(6), 781
802 (1988)
19. Kazakov, A., Lempert, A.: An approach to optimization in transport logistics.
Automation and Remote Control 72(7), 13981404 (2011)
20. Kazakov, A., Lempert, A., Bukharov, D.: On segmenting logistical zones for ser-
vicing continuously developed consumers. Automation and Remote Control 74(6),
968977 (2013)
21. Lebedev, P., Ushakov, A.: Approximating sets on a plane with optimal sets of
circles. Automation and Remote Control 73(3), 485493 (2012)
22. Lempert, A., Kazakov, A.: On mathematical models for optimization problem of
logistics infrastructure. International Journal of Arti cial Intelligence 13(1), 200
210 (2015)
23. 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), 14631470 (2015)
24. Lopez, C., Beasley, J.: A heuristic for the circle packing problem with a variety of
containers. European Journal of Operational Research 214(3), 512525 (2011)
25. Lubachevsky, B., Graham, R.: Curved hexagonal packings of equal disks in a circle.
Discrete Comput Geom 18(1-3), 179194 (1997)
26. Markot, M., Csendes, T.: A new veri ed optimization technique for the packing
circles in a unit square problems. SIAM Journal on Optimization 16(1), 193219
(2005)
27. Melissen, J., Schuur, P.: Covering a rectangle with six and seven circles. Discrete
Appl. Math. 99, 149156 (2000)
28. Nasab, H., Tavana, M., Yousef, M.: A new heuristic algorithm for the planar mini-
mum covering circle problem. Production & Manufacturing Research 2(1), 142155
(2014)
29. Nurmela, K.: Conjecturally optimal coverings of an equilateral triangle with up to
36 equal circles. Experiment. Math. 9(2), 241250 (2000)
30. Nurmela, K., Ostergard, P.: Covering a square with up to 30 equal circles. Tech.
Rep. Res. rept A62., Lab. Technol. Helsinki Univ. (2000)
31. Specht, E.: Packomania. http://www.packomania.com/, accessed: 2015-10-28
32. Stoyan, Y., Patsuk, V.: Covering a compact polygonal set by identical circles.
Comput. Optim. Appl. 46, 7592 (2010)
33. Szabo, P., Specht, E.: Packing up to 200 equal circles in a square. In: Torn, A.,
Zilinskas, J. (eds.) Models and Algorithms for Global Optimization. Optimization
and Its Applications, vol. 4, pp. 141156. Springer, Heidelberg (2007)
34. Szirmai, J.: The optimal ball and horoball packings of the coxeter tilings in the
hyperbolic 3-space. Beitr. Algebra Geom. 46(2), 545558 (2005)
35. Szirmai, J.: The optimal ball and horoball packings to the coxeter honeycombs in
the hyperbolic d-space. Beitr. Algebra Geom. 48(1), 3547 (2007)
36. Szirmai, J.: A candidate for the densest packing with equal balls in thurston ge-
ometries. Beitr. Algebra Geom. 55(2), 441452 (2014)
37. Verter, V.: Uncapacitated and capacitated facility location problems. In: Eiselt,
H., Marianov, V. (eds.) Foundations of location analysis, pp. 2537. Springer, New
York (2011)
38. Watson-Gandy, C.: Heuristic procedures for the m-partial cover problem on a plane.
European Journal of Operational Research 11(2), 149157 (1982)
343