Исследование эффективности алгоритма оптимизации потока воздушных судов на посадку

Рассмотрена задача оптимизации последовательности приземления воздушных судов. Представлены формальная постановка задачи формирования оптимальной очереди воздушных судов на посадку, основные ограничения и целевые функции. С целью получения решения в режиме реального времени проиллюстрированы способы оптимизации исходной последовательности и предложен эвристический алгоритм приближенного решения задачи. В качестве исходной последовательности для работы алгоритма выбрана последовательность, при которой воздушные суда приземляются в порядке прибытия. В процессе применения алгоритма исходное решение, соответствующее исходной последовательности, не может быть ухудшено. Проведены вычислительные эксперименты с целью исследования эффективности предложенного алгоритма. Сравнены времена счета и качество исходного решения, эвристического решения, полученного при помощи предлагаемого эвристического алгоритма, и оптимального решения, полученного при помощи стандартного пакета CPLEX. Отмечено, что для задачи большой размерности (при большом числе воздушных судов) оптимальное решение получить не удается, поэтому эвристическое решение сравнивалось с исходным. Тесты для интенсивных потоков воздушных судов генерировались случайным образом. Предложенный алгоритм позволил за приемлемое время получать решения задачи либо оптимальные (30–52% случаев), либо значительно улучшающие исходное решение.