Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Том 59 >>> № 1 СІЧЕНЬ — ЛЮТИЙ 2023
-->

УДК 514.18: 519.8

С.В. ЯКОВЛЕВ,
Національний аерокосмічний університет ім. М.Є. Жуковського «Харківський авіаційний інститут», Харків, Україна; Лодзинський політехнічний університет, Лодзь, Польща,  svsyak7@gmail.com


КОНЦЕПЦІЯ МОДЕЛЮВАННЯ ЗАДАЧ РОЗМІЩЕННЯ
ТА ПОКРИТТЯ З ВИКОРИСТАННЯМ СУЧАСНИХ
ПАКЕТІВ ОБЧИСЛЮВАЛЬНОЇ ГЕОМЕТРІЇ

Анотація. Розглянуто клас геометричних задач розміщення та покриття. Запропоновано нову концепцію їхнього математичного моделювання з використанням спеціального класу функцій. Для розв’язування задач використано спеціальні бібліотеки програм обчислювальної геометрії, які не потребують аналітичного вигляду функцій, що описують умови розміщення та покриття, але дають змогу здійснювати їхню перевірку. Обґрунтовано скорочення обчислювальних витрат, що розширює можливості ефективного застосування методів локальної та глобальної оптимізації. Наведено результати розв’язування тестових задач максимального покриття прямокутної області сукупністю еліпсів заданих розмірів та задачу розміщення еліпсів у прямокутнику мінімальної площі.

Ключові слова: задачі розміщення та покриття, математичне моделювання, пакети обчислювальної геометрії, оптимізація.


повний текст

