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

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