An algorithm of packing congruent circles in a multiply connected set with non-Euclidean metrics

Authors

DOI:

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

Keywords:

optimal packing of circles, optical-geometric approach, non-Euclidean space, multiply connected domain, numerical method, computational experiment

Abstract

The problem of optimal packing of congruent circles in a bounded set (a container) in a two-dimensional metric space is considered. It is required to find an arrangement of circles in the container such that these circles occupy the largest area of the container as possible. In the case when the space is Euclidean, this problem is well known, but the case of non-Euclidean metrics is studied much worse. However, there are some applied problems leading us to the use of special non-Euclidean metrics. For example, such a situation appears in the infrastructure logistics. Here we consider the optimal packing problem in the case when the container is simply or multiply connected. A special algorithm based on the optical-geometric approach is proposed and implemented. The results of numerical experiments are discussed.

Author Biographies

A.L. Kazakov

A.A. Lempert

H.L. Nguyen

References

  1. Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычислительные методы и программирование: новые вычислительные технологии. 2015. 16. 307-317.
  2. Бухаров Д.С., Казаков А.Л. Программная система «Виголт» для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование: новые вычислительные технологии. 2012. 13. 65-74.
  3. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. М.: Мир, 1990.
  4. Kellerer H., Pferschy U., Pisinger D. Knapsack problems. Berlin: Springer, 2004.
  5. Левенштейн В.И. О границах для упаковок в n-мерном евклидовом пространстве // Доклады АН СССР. 1979. 245, № 6. 1299-1303.
  6. Гэри М.Р., Джонсон Д.С. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
  7. Casado L.G., Garcia I., Szab’o P.G., Csendes T. Packing equal circles in a square II - New results for up to 100 circles using the TAMSASS-PECS algorithm // Optimization Theory. Dordrecht: Kluwer, 2001. 207-224.
  8. Mark’ot M.Cs., Csendes T. A new verified optimization technique for the «packing circles in a unit square» problems // SIAM Journal on Optimization. 2005. 16, № 1. 193-219.
  9. Szab’o P.G., Specht E. Packing up to 200 equal circles in a square // Global Optimization. NY: Springer, 2007. 141-156.
  10. Goldberg M. Packing of 14, 16, and 20 circles in a circle // Mathematics Magazine. 1971. 44, N 3. 134-139.
  11. Graham R.L., Lubachevsky B.D., Nurmela K.J., Östergard P.R. J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. 181, N 1-3. 139-154.
  12. Lubachevsky B.D., Graham R.L. Curved hexagonal packings of equal disks in a circle // Discrete Comput. Geom. 1997. 18, N 2. 179-194.
  13. Birgin E.G., Gentil J.M New and improved results for packing identical unitary radius circles within triangles, rectangles and strips // Computers and Operations Research. 2010. 37, N 7. 1318-1327.
  14. Litvinchev I., Ozuna E.L. Integer programming formulations for approximate packing circles in a rectangular container // Mathematical Problems in Engineering. 2014. doi: 10.1155/2014/317697.
  15. Litvinchev I., Ozuna E.L. Packing circles in a rectangular container // Proceedings of the International Congress on Logistics and Supply Chain. Queretaro: Mexican Inst. of Transportation, 2013. 24-25.
  16. L’opez C.O., Beasley J.E. A heuristic for the circle packing problem with a variety of containers // European Journal of Operational Research. 2011. 214, N 3. 512-525.
  17. L’opez C.O., Beasley J.E. Packing unequal circles using formulation space search // Computers and Operations Research. 2013. 40, N 5. 1276-1288.
  18. Pedroso J.P., Cunha S., Tavares J.N. Recursive circle packing problems // International Transactions in Operational Research. 2014. 23, N 1-2. 355-368.
  19. Andrade R., Birgin E.G. Symmetry-breaking constraints for packing identical rectangles within polyhedra // Optimization Letters. 2013. 7, N 2. 375-405.
  20. Галиев Ш.И., Лисафина М.С. Численные методы оптимизации упаковок равных ортогонально ориентированных эллипсов в прямоугольную область // Журн. вычисл. матем. и матем. физ. 2013. 53, № 11. 1923-1938.
  21. Coxeter H.S. M. Arrangements of equal spheres in non-Euclidean spaces // Acta Mathematica Academiae Scientiarum Hungarica. 1954. 5, N 3. 263-274.
  22. Böröczky K. Packing of spheres in spaces of constant curvature // Acta Mathematica Academiae Scientiarum Hungarica. 1978. 32, N 3. 243-261.
  23. Szirmai J. The optimal ball and horoball packings of the Coxeter tilings in the hyperbolic 3-space // Beitr. Algebra Geom. 2005. 46, N 2. 545-558.
  24. Szirmai J. The optimal ball and horoball packings to the Coxeter honeycombs in the hyperbolic d-space // Beitr. Algebra Geom. 2007. 48, N 1. 35-47.
  25. Szirmai J. A candidate for the densest packing with equal balls in Thurston geometries // Beitr. Algebra Geom. 2014. 55, N 2. 441-452.
  26. Казаков А.Л., Журавская М.А., Лемперт А.А. Вопросы сегментации логистических платформ в условиях становления региональной логистики // Транспорт Урала. 2010. № 4. 17-20.
  27. Лемперт А.А., Казаков А.Л., Бухаров Д.С. Математическая модель и программная система для решения задачи размещения логистических объектов // Управление большими системами. 2013. № 41. 270-284.
  28. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. 87-100.
  29. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. 50-57.
  30. Kazakov A.L., Lempert A.A. On mathematical models for optimization problem of logistics infrastructure // International Journal of Artificial Intelligence. 2015. 13, № 1. 200-210.
  31. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. М.: Мир, 1989.
  32. Specht E. Packomania. http://www.packomania.com.
  33. Москаленский Е.Д. О нахождении точных решений двумерного уравнения эйконала для случая, когда фронт волны, распространяющейся в среде, является окружностью // Сиб. ж. вычислит. математики. 2014. 17, № 4. 363-372.

Published

2016-05-03

How to Cite

Казаков А.Л., Лемперт А.А., Нгуен Г.Л. An Algorithm of Packing Congruent Circles in a Multiply Connected Set With Non-Euclidean Metrics // Numerical methods and programming. 2016. 17. 177-188. doi 10.26089/NumMet.v17r216

Issue

Section

Section 1. Numerical methods and applications