УДК 514.174.2
MSC: 52C17, 05B40, 51M16, 52A27
DOI: 10.21538/0134-4889-2020-26-2-173-187
Полный текст статьи (Full text)
Исследование П.Д. Лебедева поддержано грантом РНФ (проект № 19-11-00105), исследование А.Л. Казакова выполнено при поддержке РФФИ (проект № 18-07-00604), исследование А.А. Лемперт — при поддержке РФФИ (проект № 20-010-00724) и Правительства Иркутской области.
Исследуется проблема оптимальной упаковки неравных шаров в выпуклый компакт. Рассматриваются наборы шаров, радиусы которых пропорциональны заданному параметру r. Максимизация последнего выбрана в качестве критерия оптимальности. Наибольшее возможное количество различных типов шаров равно трем. Задача относится к классу NP-трудных и исследуется численно. Предложены алгоритмы, основанные на сегментации заданного компакта на зоны влияния центров элементов упаковки (обобщенные зоны Дирихле). Разбиение строится с использованием оптико-геометрического подхода, развиваемого в последние годы авторами. После получения промежуточного результата выполняется процедура улучшения с помощью разработанного геометрического алгоритма. В качестве его основы использованы методы, базирующиеся на пошаговом сдвиге точек с целью максимизации радиуса текущего шара. Для отыскания направления сдвига строится супердифференциал функции, равной максимальному радиусу элемента упаковки с центром в текущей точке. Выведена формула, позволяющая определить направление максимального роста данной функции. Разработанные алгоритмы реализованы в виде программного комплекса для построения упаковок шаров в компакт. Выполнен численный эксперимент, в ходе которого рассмотрено несколько примеров. Построены упаковки шаров разного радиуса для тел различной формы: куба, шара, цилиндра.
Ключевые слова: упаковка, шар, оптимизация, обобщенная зона Дирихле, производная по направлению, супердифференциал, оптико-геометрический подход
СПИСОК ЛИТЕРАТУРЫ
1. Castillo I., Kampas F.J., Pinter J.D. Solving circle packing problems by global optimization: Numerical results and industrial applications // European J. Operat. Research. 2008. Vol. 191, no. 3. P. 786–802. doi: 10.1016/j.ejor.2007.01.054
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 Appl. Math. 1996. Vol. 67, no. 1–3. P. 127–135. doi: 10.1016/0166-218X(95)00014-I
3. Wang J. Packing of unequal spheres and automated radiosurgical treatment planning // J. Combinator. Optim. 1999. Vol. 3, no. 4. P. 453–463. doi: 10.1023/A:1009831621621
4. Hales T. Cannonballs and honeycombs // Notices of the American Math. Soc. 2000. Vol. 47. P. 440–449.
5. Chernov N., Stoyan Yu., Romanova T. Mathematical model and efficient algorithms for object packing problem // Computational Geometry. 2010. Vol. 43, no. 5. P. 535–553. doi: 10.1016/j.comgeo.2009.12.003
6. Stoyan Y.G., Scheithauer G. Yaskov G.N. Packing Unequal Spheres into Various Containers // Cybernetics Syst. Anal. 2016. Vol. 52, no. 3. P. 419–426. doi: 10.1007/s10559-016-9842-1
7. Khlud O.M., Yaskov G.N. Packing homothetic spheroids into a larger spheroid with the jump algorithm // Control, Navigation and Communication Systems. 2017. Vol. 6, no. 46. P. 131–135.
8. Kubach T., Bortfeldt A., Tilli T., Gehring H. Greedy algorithms for packing unequal spheres into a cuboidal strip or a cuboid // Asia Pacific J. Operat. Research. 2011. Vol. 28. P. 739–753. doi: 10.1142/S0217595911003326
9. Huang W.Q., Li Y., Akeb H., Li C.M. Greedy algorithms for packing unequal circles into a rectangular container // J. Operat. Research Soc. 2005. Vol. 56, no. 5. P. 539–548. doi: 10.1057/palgrave.jors.2601836
10. Hifi M., Yousef L. Width beam and hill-climbing strategies for the three-dimensional sphere packing problem // Annals of Computer Science and Information Systems, vol. 2: Proc. Federated Conf. on Computer Science and Information Systems. Warsaw, 2014. P. 421–428. (Ser. Polish Information Processing Society). doi: 10.15439/2014F284
11. Zeng Z.Z., Huang W.Q., Xu R.C., Fu Z.H. An algorithm to packing unequal spheres in a larger sphere // Advanced Materials Research. 2012. Vol. 546–547. P. 1464–1469. doi: 10.4028/www.scientific.net/AMR.546-547.1464
12. 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. Vol. 4. P. 126–133. doi: 10.2197/ipsjtrans.4.126
13. Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычисл. методы и программирование. Т. 16, вып. 3. 2015. С. 307–317.
14. Ушаков В.Н., Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок в эллипсы // Вест. ЮУрГУ. Сер. Мат. моделирование и программирование. 2017. Т. 10, no. 3. С. 67–79. doi: 10.14529/mmp170306
15. 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. Vol. 51, no. 32. P. 782–787. doi: 10.1016/j.ifacol.2018.11.450 .
16. Лебедев П.Д., Лавров Н.Г. Алгоритмы построения оптимальных упаковок в эллипсоиды // Изв. Ин-та математики и информатики УдГУ. 2018. Т. 52. C. 59–74. doi: 10.20537/2226-3594-2018-52-05
17. Тот Л.Ф. Расположения на плоскости, на сфере и в пространстве. Москва: Физматлит, 1958. 365 c.
18. Субботин А.И. Обобщенные решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. Москва; Ижевск: Ин-т компьютерных технологий, 2003. 336 с.
19. Демьянов В.Ф., Васильев Л.В. Недифференцируемая оптимизация. Москва: Наука, 1981. 384 с.
20. Половинкин Е.С., Балашов М.В. Элементы выпуклого и сильно выпуклого анализа. Москва: Физматлит, 2004. 416 с. ISBN: 5-9221-0499-3.
21. Tatarevic M. On limits of dense packing of equal spheres in a cube: [e-resource]. arXiv:1503.07933 [cs.CG]. 2015. 9 p.
22. Stoyan Y.G., Yaskov, G. Packing congruent hyperspheres into a hypersphere // J. Global Optim. 2012. Vol. 52, no. 4. P. 855–868. doi: 10.1007/s10898-011-9716-z
23. Stoyan Yu.G., Yaskov, G. Packing identical spheres into a cylinder // Intern. Trans. Oper. Research. 2010. Vol. 17, no. 1. P. 51–70. doi: 10.1111/j.1475-3995.2009.00733.x
24. Бухаров Д.С., Казаков А.Л. Программная система “Виголт” для решения задач оптимизации, возникающих в транспортной логистике // Вычислительные методы и программирование: новые вычислительные технологии. 2012. Т. 13, № 2. С. 65–74.
Поступила 26.03.2020
После доработки 7.05.2020
Принята к публикации 18.05.2020
Лебедев Павел Дмитриевич
канд. физ.-мат. наук, старший науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН;
Уральский федеральный университет
г. Екатеринбург
e-mail: pleb@yandex.ru
Казаков Александр Леонидович
д-р физ.-мат. наук, главный науч. сотрудник
Институт динамики систем и теории управления имени В.М. Матросова СО РАН
г. Иркутск
e-mail: kazakov@icc.ru
Лемперт Анна Ананьевна
канд. физ.-мат. наук, ведущий науч. сотрудник
Институт динамики систем и теории управления имени В.М. Матросова СО РАН
г. Иркутск
e-mail: lempert@icc.ru
Ссылка на статью: П.Д. Лебедев, А.Л. Казаков, А А. Лемперт. Численные методы построения упаковок из различных шаров в выпуклые компакты // Тр. Ин-та математики и механики УрО РАН. 2020. Т.26, № 2. С. 173-187
English
P.D. Lebedev, A.L. Kazakov, A.A. Lempert. Numerical methods for the construction of packings of different balls into convex compact sets
The problem of an optimal packing of incongruent balls into a convex compact set is studied. We consider sets of balls whose radii are proportional to a specified parameter r. The aim is to maximize r. The maximum possible number of different types of balls is three. The problem belongs to the class of NP-hard problems and is solved numerically. We propose algorithms based on partitioning the given compact set into zones of influence of the centers of the elements (generalized Dirichlet zones). The partition is constructed using the optical-geometric approach developed by the authors earlier. A preliminary result is obtained and then improved by a geometric algorithm based on a step-by-step shift of points aimed at maximizing the radius of the current ball. To find the shift direction, we construct the superdifferential of the function equal to the maximum radius of a packed ball centered at the current point. We derive a formula for the maximum growth direction of this function. The developed algorithms are implemented as a software complex for the construction of a ball packing of a compact set. A numerical experiment was carried out for several examples. Packings with balls of different radii are constructed for containers of different shapes: a cube, a sphere, and a cylinder.
Keywords: packing, sphere, optimization, generalized Dirichlet zone, directional derivative, superdifferential, optical-geometric approach
Received March 6, 2020
Revised May 7, 2020
Accepted May 18, 2020
Funding Agency: P.D.Lebedev’s research is supported by the Russian Science Foundation (project no. 19-11-00105), A.L.Kazakov’s research is supported by the Russian Foundation for Basic Research (project no. 18-07-00604), and A.A.Lempert’s research is supported by the Russian Foundation for Basic Research (project no. 20-010-00724).
Pavel Dmitrievich Lebedev. Cand. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, Ural Federal University, 620083 Russia, e-mail: pleb@yandex.ru
Alexander Leonidovich Kazakov. Dr. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: kazakov@icc.ru
Anna Ananievna Lempert. Cand. Phys.-Math. Sci., Matrosov Institute for System Dynamics and Control Theory, Siberian Branch of the Russian Academy of Sciences, Irkutsk, 664033 Russia, e-mail: lempert@icc.ru
Cite this article as: P.D. Lebedev, A.L. Kazakov, A.A. Lempert. Numerical methods for the construction of packings of different balls into convex compact sets. Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 2, p p. 173–187.
[References -> on the "English" button bottom right]
