Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой

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