СПИСОК ЛІТЕРАТУРИ

  1. Toth L.F. Regulare Figuren. Budapemia: Akiademia, 1965. 316 p.

  2. Rogers C.A. Packing and covering. Cambridge: University Press, 1964. 109 p.

  3. Stoyan Y.G. Mathematical methods for geometric design. Advances in CAD/CAM. Proc. of PROLAMAT82. Leningrad, USSR, May 1982. P. 67–86. North–Holland, Amsterdam. The Netherlands, 2003.

  4. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наук. думка, 2020. 272 с.

  5. Berge C. Principes de combinatoire. Paris: Dunod, 1968. 146 p.

  6. Stoyan Y.G., Yakovlev S.V. Configuration space of geometric objects. Cybernetics and Systems Analysis. 2018. Vol. 54, N 5. P. 716–726. https://doi.org/10.1007/s10559-018-0073-5.

  7. Yakovlev S.V. On some classes of spatial configurations of geometric objects and their formalization. Journal of Automation and Information Sciences. 2018. Vol. 50, Iss. 9. P. 38–50. https://doi.org/10.1615/JAutomatInfScien.v50.i9.30.

  8. Рвачев В.Л. Теория R-функций и некоторые ее приложения. Киев: Наук. думка, 1982. 552 с.

  9. Stoyan Yu., Romanova T. Mathematical models of placement optimisation: two- and three-dimensional problems and applications. In: Modeling and Optimization in Space Engineering. Fasano G., PintБr J. (Eds.). SOIA. 2013. Vol. 73. P. 363–388. https://doi.org/10.1007/978-1-4614-4469-5_15.

  10. Bennell J., Scheithauer G., Stoyan Y.G., Romanova T. Tools of mathematical modelling of arbitrary object packing problems. Annals of Operations Research. 2010. Vol. 179, Iss. 1. P. 343–368. https://doi.org/10.1007/s10479-008-0456-5.

  11. Stoyan Y., Gil M., Terno J., Romanova T., Schithauer G. Ф-function for complex 2D objects. 4OR Quarterly Journal of the Belgian, French and Italian Operations Research Societies. 2004. Vol. 2, N 1. P. 69–84.

  12. Scheithauer G., Stoyan Yu., Romanova T. Mathematical modeling of interaction of primary geometric 3D objects. Cybernetics and Systems Analysis. 2005. Vol. 41, N 3. P. 332–342. https://doi.org/10.1007/s10559-005-0067-y .

  13. Stoyan Yu., Romanova T., Pankratov A., Chugay A. Optimized object packings using quasi-phi-functions. In: Optimized Packings with Applications. Fasano G., PintБr J.D. (Eds.). SOIA. 2015. Vol. 105. P. 265–293. https://doi.org/10.1007/978-3-319-18899-7_13.

  14. Pankratov A., Romanova T., Litvinchev I. Packing ellipses in an optimized convex polygon. Journal of Global Optimization. 2019. Vol. 75, Iss. 2. P. 495–522. https://doi.org/10.1007/ s10898-019-00777-y.

  15. Romanova T., Stoyan Y., Pankratov A. et al. Optimal layout of ellipses and its application for additive manufacturing. International Journal of Production Research. 2021. Vol. 59, Iss. 2. P. 560–575. https://doi.org/10.1080/00207543.2019.1697836.

  16. Stoyan Yu.G., Pankratov A.V., Romanova T.E. Mathematical modeling of distance constraints on two-dimensional -objects. Cybernetics and Systems Analysis. 2012. Vol. 48, N 3. 330–334. https://doi.org/10.1007/s10559-012-9412-0.

  17. Stoyan Yu., Pankratov A., Romanova T., Fasano G., PintБr J.D., Stoian Yu.E., Chugai A. Optimized packings in space engineering applications: Part I. In: Modeling and Optimization in Space Engineering. Fasano G., PintБr J.D. (Eds.). SOIA. 2019. Vol. 144. P. 395–437. https://doi.org/10.1007/978-3-030-10501-3_15.

  18. Stoyan Yu., Pankratov A., Romanova T. Placement problems for irregular objects: Mathematical modeling, optimization and applications. In: Optimization Methods and Applications. Butenko S. Pardalos P.M., Shylo V. (Eds.). SOIA. 2017. Vol. 130. P. 521–558. https://doi.org/10.1007/ 978-3-319-68640-0_25.

  19. Stoyan Y.G., Romanova T., Scheithauer G. et al. Covering a polygonal region by rectangles. Computational Optimization and Applications. 2011. Vol. 48, Iss. 3. P. 675–695. https://doi.org/10.1007/s10589-009-9258-1.

  20. Стоян Ю.Г., Сосюрка Е.С. Покриття компактної багатогранної області скінченим сімейством прямих паралелепіпедів. Доповiдi Національної академії наук України. 2010. № 8. С. 43–48.

  21. Магас С.Л. Определение и свойства структур линейных неравенств. Автоматизация проектирования в машиностроении. 1983. Bып. 3. C. 5–11.

  22. Stoyan Yu.G., Novozhilova M.V., Kartashov A.V. Mathematical model and method of searching for a local extremum for the non-convex oriented polygons allocation problem. European Journal of Operational Research. 1996. Vol. 92, Iss. 1. P. 193–210. https://doi.org/10.1016/ 0377-2217(95)00038-0.

  23. Yakovlev S.V. On a class of problems on covering of a bounded set. Acta Mathematica Hungarica. 1989. Vol. 53, Iss. 3–4. P. 253–262. https://doi.org/10.1007/BF01953365.

  24. Shekhovtsov S.B., Yakovlev S.V. Formalization and solution of one class of covering problem in design of control and monitoring systems. Autom. Remote Control. 1989. Vol. 50, Iss. 5. P. 705–710.

  25. Yakovlev S.V. Formalizing spatial configuration optimization problems with the use of a special function class. Cybernetics and Systems Analysis. 2019. Vol. 55, N 4. P. 581–589. https://doi.org/10.1007/s10559-019-00167-y .

  26. Кісельова О.М., Гарт Л.Л. Елементи теорії функцій множин. Дніпро: Вид-во ДНУ, 2006. 176 с.

  27. Kiseleva E.M. The emergence and formation of the theory of optimal set partitioning for sets of the n-dimensional Euclidean space. Theory and application. Journal of Automation and Information Sciences. 2018. Vol. 50, Iss. 9. P. 1–24. https://doi.org/10.1615/JAutomatInfScien.v50.i9.10.

  28. 28. Kiseleva E.M., Kadochnikova Ya.E. Solving a continuous single-product problem of optimal partitioning with additional conditions. Journal of Automation and Information Sciences. 2009. Vol. 41, Iss. 7. P. 48–63. https://doi.org/10.1615/JAutomatInfScien.v41.i7.30 .

  29. Gillies S. The shapely user manual. URL: https://shapely.readthedocs.io/en/stable/manual.html.

  30. Shapely 1.8.5.post1 documentation. URL: https://shapely.readthedocs.io/en/stable/.

  31. Yakovlev S., Kartashov O., Podzeha D. Mathematical models and nonlinear optimization in continuous maximum coverage location problem. Computation. 2022. Vol. 10, Iss 7. 119. https://doi.org/10.3390/computation10070119 .

  32. Yakovlev S., Kartashov O., Mumrienko A. Formalization and solution of the maximum area coverage problem using library Shapely for territory monitoring. Radioelectronic and Computer Systems. 2022. Vol. 2022, Iss. 2. P. 35–48. https://doi.org/10.32620/reks.2022.2.03.

  33. Birgin E.G., Lobato R.D., Martinez J.M. A nonlinear programming model with implicit variables for packing ellipsoids. Journal of Global Optimization. 2017. Vol. 68, Iss. 3. P. 467–499. https://doi.org/10.1007/s10898-016-0483-8.

  34. Stoyan Y.G., Romanova T.E., Pankratov O.V., Stetsyuk P.I., Maximov S.V. Sparse balanced layout of ellipsoids. Cybernetics and Systems Analysis. 2021. Vol. 57, N 6. P. 864–873. https://doi.org/10.1007/s10559-021-00412-3.

  35. Stoyan Y., Romanova T., Pankratov A., Kovalenko A., Stetsyuk P. Balance layout problems: Mathematical modeling and nonlinear optimization. In: Space Engineering. Fasano G., PintБr J.D. (Eds.). SOIA. 2016. Vol. 114. P. 369–400. https://doi.org/10.1007/978-3-319-41508-6_14.

  36. Romanova T., Litvinchev I., Shekhovtsov S. Packing convex 3D objects with special geometric and balancing conditions. In: Intelligent Computing and Optimization. Vasant P., Zelinka I., Weber G.-W. (Eds.). Advances in Intelligent Systems and Computing. 2020. Vol. 1072. Р. 273–281. https://doi.org/10.1007/978-3-030-33585-4_27.

  37. Glover F., Sorensen K. (Eds.). Metaheuristics. Scholarpedia. 2015. 10(4):6532.

  38. MartЗ R., Pardalos P.M., Resende M.G.C. (Eds.). Handbook of heuristics. Springer International Publishing, 2018.

  39. Gulyanitskii L.F., Sergienko I.V. Metaheuristic downhill simplex method in combinatorial optimization. Cybernetics and Systems Analysis. 2007. Vol. 43, N 6. P. 822–829. https://doi.org/10.1007/s10559-007-0106-y .

  40. Romanova T.E., Stetsyuk P.I., Chugay A.M., Shekhovtsov S.B. Parallel computing technologies for solving optimization problems of geometric design. Cybernetics and Systems Analysis. 2019. Vol. 55, N 6. P. 894–904. https://doi.org/10.1007/s10559-019-00199-4.

  41. Church R.L., ReVelle C. The maximal covering location problem. Papers of the Regional Science Association. 1974. Vol. 32, Iss. 1. P. 101–118. https://doi.org/10.1007/BF01942293.

  42. Murray A.T. Maximal coverage location problem: impacts, significance, and evolution. International Regional Science Review. 2016. Vol. 39, Iss. 1. P. 5–27. https://doi.org/10.1177/0160017615600222.

  43. Coll N., Fort M., Saus M. Coverage area maximization with parallel simulated annealing. Expert Systems with Application. 2022. Vol. 202. 117185. https://doi.org/10.1016/j.eswa.2022.117185.

  44. Murray A.T., Church R.L. Location covering models: History, applications and advancements. Ser. Advances in Spatial Science. Cham: Springer, 2018. 271 p. https://doi.org/10.1007/978-3-319-99846-6.

  45. Blanco V., Gїzquez R. Continuous maximal covering location problems with interconnected facilities. Computers & Operations Research. 2021. Vol. 132. 105310.

  46. Bansal M., Kianfar K. Planar maximum coverage location problem with partial coverage and rectangular demand and service zones. INFORMS Journal on Computing. 2017. Vol. 29, N 1. P. 152–169. https://doi.org/10.1287/ijoc.2016.0722.

  47. Davari S., Fazel Zarandi M.H., Hemmati A. Maximal covering location problem (MCLP) with fuzzy travel times. Expert Systems with Applications. 2011. Vol. 38, Iss. 12. P. 14535–14541. https://doi.org/10.1016/j.eswa.2011.05.031.

  48. Fletcher R. Practical methods for optimization (2nd ed.). New York: John Wiley Sons, 1987. 456 p.

  49. Kallrath J., Rebennack S. Cutting ellipses from area-minimizing rectangles. Journal of Global Optimization. 2014. Vol. 59, Iss. 2–3. P. 405–437. https://doi.org/10.1007/s10898-013-0125-3.

  50. Miller P. Globally optimal packing of nonconvex two dimensional shapes by approximation with ellipses. Senior thesis. Princeton University, Princeton, NJ. 2012.

  51. Stoyan Yu., Pankratov A., Romanova T. Cutting and packing problems for irregular objects with continuous rotations: Mathematical modelling and non-linear optimization. Journal of the Operational Research Society. 2016. Vol. 67, Iss. 5. P. 786–800. https://doi.org/10.1057/jors.2015.94.

  52. Litvinchev I., Infante L., Ozuna L. Packing circular-like objects in a rectangular container. Journal of Computer and Systems Sciences International. 2015. Vol. 54, Iss. 2. P. 259–267. https://doi.org/10.1134/S1064230715020070.

  53. Birgin E.G., Lobato R.D., Martinez J.M. Packing ellipsoids by nonlinear optimization. Journal of Global Optimization. 2016 Vol. 65, Iss. 4. P. 709–743. https://doi.org/10.1007/s10898-015-0395-z.

  54. Optimal packing of rotating ellipses. URL: https://app.box.com/s/mo7xjvjve7v52p9movfi.

  55. Бейко И.В., Бублик Б.Н., Зинько П.Н. Методы и алгоритмы решения задач оптимизации. Киев: Вища шк., 1983. 512 с.




Інформація редакції Аннотації статей Автори Архів
Журнал Тематичні Розділи Редакція Редакційна колегія Приклади документів Передплата Контакти
© 2023 Kibernetika.org. All rights reserved.