Оптимизация траекторий рейсов с помощью 3 методов: метод полного перебора, генетический алгоритм и метод муравьиной колонии (реализация на python)

В простейшем случае задачу составления оптимального плана полетов можно свести к поиску оптимальной 4D траектории для каждого из N рейсов между M аэропортами. Для сравнения эффективности алгоритмов построим упрощенную модель движения ВС. Будем считать, что все ВС имеют одинаковые характеристики и при наборе высоты и снижении движутся п
траекториям, имеющим одинаковый фиксированный наклон. Предполагаетс
также, что все рейсы, принадлежащие одному и тому же потоку отправления-назначения, запрашивают один и тот же эшелон, и что их предпочтительным маршрутом является прямой маршрут от пункта отправления до пункт
назначения
В описанной упрощенной модели необходимо назначить только одну 4
траекторию для каждого потока отправления-назначения. Такая траектори
является просто последовательностью сегментов: 1) набор высоты (отрезок
фиксированным наклоном), 2) полет на эшелоне (несколько сегментов большог
круга – ортодромии – или один сегмент, если не требуется смена курса)
3) снижение (отрезок с фиксированным наклоном). При этом мы такж
пренебрегаем погодными условиями
Один из возможных способов построения отдельных траекторий дл
потоков воздушного движения состоит в том, чтобы рассматривать потоки ка
упорядоченную последовательность, учитывая такой критерий, как количеств
полетов на поток. В этом последовательном подходе (n+1)-я траектория строитс
так, чтобы избежать потенциальных конфликтных ситуаций (ПКС) с
предыдущими траекториями. Как следствие, рейсы с наивысшим приоритето
получают траектории с минимальным количеством промежуточных точек,
которых происходит смена курса
ПКС между двумя ВС – это ситуация, при которой без изменени
траектории или времени пролета данного участка маршрута произойдет опасно
сближение ВС
В качестве целевой функции, подлежащей минимизации, можно взять сумм
длин получившихся траекторий (при условии соблюдения описанны
ограничений на вид каждой траектории и отсутствие ПКС с предыдущим
траекториями). Также можно накладывать штраф за каждое изменение курс
и/или за каждое сближение ВС (приводящее к ПКС при достаточно мало
отклонении от заданной 4D траектории по координатам или времени)
В качестве начальной и конечной точки каждой траектории берутс
географические координаты аэропортов вылета и назначения, в качеств
промежуточных точек смены курса – навигационные точки, заданные своим
географическими координатами (долгота и широта). Множество навигационны
точек представлено в виде взвешенного полного связного неориентированног
графа. Особенности пролета навигационных точек при смене курса в данно
упрощенной модели не учитываются (считаем, что смена курса происходи
мгновенно)
Необходимо сравнить эффективность алгоритмов.