On reserve and double covering problems for the sets with non-Euclidean metrics
DOI:
https://doi.org/10.2298/YJOR171112010LKeywords:
covering problem, Fermat principle, Huygens principle, wave front, non-Euclidean metric, reserve covering, double covering, computational experimentAbstract
The article is devoted to Circle covering problem for a bounded set in a two-dimensional metric space with a given amount of circles. Here we focus on a more complex problem of constructing reserve and multiply coverings. Besides that, we consider the case where covering set is a multiply-connected domain. The numerical algorithms based on fundamental physical principles, established by Fermat and Huygens, are suggested and implemented. This allows us to solve the problems for the cases of non-convex sets and non-Euclidean metrics. Preliminary results of numerical experiments are presented and discussed. Calculations show the applicability of the proposed approach.References
Al-Sultan, K.S., Hussain, M.F., and Nizami, J.S., A genetic algorithm for the set covering problem, Journal of the Operational Research Society, 47 (5) (1996) 702-709.
Aldynool, T.A., Erzin, A.I., and Zalyubovskiy, V.V., The coverage of a planar region by randomly deployed sensors, Journal of Mathematical Sciences, 10 (4) (2010) 725.
Astrakov, S.N., and Erzin, A.I., Efficient band monitoring with sensors outer positioning, Optimizat. J. Math. Program and Operat. Res., 62 (10) (2013) 1367-1378.
Astrakov, S.N., Erzin, A.I., and Zalyubovskiy, V.V., Sensor networks and covering of plane by discs, Journal of Applied and Industrial Mathematics, 16 (3) (2009) 319.
Azimi, Z.N., Toth, P., and Galli, L., An electromagnetism metaheuristic for the unicost set covering problem, European Journal of Operational Research, 205 (2) (2010) 290-300.
Banhelyi, B., Palatinus, E., and Levai B.L., Optimal circle covering problems and their applications, Central European Journal of Operations Research, 23 (2015) 815-832.
Borovskikh, A.V., The two-dimensional eikonal equation, Siberian Mathematical Journal, 47 (5) (2006) 813-834.
Brusov, V.S., and Piyavskii, S.A., A computational algorithm for optimally covering a plane region, Computational Mathematics and Mathematical Physics, 11 (2) (1971) 17-27.
Cardei, M., Wu, J., and Lu, M., Improving network lifetime using sensors with adjustable sensing ranges, Int. J. Sensor Networks, 1 (2006) 41-49.
Drezner, Z., Facility location: A survey of applications and methods. Springer-Verl, New York, 1995.
Galiev, S.I., and Karpova M.A., Optimization of multiple covering of a bounded set with circles, Computational Mathematics and Mathematical Physics, 50 (4) (2010) 721-732.
Heppes, A., Covering a planar domain with sets of small diameter, Periodica Mathematica Hungarica, 53 (2006) 157-168.
Heppes, A., and Melissen, J.B.M., Covering a rectangle with equal circles, Periodica Mathematica Hungarica, 34 (1997) 65-81.
Jandl, H., and Wieder, K., A continuous set covering problem as a quasi-differential optimization problem, Optimizat. J. Math. Program and Operat. Res., 19 (6) (1988) 781-802.
Kazakov, A.L., and Lempert, A.A., An approach to optimization in transport logistics, Automation and Remote Control, 72 (7) (2011) 1398-1404.
Kazakov, A.L., Lempert, A.A., and Bukharov, D.S., On segmenting logistical zones for servicing continuously developed consumers, Automation and Remote Control, 74 (6) (2013) 968-977.
Lempert, A.A., Kazakov, A.L., and Bukharov, D.S., Mathematical model and program system for solving a problem of logistic object placement, Automation and Remote Control, 76 (8) (2015) 1463-1470.
Lempert, A.A., and Kazakov, A.L., On mathematical models for optimization problem of logistics infrastructure, International Journal of Artificial Intelligence, 13 (1) (2015) 200-210.
Melissen, J.B.M., and Schuur, P.C., Covering a rectangle with six and seven circles, Discrete Appl. Math., 99 (2000) 149-156.
Nasab, H.H., Tavana, M., and Yousef M., A new heuristic algorithm for the planar minimum covering circle problem, Production & Manufacturing Research, 2 (1) (2014) 142-155.
Nurmela, K.J., Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Experiment. Math., 9 (2) (2000) 241-250.
Nurmela, K.J., and Ostergard, P.R.J., Covering a square with up to 30 equal circles, Technical report, Lab. Technol. Helsinki Univ., 2000.
Stoyan, Y.G., and Patsuk, V.M., Covering a compact polygonal set by identical circles, Comput. Optim. Appl., 46 (2010) 75-92.
Tabirca, T., Yang, L.T., and Tabirca, S., Smallest number of sensors for k-covering, Int. J. Comput. Commun. Control, 8 (2) (2013) 312-319.
Tarnai, T., and Gaspar, Zs., Covering a square by equal circles, Elem. Math., 50 (1995) 167-170.
Ushakov, V.N., and Lebedev, P.D., Algorithms for the construction of an optimal cover for sets in three-dimensional euclidean space, Proc. of the Steklov Institute of Mathematics, 293 (S1) (2016) 225-237.
Watson-Gandy, C.D.T., Heuristic procedures for the m-partial cover problem on a plane, European Journal of Operational Research, 11 (2) (1982) 149-157.
Zahn Jr., C.T., Black box maximization of circular coverage, Journal of Research of the National Bureau of Standards, 66 (1962) 181-216.
Downloads
Published
Issue
Section
License
Copyright (c) 2019 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
