О задачах упаковок неравных шаров в трехмерном пространстве

Автор(ы): Казаков А.Л., Лемперт А.А., Та Ч.Т.

Выпуск: 87

Рубрика: Математическая теория управления

Год: 2020

Библиография: Казаков А.Л., Лемперт А.А., Та Ч.Т. О задачах упаковок неравных шаров в трехмерном пространстве // Управление большими системами. Выпуск 87. М.: ИПУ РАН, 2020. С.47-66. DOI: https://doi.org/10.25728/ubs.2020.87.3

Дата опубликования: 30.09.2020

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

Аннотация: Статья посвящена построению оптимальных упаковок набора шаров разных радиусов в трехмерное замкнутое множество: требуется найти такое расположение фиксированного числа шаров, чтобы их радиусы были максимальными. Данная проблема является NP-трудной. Для ее решения предложен вычислительный алгоритм, основанный на использовании оптико-геометрического подхода и метода бильярдного моделирования. Применение данного подхода позволяет решать задачи упаковки не только в евклидовом, но и в других метрических пространствах. Так, рассмотрена задача, в которой вместо расстояния между центрами шаров параметром оптимизации является минимальное время перемещения между ними. Подобные постановки нередко возникают при решении задач охраны периметра, когда время перемещения «нарушителя» до охраняемого объекта играет существенно более важную роль, чем пройденное при этом расстояние, а также в логистике, где время доставки имеет первостепенное значение. Алгоритм реализован в виде программного комплекса, с помощью которого проведены вычислительные эксперименты, причем в качестве множества-контейнера выбирались как выпуклые, так и невыпуклые множества. Результаты расчетов позволяют оценить работоспособность и эффективность предложенного алгоритма. Выполнена 3D-визуализация полученных результатов.

Author(s): Kazakov A., Lempert A., Ta T.T.

Article title: On unequal balls packing problem in three-dimensional space

Issue: 87

Year: 2020

Keywords: unequal balls packing, three dimensional space, optical-geometric approach, billiard simulation method, computational algorithm, non-Euclidean metric

Abstract: The article is devoted to the construction of optimal packings of unequal balls in a three-dimensional closed set. It is required to find such an arrangement of a fixed number of balls that their radii are maximal. This problem is NP-hard. To solve it, we propose a computational algorithm based on the optical-geometric approach and billiard modeling. Using this approach allows us to solve packing problems not only in Euclidean, but also in other metric spaces. We consider a problem in which, instead of the distance between the centers of the balls, the optimization parameter is the minimum traveling time between them. Such statements often arise if we consider problems of protecting the perimeter, in which the time of movement of the "intruder" to the protected object plays a much more significant role than the distance traveled, as well as in logistics, where the delivery time is paramount important. The algorithm was implemented, and computational experiments were performed. Both convex and non-convex sets were selected as container sets. The results of calculations allow us to positively assess the efficiency and effectiveness of the proposed algorithm. We performed a 3-D visualization of the results.