Вычислительный алгоритм для решения задачи упаковки шаров двух различных типов в трехмерное множество с неевклидовой метрикой

Авторы

  • А.Л. Казаков Институт динамики систем и теории управления им. В.М. Матросова СО РАН
  • А.А. Лемперт Институт динамики систем и теории управления им. В.М. Матросова СО РАН
  • Ч.Т. Та Иркутский национальный исследовательский технический университет

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

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

Аннотация

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

Авторы

А.Л. Казаков

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

А.А. Лемперт

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

Ч.Т. Та

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

  1. Castillo I., Kampas F.J., Pint´er J.D. Solving circle packing problems by global optimization: numerical results and industrial applications // European Journal of Operational Research. 2008. 191, N 3. 786–802.
  2. Harary F., Randolph W., Mezey P.G. A study of maximum unit-circle caterpillars — tools for the study of the shape of adsorption patterns // Discrete Applied Mathematics. 1996. 67, N 1–3. 127–135.
  3. Wang J. Packing of unequal spheres and automated radiosurgical treatment planning // Journal of Combinatorial Optimization. 1999. 3. 453–463.
  4. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem // Computational Geometry. 2010. 43, N 5. 535–553.
  5. Hales T. Cannonballs and honeycombs // Notices of the American Mathematical Society. 2000. 47, N 4. 440–449.
  6. Stoyan Y., Yaskov G. Packing identical spheres into a rectangular parallelepiped // Intelligent Decision Support. Wiesbaden: Betriebswirtschaftlicher Verlag Dr. Th. Gabler, 2008. 47–67.
  7. Stoyan Yu.G., Yaskov G. Packing identical spheres into a cylinder // International Transactions in Operational Research. 2009. 17, N 1. 51–70.
  8. Huang W., Yu L. Serial symmetrical relocation algorithm for the equal sphere packing problem. Ithaca: Cornell Univ. Library, 2012. Available at https://arxiv.org/abs/1202.4149.
  9. Mughal A., Chan H., Weaire D., Hutzler D. Dense packings of spheres in cylinders: simulations // Physical Review E. 2012. 85. doi 10.1103/PhysRevE.85.051305.
  10. Fu L., Steinhardt W., Zhaod H., Socolar J.E.S., Charbonneau P. Hard sphere packings within cylinders // Soft Matter. 2016. 12. 2505–2514.
  11. Scheithauer G., Stoyan Yu., Yaskov G. Packing non-equal spheres into containers of different shapes. 2013. http://www.math.tu-dresden.de/~scheith/ABSTRACTS/2013-spheres.html.
  12. Stoyan Yu.G., Scheithauer G., Yaskov G.N. Packing unequal spheres into various containers // Cybernetics and Systems Analysis. 2016. 52, N 3. 419–426.
  13. Khlud O.M., Yaskov G.N. Packing homothetic spheroids into a larger spheroid with the jump algorithm // Control, Navigation and Communication Systems. 2017. 6, N 46. 131–135.
  14. Kubach T., Bortfeldt A., Tilli T., Gehring H. Parallel greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid. 2009. https://www.fernuni-hagen.de/wirtschaftswissenschaft/download/beitraege/db440.pdf.
  15. Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid // Asia Pacific Journal of Operational Research. 2011. 28, N 6. 739–753.
  16. Huang W.Q., Li Y., Akeb H., Li C.M. Greedy algorithms for packing unequal circles into a rectangular container // Journal of the Operational Research Society. 2005. 56, N 5. 539–548.
  17. Hifi M., Yousef L. Width beam and hill-climbing strategies for the three-dimensional sphere packing problem // 2014 Federated Conference on Computer Science and Information Systems. New York: IEEE Press, 2014. 421–428.
  18. Yamada S., Kanno J., Miyauchi M. Multi-sized sphere packing in containers: optimization formula for obtaining the highest density with two different sized spheres // IPSJ Online Transactions. 2011. 4. 126–133.
  19. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. 50–57.
  20. Бухаров Д.С., Казаков А.Л. Программная система “ВИГОЛТ” для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование. 2012. 13 65–74.
  21. Казаков А.Л., Лемперт А.А., Бухаров Д.С. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей // Автоматика и телемеханика. 2013. № 6. 87–100.
  22. Kazakov A.L., Lempert A.A. On mathematical models for optimization problem of logistics infrastructure // International Journal of Artificial Intelligence. 2015. 13, N 1. 200–210.
  23. Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычислительные методы и программирование. 2015. 16. 307–317.
  24. Казаков А.Л., Лемперт A.A., Нгуен Г.Л. Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой // Вычислительные методы и программирование. 2016. 17. 177–188.
  25. Kazakov A.L., Lempert A.A., Ta T.T. The sphere packing problem into bounded containers in three-dimension non-Euclidean space // IFAC-PapersOnLine. 2018. 51, N 32. 782–787.
  26. Kazakov A.L., Lempert A.A., Ta T.T. On the algorithm for equal balls packing into a multi-connected set // VIth International Workshop on Critical Infrastructures: Contingency Management, Intelligent, Agent-Based, Cloud Computing and Cyber Security (IWCI 2019). Paris: Atlantis Press, 2019. 216–222.
  27. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989.
  28. Graham R.L., Lubachevsky B.D., Nurmela K.J., Ostergard P.R.J. Dense packings of congruent circles in a circle // Discrete Mathematics. 1998. 181, N 1–3. 139–154.

Опубликован

2020-05-20

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

Казаков А.Л., Лемперт А.А., Та Ч.Т. Вычислительный алгоритм для решения задачи упаковки шаров двух различных типов в трехмерное множество с неевклидовой метрикой // Вычислительные методы и программирование. 2020. 21. 152-163

Выпуск

Раздел

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

Наиболее читаемые статьи этого автора (авторов)