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