RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2021, том 28, выпуск 4, страницы 70–89 (Mi da1286)

Оптимизация размещения взаимосвязанных объектов на параллельных линиях с запрещёнными зонами

Г. Г. Забудскийa, Н. С. Веремчукb

a Институт математики им. С. Л. Соболева, пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
b Сибирский государственный автомобильно-дорожный университет, пр. Мира, 5, 644080 Омск, Россия

Аннотация: Приводится обзор постановок, моделей и методов решения задачи размещения взаимосвязанных прямоугольных объектов на параллельных линиях с запрещёнными зонами. Центры объектов связаны коммуникациями между собой и с зонами. Необходимо разместить объекты вне зон таким образом, чтобы суммарная стоимость связей объектов между собой и с зонами была минимальной. Основное внимание уделяется задаче на линии. Для нескольких линий связи прокладываются через виадук. Построены модели в теоретико-графовой формулировке и формулировке частично-целочисленного программирования с булевыми переменными. Найдены свойства, позволяющие рассматривать задачу как дискретную и декомпозировать её на ряд задач меньшей размерности. Разработаны алгоритмы поиска точного и приближённого решений, выделены полиномиально разрешимые случаи. Приведены результаты численных экспериментов. Библиогр. 32.

Ключевые слова: дискретная оптимизация, задача размещения, запрещённые зоны.

УДК: 519.658

Статья поступила: 03.06.2021
Переработанный вариант: 02.07.2021
Принята к публикации: 05.07.2021

DOI: 10.33048/daio.2021.28.717



© МИАН, 2025