Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой

Авторы

  • А.Л. Казаков Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН) https://orcid.org/0000-0002-3047-1650
  • А.А. Лемперт Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН) https://orcid.org/0000-0001-9562-7903
  • Г.Л. Нгуен Иркутский национальный исследовательский технический университет

DOI:

https://doi.org/10.26089/NumMet.v17r216

Ключевые слова:

oптимальная упаковка кругов, оптико-геометрический подход, неевклидово пространство, многосвязная область, численный метод, вычислительный эксперимент

Аннотация

Рассматривается задача об упаковке конгруэнтных кругов в ограниченное множество (контейнер) в двумерном метрическом пространстве: требуется найти такое расположение кругов в контейнере, при котором они заполнят как можно большую долю последнего. В случае, когда пространство является евклидовым, эта задача достаточно хорошо изучена, однако существует ряд прикладных задач, в частности в области инфраструктурной логистики, которые приводят нас к необходимости использовать специальные неевклидовые метрики. Исследованию таких задач и посвящена данная работа, причем рассматриваются как односвязные, так и многосвязные контейнеры. Разработан и программно реализован алгоритм численного решения указанной задачи, основанный на оптико-геометрическом подходе. Приведены результаты вычислительного эксперимента.

Авторы

А.Л. Казаков

Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН)
ул. Лермонтова, 134, 664033, Иркутск
• заведующий лабораторией

А.А. Лемперт

Институт динамики систем и теории управления имени В.М. Матросова СО РАН (ИДСТУ СО РАН)
ул. Лермонтова, 134, 664033, Иркутск
• ведущий научный сотрудник

Г.Л. Нгуен

Иркутский национальный исследовательский технический университет
ул. Лермонтова 83, 664074, Иркутск
• аспирант

