Метод декомпозиции для задачи размещения антенн на стадионе

Рассматривается задача размещения антенн на стадионе. Стадион разделён на секторы, и на каждый сектор назначается некоторое число антенн связи. Пользователи должны получать сигнал определённого качества от антенн, назначенных на их сектор. Задача состоит в том, чтобы выбрать места размещения антенн, их типы, углы направления и назначения на сектора так, чтобы максимизировать три критерия качества решения: среднее отношение сигнал/помехи (signal to interference ratio, SIR), количество клиентов с хорошим качеством сигнала и согласованность назначения. Вычисление качества сигнала производится при помощи имитационной модели. В работе представлена трехэтапная эвристическая схема для решения задачи. Она использует конструктивную эвристику, процедуру локального улучшения и эвристику на основе декомпозиции задачи по секторам с использованием модели целочисленного линейного программирования. Проведены численные эксперименты на тестовых примерах с 94 антеннами 7 типов, 19 секторами и 4426 пользователями. На данных примерах удалось за 2 ч улучшить предоставленные базовые решения и получить решения, сравнимые с запуском метаэвристического пакета на 24 ч. Табл. 2, ил. 3, библиогр. 17.