УДК 514.174.2
MSC: 05B40, 28A78, 52C15, 52C26
DOI: 10.21538/0134-4889-2018-24-2-141-151
Полный текст статьи
Работа выполнена при поддержке РФФИ (проекты № 18-01-00221, № 18-07-00604, № 16-06-00464).
Рассматривается задача о построении оптимальной упаковки из фиксированного числа $n>1$ кругов в общем случае различного радиуса в плоское компактное множество $M$. Считается, что для каждого элемента упаковки задано положительное число такое, что радиус круга равен его произведению на общий для всей упаковки параметр $r$. Критерием оптимальности выбран максимум $r$, что приводит в том числе и к увеличению плотностиупаковки - отношения ее площади к площади фигуры $M$. Основу метода решения задачи составляет итерационное изменение координат центров элементов упаковки $S_n$, дающее возможность увеличивать радиусы кругов. Разработанные вычислительные процедуры реализуют имитацию отталкивания центра каждого элемента упаковки от близко лежащих других центров и от границы множества $M$. Исследованы дифференциальные свойства функции двух переменных $(x,y)$, значение которой равно максимальному радиусу круга упаковки, располагающегося с центром в точке $(x,y)$. При это координаты центров остальных элементов упаковки считаются фиксированными. При программной реализации используется конструкция чебышевского центра компактного множества. Создан программный комплекс, с его помощью рассмотрен ряд примеров для множеств $M$ различной геометрии. Выполнена визуализация полученных результатов.
Ключевые слова: задача об упаковке кругов, оптимизация, чебышевский центр, супердифференциал, итерационный алгоритм.
СПИСОК ЛИТЕРАТУРЫ
1. Красовский Н.Н., Субботин А.И. Позиционные дифференциальные игры. М.: Наука, 1974. 456 с.
2. Conway J., Sloane N. Sphere packing. Lattices and groups. N Y: Springer Science and Business Media, 1999. 706 p. doi 10.1007/978-1-4757-2016-7 .
3. Hifi M., M’Hallah R. A literature review on circle and sphere packing problems: Models and methodologies // Advances Oper. Research. 2009. Vol. 2009. P. 1–22. doi 10.1155/2009/150624 .
4. Казаков А.Л., Лемперт А.А. Об одном подходе к решению задач оптимизации, возникающих в транспортной логистике // Автоматика и телемеханика. 2011. № 7. C. 50–57.
5. Kazakov A., Lempert A. On mathematical models for optimization problem of logistics infrastructure. Intern. J. of Artificial Intelligence. 2015. Vol. 13, iss. 1, pp. 200–210.
6. Казаков А.Л., Лебедев П.Д. Алгоритмы построения оптимальных упаковок для компактных множеств на плоскости // Вычислит. методы и программирование. Т. 16, вып. 3. 2015. С. 307–317.
7. Лебедев П.Д., Успенский А.А. Алгоритмы построения оптимальных упаковок в трехмерном евклидовом пространстве // Modern Problems in Math. and its Appl.: Proc. 47th Intern. Youth School-Conf. Yekaterinburg, 2016. CEUR Workshop Proc. Vol. 1662. С. 84–93.
8. Яськов Г.Н. Метод решения задачи упаковки разных кругов с выбором перспективных начальных точек // Збiрник наукових праць Харкiвського нацiонального унiверситету Повiтряних Сил. 2010. №3 (25). С. 119–122.
9. Lopez C., Beasley J. A formulation space search heuristic for packing unequal circles in a fixed size circular container // European J. Oper. Research. Vol. 251, no. 1. P. 64–73. doi 10.1016/j.ejor.2015.10.062 .
10. Kubach T., Bortfeldt A., Gehring H. Parallel greedy algorithms for packing unequal circles into a strip or a rectangle // Central European J. Oper. Research. 2009. Vol. 17, no. 4. P. 461–477. doi 10.1007/s10100-009-0103-5 .
11. Zeng Z., Yu X., Chen M., Liu Yu. A memetic algorithm to pack unequal circles into a square // Comput. Oper. Research. 2018. Vol. 92. P. 47–55. doi: 10.1016/j.cor.2017.09.013 .
12. Kazakov A.L., Lempert A.A., Le Q.M. An Algorithm for packing circles of two types in a fixed size container with non-euclidean metric // CEUR Workshop Proc. 2017. Vol. 1975. P. 286–297.
13. Субботин А.И. Обобщенные решения уравнений в частных производных первого порядка. Перспективы динамической оптимизации. М.; Ижевск: Ин-т компьютерных технологий, 2003. 336 с.
14. Демьянов В.Ф. Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981. 384 с.
15. Демьянов В.Ф. Рубинов. А.М. Основы негладкого анализа и квазидифференциальное исчисление. М.: Наука, 1990. 432 с.
16. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. М.: Наука, 1986. 326 с.
17. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985. 335 с.
18. Гаркави А.Л. О чебышевском центре и выпуклой оболочке множества // Успехи мат. наук. 1964. Т. 19, вып. 6. С. 139–145.
19. Тот Л. Ф. Расположения на плоскости, на сфере и в пространстве. М.: Гос. изд-во физ.-мат. лит., 1958. 365 c.
Поступила 15.03.2018
Лебедев Павел Дмитриевич
канд. физ.-мат. наук
науч. сотрудник
Институт математики и механики им. Н.Н. Красовского УрО РАН,
г. Екатеринбург
e-mail: pleb@yandex.ru
Казаков Александр Леонидович
д-р физ.-мат. наук
главный науч. сотрудник
Институт динамики систем и теории управления им. В.М. Матросова СО РАН,
г. Иркутск
e-mail: kazakov@icc.ru
English
P.D. Lebedev, A.L. Kazakov. Iterative methods for the construction of planar packings of circles of different size
We consider the problem of constructing an optimal packing of a fixed number $n>1$ of circles, generally, of different radii in a planar compact set $M$. It is assumed that a positive number is given for each element of the packing such that the radius of the circle equals the product of this number by a parameter $r$, which is common to the whole package. The optimality criterion is the maximum of $r$, which leads, in particular, to an increase in the packing density, which is the ratio of the area of the packing to the area of $M$. In the proposed solution method, we iteratively change the coordinates of the centers of the packing elements $S_n$, which makes it possible to increase the radii of the circles. The developed computational procedures imitate the repulsion of the center of each element of the packing from nearby centers of other elements and from the boundary of $M$. We study the differential properties of a function of two variables $(x,y)$ whose value is the maximum radius of the circle of the packing centered at the point $(x,y)$, where the centers of the remaining elements are assumed to be fixed. The software implementation employs the notion of Chebyshev center of a compact set. A software complex is created and a number of examples are considered for sets $M$ of different geometry with the use of this complex. The results are visualized.
Keywords: circle packing problem (CPP), optimization, Chebyshev center, superdifferential, iterative algorithm.
The paper was received by the Editorial Office on March 15, 2018.
Funding Agency:
Russian Foundation for Basic Research (Grant Numbers: 18-01-00221, 18-07-00604, 16-06-00464).
Pavel Dmitrievich Lebedev, Cand. Sci. (Phys.-Math.), Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia,
e-mail: pleb@yandex.ru
Aleksandr 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
[References on the English button bottom right]