Библиографические ссылки

  1. A. L. Kazakov and P. D. Lebedev, “Algorithms of Optimal Packing Construction for Planar Compact Sets,” Vychisl. Metody Programm. 16, 307-317 (2015).
  2. D. S. Bukharov and A. L. Kazakov, “VIGOLT System for Solving Transport Logistics Optimization Problems,” Vychisl. Metody Programm. 13, 65-74 (2012).
  3. J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer, New York, 1988; Mir, Moscow, 1990).
  4. H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems (Springer, Berlin, 2004).
  5. V. I. Levenshtein, “Boundaries for Packings in n-Dimensional Euclidean Space,” Dokl. Akad. Nauk SSSR 245 (6), 1299-1303 (1979).
  6. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir, Moscow, 1982).
  7. L. G. Casado, I. Garcia, P. G. Szabó, and T. Csendes, “Packing Equal Circles in a Square II. - New Results for up to 100 Circles Using the TAMSASS-PECS Algorithm,” in Optimization Theory (Kluwer, Dordrecht, 2001), pp. 207-224.
  8. M. C. Markót and T. Csendes, “A New Verified Optimization Technique for the ’Packing Circles in a Unit Square’ Problems,” SIAM J. Optim. 16 (1), 193-219 (2005).
  9. P. G. Szabó and E. Specht, “Packing up to 200 Equal Circles in a Square,” in Models and Algorithms for Global Optimization (Springer, New York, 2007), pp. 141-156.
  10. M. Goldberg, “Packing of 14, 16, 17 and 20 Circles in a Circle,” Math. Mag. 44 (3), 134-139 (1971).
  11. R. L. Graham, B. D. Lubachevsky, K. J. Nurmela, and P. R. J. Östergard, “Dense Packings of Congruent Circles in a Circle,” Discrete Math. 181 (1-3), 139-154 (1998).
  12. B. D. Lubachevsky and R. L. Graham, “Curved Hexagonal Packings of Equal Disks in a Circle,” Discrete Comput. Geom. 18 (2), 179-194 (1997).
  13. E. G. Birgin and J. M. Gentil, “New and Improved Results for Packing Identical Unitary Radius Circles within Triangles, Rectangles and Strips,” Comput. Oper. Res. 37 (7), 1318-1327 (2010).
  14. I. Litvinchev and E. L. Ozuna, “Integer Programming Formulations for Approximate Packing Circles in a Rectangular Container,” Math. Probl. Eng. 2014 (2014).
    doi 10.1155/2014/317697
  15. I. Litvinchev and E. L. Ozuna, “Packing Circles in a Rectangular Container,” in Proc. Int. Congr. on Logistics and Supply Chain, Queretaro, Mexico, October 24-25, 2013 (Mexican Inst. of Transportation, Queretaro, 2013), pp. 24-25.
  16. C. O. López and J. E. Beasley, “A Heuristic for the Circle Packing Problem with a Variety of Containers,” Eur. J. Oper. Res. 214 (3), 512-525 (2011).
  17. C. O. López and J. E. Beasley, “Packing Unequal Circles Using Formulation Space Search,” Comput. Oper. Res. 40 (5), 1276-1288 (2013).
  18. J. P. Pedroso, S. Cunha, and J. N. Tavares, “Recursive Circle Packing Problems,” Int. Trans. Oper. Res. 23 (1-2), 355-368 (2014).
  19. R. Andrade and E. G. Birgin, “Symmetry-Breaking Constraints for Packing Identical Rectangles within Polyhedra,” Optim. Lett. 7 (2), 375-405 (2013).
  20. Sh. I. Galiev and M. S. Lisafina, “Numerical Optimization Methods for Packing Equal Orthogonally Oriented Ellipses in a Rectangular Domain,” Zh. Vychisl. Mat. Mat. Fiz. 53 (11), 1923-1938 (2013) [Comput. Math. Math. Phys. 53 (11), 1748-1762 (2013)].
  21. H. S. M. Coxeter, “Arrangements of Equal Spheres in Non-Euclidean Spaces,” Acta Math. Acad. Sci. Hung. 5 (3), 263-274 (1954).
  22. K. Böröczky, “Packing of Spheres in Spaces of Constant Curvature,” Acta Math. Acad. Sci. Hung. 32 (3), 243-261 (1978).
  23. J. Szirmai, “The Optimal Ball and Horoball Packings of the Coxeter Tilings in the Hyperbolic 3-Space,” Beitr. Algebra Geom. 46 (2), 545-558 (2005).
  24. J. Szirmai, “The Optimal Ball and Horoball Packings to the Coxeter Honeycombs in the Hyperbolic d-Space,” Beitr. Algebra Geom. 48 (1), 35-47 (2007).
  25. J. Szirmai, “A Candidate for the Densest Packing with Equal Balls in Thurston Geometries,” Beitr. Algebra Geom. 55 (2), 441-452 (2014).
  26. A. L. Kazakov, M. A. Zhuravskaya, and A. A. Lempert, “The Problems of Logistic Platforms Segmentation in the Conditions of Regional Logistics Development,” Transport Urala, No. 4, 17-20 (2010).
  27. A. A. Lempert, A. L. Kazakov, and D. S. Bukharov, “Mathematical Model and Program System for Solving a Problem of Logistic Objects Placement,” Upravlenie Bol’shimi Sistemami, No. 41, 270-284 (2013).
  28. A. L. Kazakov, A. A. Lempert, and D. S. Bukharov, “On Segmenting Logistical Zones for Servicing Continuously Developed Consumers,” Avtom. Telemekh., No. 6, 87-100 (2013) [Autom. Rem. Contr. 74 (6), 968-977 (2013)].
  29. A. L. Kazakov and A. A. Lempert, “An Approach to Optimization in Transport Logistics,” Avtom. Telemekh., No. 7, 50-57 (2011) [Autom. Rem. Contr. 72 (7), 1398-1404 (2011)].
  30. A. L. Kazakov and A. A. Lempert, “On Mathematical Models for Optimization Problem of Logistics Infrastructure,” Int. J. Artif. Intell. 13 (1), 200-210 (2015).
  31. F. P. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Springer, New York, 1985; Mir, Moscow, 1989).
  32. E. Specht, “Packomania,”
    http://www.packomania.com . Cited May 14, 2016.
  33. E. D. Moskalensky, “On Finding Exact Solutions of the Two-Dimensional Eikonal Equation when the Front of the Wave Propagating in a Medium is a Circle,” Sib. Zh. Vychisl. Mat. 17 (4), 363-372 (2014) [Numer. Anal. Appl. 7 (4), 304-313 (2014)].
Новые вычислительные технологии

Загрузки

Опубликован

03-05-2016

Как цитировать

Казаков А., Лемперт А., Нгуен Г. Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой // Вычислительные методы и программирование. 2016. 17. 177-188. doi 10.26089/NumMet.v17r216

Выпуск

Том 17 (2016): Выпуск 2.

Раздел

Раздел 1. Вычислительные методы и приложения