Об одном алгоритме построения упаковки конгруэнтных кругов в неодносвязное множество с неевклидовой метрикой
Казаков А.Л., Лемперт А.А., Нгуен Г.Л.

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

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

Название статьи, аннотация и ключевые слова на английском языке

  • Казаков А.Л. – Институт динамики систем и теории управления им. В.М. Матросова СО РАН, ул. Лермонтова, 134, 664033, г. Иркутск; зав. лабораторией, e-mail: kazakov@icc.ru
  • Лемперт А.А. – Институт динамики систем и теории управления им. В.М. Матросова СО РАН, ул. Лермонтова, 134, 664033, г. Иркутск; вед. науч. сотр., e-mail: lempert@icc.ru
  • Нгуен Г.Л. – Иркутский национальный исследовательский технический университет, Институт кибернетики им. Е.И. Попова, ул. Лермонтова, 83, 664074, г. Иркутск; аспирант, e-mail: nguyenhuyliem225@gmail.com