The article is devoted to optimal covering and packing problems for a bounded set in a two-dimensional metric space with a given amount of congruous circles. Such problems are of both theoretical interest 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 principles 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 discussed. Calculations show the applicability of the proposed approach its high eciency for covering of a convex set in the Euclidean space by a suciently large amount of circles.
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 denes facilities as An
installation, contrivance, or other thing which facilitates something; a place for
doing something: Commercial or institutional buildings, including oces, plants
and warehouses. There is a number of papers devoted to the problem, see e.g.
[
In connection with the above, we develop a multi-stage technology for studying complex systems. On the rst stage, we solve the problem of optimal placement 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 modications 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 designing of a proper communication system for the above dened 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 operates 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 [
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 [
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 [
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
Assume we are given a bounded domain containing a collection of disjoint prohibited 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 :
P = cl
D \ m [ Bk k=1
⊂ X ⊆ R2 . ρ(a, b) =
min Γ ∈G(a,b)
dΓ f (x, y)
, ! Z Γ 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 R∗ = min min i=1,n ρ (si, (Sn\{si})) , ρ(si, ∂P ) 2 .
(1) (2) (3) 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) .
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 P m∗ = {Ok∗}, which provide minimum for R∗ = max ρ (Ok, ∂Mk) .
k=1,m (4) (5) The formulated logistic problem is equivalent to optimal covering of the set M with the metric (2) by circles of equal radia. 3
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 [
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 [
Rk min = max ρ(O¯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 = O¯k, k = 1, m.
k=1,..m Steps 27 are being carried out while covering
Pm = m [ Ck(O¯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 r .
i=1,...,n i Steps 2-4 are being carried out until R is increasing, then the current vector ¯
Sn = {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
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 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 [
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 [
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 [
(x − 4.5)2 + (y − 6)2 (x − 4.5)2 + (y − 6)2) + 1 + 0.5.
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 following
S8 ≈ {(3.610, 4.375), (3.725, 7.750), (5.603, 9.748), (6.0, 8.745) ,
Radius Rmax ≈ 0.8787. Set M (bold line), packing U8∗ (thin line) and coordinates of circles centers O8 (dots) are shown at g. 2. 5
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 ecient for covering and packing problems with non-convex sets, even if the metric is non-Euclidean: numerical simulation conrms that the designed approach is relevant. At the same time, in the case of Euclidean metric and a suciently large number of covering circles, our algorithms are shown to be competitive, compared to known approaches. The latter observation was pleasantly unexpected.
The obtained results could be further extended to multiply covering problems. This would be a subject of our future study. 0 −2 Acknowledgments. The study is partially supported by the Russian Foundation for Basic Research, projects nos 16-31-00356, 16-06-00464. 2 4 6 8
10