Мы все любим мечтать, особенно когда речь идет о посещении новых мест или возвращении в любимые места.
Нет ничего более вдохновляющего, чем чувство предвкушения запланированного мероприятия, и оно омрачается лишь наличием организационных вопросов, в частности, выбора и покупки билетов на самолет. И почему-то внутренне мы всегда откладываем этот вопрос или перекладываем его на туроператоров, метапоисковики или другие агрегаторы.
В практике каждого бывали ситуации, когда на экране выдавалось сообщение: «К сожалению, по вашему запросу ничего не найдено.
Возможно, будут рейсы и в другие дни».
Как это часто бывает, не всегда в ответ на запрос на поиск маршрута выдается желаемый результат с перелетом, который сразу переходит к оформлению заказа.
Мы начинаем переходить с сайта на сайт, чтобы получить удовлетворительный ответ. Возникновение подобных случаев связано с отсутствием прямого сообщения или заранее предусмотренными комбинированными (стыковочными) маршрутами, либо предлагались маршруты с пересадками, которые включали время ожидания следующего рейса более 5-6 часов, или даже весь день.
Как получается, что при всем многообразии авиакомпаний мы получаем ответы, которые не всегда нас удовлетворяют, и вообще как алгоритмически устроены механизмы поиска вариантов маршрутов? В этом вопросе нам на помощь приходит прикладная математика с использованием алгоритмов и критериев оценки.
Карта аэропортов мира
Я довольно давно решаю логистические задачи, и когда передо мной встала задача построить поисковую систему, которая бы искала оптимальные маршруты, она показалась мне довольно тривиальной.
По опыту я мог заранее сказать, что ее можно решить достаточно простыми методами и за сравнительно короткое время.
Однако если бы все было так просто, то этой статьи бы не появилось.
Поэтому, включившись в работу, через некоторое время я понял, что это не так уж и тривиально.
Отправной точкой, как это часто бывает в путешествиях, и именно такой подход я выбрал, стало решение построить транспортную сеть в виде графа.
Транспортная сеть изначально включала данные об аэропортах, авиакомпаниях, расписаниях их рейсов и показателях времени стыковок.
За основу было принято, что вершиной графа считаются аэропорты, а ребрами — рейсы между ними.
В результате у нас получился костяк, как скелет, на основе которого мы начали навязывать график, имеющий свои особенности: время отправления и прибытия.
Причем движение по граням всегда возможно только в определенное время, которое характеризуется частными вариантами решения задачи:
- минимальное время в пути;
- минимальное (или проще говоря адекватное) количество трансплантаций;
- временной интервал пересадки с одного рейса на другой при выборе сложных маршрутов.
Отсюда следует, что использование критериев накладывает определенные условия на расчет требуемых вариантов маршрута.
Помимо трех перечисленных выше, в расчет входит использование категорий классов обслуживания (первый, бизнес, эконом), стоимости, количества пассажиров и их категорий, а также наличие ряда дополнительных услуг, влияющих на результат. .
Таким образом, это полностью стало укладываться в мою концепцию решения задачи методом многокритериальной оптимизации (многокритериальной оптимизации), а именно нахождение кратчайшего пути по нескольким критериям (MOSP — multi-objective shortest path).
Но, как всем известно, чтобы проверить одну гипотезу, необходимо предъявить ряд других.
В качестве еще одного варианта решения проблемы рассматривалось использование нелинейного программирования.
Учитывая, что дуги графа взвешены векторами, решение задачи можно свести к квадратичному (нелинейному) программированию.
И все было бы идеально, если бы не тот факт, что векторы, по сути, имеют только две характеристики: длину и проекцию на оси координат, что означает наличие в целевой функции переменных со степенью не более двух.
Однако в моем случае компоненты векторов «конфликтуют» друг с другом, что противоречит нелинейному (квадратичному) программированию.
Например: «конфликт» может быть связан с тем, что на каждом рейсе есть определенная вместимость самолета и продать на него больше мест невозможно.
Из-за наличия «конфликтов» от варианта решения задачи с помощью нелинейного программирования пришлось отказаться в пользу того же многокритериального программирования.
Проанализировав варианты решения задачи, я остановился на классическом варианте декомпозиции со следующими частями:
- поиск по расписанию всех «кратчайших» маршрутов от пункта отправления до пункта прибытия;
- поиск среди «кратчайших» путей наиболее «оптимального» по критериям.
Расширенная во времени модель
Расширенный во времени граф — это ориентированный граф.Дуги такого графа — это направления пунктов вылета и прибытия рейсов, а вершины — слоты (время взлета и посадки) рейсов.
Использование расширенной во времени модели заключается в расширении исходного графа аэропортами с вершинами и дугами, отражающими маршрутные связи путем объединения аэропортов между собой в соответствии с расписаниями рейсов: 
Дуги обозначаются как 
.
Например, дуга соединяет аэропорт 
с аэропортом 
и направлен из
К 
, индекс, разделенный запятой 
показывает, что это не единственный рейс, а третий по счету.
В этом случае каждую дугу можно легко взвесить, например, вес дуги.
можно рассчитать как 
.
Вершины внутри одного аэропорта легко упорядочиваются по показателю времени каждого рейса, а также исходя из времени стыковки внутри аэропорта рейсы соединяются дугами, которые соответствуют имеющемуся времени пересадки с одного рейса на другой.
Преимущество расширенного во времени графа состоит в том, что самый быстрый путь прибытия можно найти за минимальное время, например, с помощью алгоритма Дейкстры.
Недостатком использования этого подхода является многократное увеличение вершин и ребер, что, однако, не влияет на разреженность графа, поскольку увеличение количества ребер пропорционально увеличению количества вершин.
Нестационарная модель
Зависящий от времени граф — это ориентированный граф без дополнительных преобразований исходного графа.Каждая дуга соответствует маршруту с сообщением между аэропортами; дуга имеет специальный набор данных, в том числе параметры о времени отправления и прибытия рейса по маршруту.
Значение, извлеченное из этого набора данных, зависит от точного момента времени, когда осуществляется доступ к данной дуге, отсюда и название «зависимый от времени».
Преимущество нестационарного графика в том, что он позволяет найти путь с наименьшим количеством переходов; недостатком является чрезмерная информационная нагрузка на каждую дугу.
Мультиграф
Мультиграф – это ориентированный граф с набором характеристик, присущих расширенным и нестационарным моделям.
Дуг между аэропортами такое же, как и в расширенной во времени модели, но эти дуги «взвешены» временем вылета и прибытия, и время стыковки между рейсами в каждом аэропорту придется постоянно и неоднократно рассчитывать.
С другой стороны, в мультиграфовом представлении содержится точно такой же объем информации о полетах, как и в нестационарной модели, но вся эта информация отнесена к множеству дуг.
Поиск пути с наименьшим числом переходов будет выполнен так же просто, как и в нестационарной модели, но при прохождении по одной дуге не учитывается информация других дуг, поэтому после пути с наименьшим числом переходов найден, вам придется пройти этот путь еще раз для расчета информации о других полетах (дугах).
Представление транспортной маршрутизационной сети в виде мультиграфа является «сырым» состоянием для расширенных во времени и нестационарных моделей.
Поиск пути с наименьшим прибытием будет осуществляться с помощью тех же преобразований, характерных для расширенной во времени модели, а поиск пути с наименьшим количеством пересадок будет осуществляться с использованием нестационарной модели.
А это влечет за собой увеличение времени расчета сети.
Однако здесь возникает нюанс, поскольку поиск «кратчайшего» пути по двум критериям в общем случае уже относится к классу NP-трудных задач, а модификация алгоритма Дейкстры выполняет довольно сложные манипуляции с разметкой вершин.
Представление вычислительной сложности задачи представленной мультиграфовой моделью множества маршрутов с аэропортами и рейсами можно рассмотреть с помощью простейшего метода модификации - алгоритма Дейкстры, осуществляющего поиск только оптимальных по Парето путей.
Общая сумма критериев одного оптимального по Парето пути не может быть хуже или лучше, чем другие пути, оптимальные по Парето, для всех критериев одновременно.
Например, набор путей со следующей суммой двух критериев {(30, 10), (20, 20), (10, 30)} будет оптимальным по Парето.
В качестве более наглядного примера рассмотрим работу алгоритма на небольшом графе, дуги которого взвешены двумерными векторами: 
Работа модифицированного алгоритма Дейкстры на таком графе, как и обычный алгоритм для обычного графа, будет состоять из итераций с последовательным удалением вершин, с той лишь разницей, что каждая вершина может иметь не одно Парето-оптимальное значение, а несколько.
Кроме того, необходимо также хранить информацию о происхождении каждого рассчитанного значения суммы.
Учитывая, что в задаче рассматриваются маршруты со связью между аэропортами рейсами, вполне уместно предположить, что дуг между двумя вершинами может быть довольно много, и каждая из них может быть взвешена как минимум трехкомпонентным вектором.
Но с увеличением векторных составляющих может произойти и увеличение Парето-оптимальных путей.
В этом случае почти все дуги между двумя вершинами могут оказаться оптимальными по Парето.
В этом случае в сумме путей будет еще больше путей, оптимальных по Парето.
Это можно увидеть на небольшом мультиграфе, взвешенном двумерными векторами: 
Использование модифицированного алгоритма Дейкстры в такой модели допустимо, так как он может работать и с мультиграфами, но скорость обработки алгоритма зависит от количества вершин.
, и от количества дуг 
.
Для разреженных простых графов и обычного алгоритма сложность порядка 
.
Однако трудно сказать, будет ли полученный мультиграф «разреженным», поскольку в общем случае плотность ребер мультиграфа может быть значительно больше, чем у полного графа.
Если принять во внимание, что число ребер полного графа 
определяется через количество его вершин 
в соответствии с формулой: 
А плотность ребер определяется как: 
Для полных графиков 
, но для мультиграфов значение плотности ребер вообще не ограничено.
Поэтому я пришел к выводу, что найти кратчайший путь можно с помощью алгоритма Дейкстры, а все остальные кратчайшие пути можно найти с помощью алгоритма Йена.
Учитывая, что на этом этапе мы оперируем невзвешенными дугами и можем сразу отбрасывать пути, скажем, за четыре передачи, то поиск одного кратчайшего пути гарантированно будет завершен менее чем за 
.
Учитывая, что данная статья не освещает непосредственные результаты реализации, могу заранее предположить, что модифицированный алгоритм Дейкстры на мультиграфовой модели не будет работать с учетом оптимального временного интервала.
Поэтому перейду непосредственно к решению первой подзадачи, а именно к решению вопроса, связанного с многокритериальной оптимизацией с использованием выбранного мной метода условной оптимизации.
Метод заключается в том, что, несмотря на противоречивость критериев, всегда существует наивысший приоритет, а все остальные имеют приемлемые значения.
В результате оптимизация всей задачи сводится к оптимизации по высшему приоритету.
Особенностью задания является то, что в расчет включены не только прямые рейсы, что всегда значительно упрощает задачу, но и, наоборот, стыковочные или пересадочные рейсы.
Поэтому графовая модель, зависящая от времени, очень подходит для решения задачи, поскольку зачастую количество пересадок не образует более 3-4 отрезков на маршруте.
Временной график, прежде всего, несет информацию о наборе доступных маршрутов в виде рейсов со стыковками между аэропортами.
Затем рассчитывается приблизительное время отправления и прибытия соединения на основе обычного невзвешенного графика.
Все, что необходимо сделать на этом этапе, — это найти все действующие маршруты между аэропортами «А» и «Б» с заранее фиксированным количеством пересадок, например, тремя.
Учитывая, что на этом этапе граф не взвешен, кратчайший путь можно найти с помощью обычного поиска в ширину, а все остальные кратчайшие пути можно найти с помощью алгоритма Йена.
Поскольку поиск в ширину выполняется за линейное время, можно сказать, что время поиска для всех путей с одинаковыми 3 переходами будет линейным.
Оценивая использование алгоритмов поиска оптимальных маршрутов и наличие данных о частоте обновления расписания, можно сказать, что идея заранее рассчитанной матрицы со всеми «кратчайшими» путями по направлениям оправдана.
Конечно, на начальном этапе создания матрицы такое решение приведет к трудоемким расчетам, но в дальнейшем позволит практически мгновенно находить «кратчайшие» пути и быстро вносить коррективы в саму матрицу.
Однако остается вопрос: какие «самые короткие» маршруты с пересадками и пересадками являются «самыми короткими»? В противном случае у нас будет огромный объем данных, которые не позволят нам принять решение.
Набор критериев зачастую сводится к наиболее оптимальному в том или ином случае, а именно:
- минимальное время в пути;
- минимальное количество переводов.
Учитывая, что максимальное количество пересадок варьируется в пределах 3-4, некоторые комбинации рейсов будут сразу исключены, что приведет нас к решению следующей подзадачи – выявлению среди маршрутов наиболее «оптимальных» по типу критериев.
Критериальная система является основной проблемой при создании маршрутов, поскольку понятие «оптимальный» будет зависеть от предпочтений конкретного пассажира, и зачастую он может управлять полученными маршрутами, устанавливая другой набор фильтров только после получения ответа.
на запрос.
И даже если ему предоставить ранжированные маршруты в соответствии с «кратчайшими» путями, результатом будет массив данных, который не позволит пассажиру принять решение и приведет к бесконечному поиску вариантов.
Поэтому формирование массива вариантов маршрута, учитывающего различные комбинации фильтров как в совокупности, так и по отдельности, является чрезвычайно важным параметром, влияющим на всю задачу.
Что тогда нужно учитывать и как? Создание ранжирующих фильтров является весьма трудоемкой задачей, поскольку.
набор фильтров, их количество и степень влияния друг на друга могут существенно изменить результат поиска оптимальных путей в результате разработки алгоритмов поиска.
Тогда в чем же оно могло заключаться? Все мы знаем ключевые параметры полета – информацию об авиакомпаниях, даты со временем вылета/прилета, аэропорты вылета/прилета, смещения часовых поясов, стыковки и время пересадки, но часто забываем о таких данных, как необходимое и достаточное время для прибытия.
в аэропорту или время в пути между аэропортами для осуществления стыковки в случае, когда последующий вылет осуществляется из другого пункта нахождения.
При этом мы не должны забывать о категории наших пассажиров, а также их количестве, чтобы впоследствии предложить не только оптимальный маршрут по времени, но и по цене в зависимости от тарифной политики.
Массив предложений должен вселить определенную степень доверия в каждого путешественника, как бы парадоксально это ни звучало.
Доверие, основанное на математических принципах и заключающееся в предоставлении минимального набора предложений с вариантами маршрутов, учитывающими предпочтения и снижающими риск возникновения форс-мажорных обстоятельств.
И в данном случае форс-мажорными обстоятельствами являются не только вероятность задержки рейса или изменения времени и аэропорта вылета/прилета, но и такие показатели, как природные, техногенные и эпидемиологические ситуации, влекущие за собой полную или частичную отмену рейсов.
Возможность управления данными в наших реалиях каждый раз влечет за собой множество вопросов: все ли учтено, что еще можно добавить.
И в этом стремлении построить сеть транспортных маршрутов возникает парадокс, связанный с тем, что алгоритм должен быть одновременно оптимальным и простым.
Но часто приходится чем-то жертвовать, поэтому сведение исходных критериев к минимальной сумме мне показалось наиболее приемлемым.
Если пойти по пути выбора критериев, то, опуская второстепенные, можно выделить варианты, учитывающие не только все время в пути, стоимость и комфорт, количество пересадок и продолжительность их пересадок, но и, например, , информация о загруженности аэропортов и данные о сообщении между аэропортами при пересадке из одного аэропорта в другой.
Это обосновано тем, что при создании сообщений с учетом наличия в одном городе нескольких аэропортов, имеющих разное сообщение с внешними аэропортами, расчет времени и формирование маршрута будет включать не только авиаперевозки, но и проезд. время, когда возникает такая ситуация.
И они имеют место быть.
Система принятия решений при выборе «оптимальных» маршрутов в ситуациях, когда мы имеем набор наборов критериев, влияющих на предпочтения, является именно тем камнем преткновения, о котором я даже не задумывался на начальных этапах.
Даже доведя их до некоторой систематизации, различий в их применении друг к другу довольно много, поэтому рассмотрим их отдельно.
Комфорт Смысл понятия «комфорт» каждый понимает по-своему, но авиакомпании принимают следующие уровни:
- первый класс;
- Бизнес-класс;
- Эконом-класс.
.
В этом случае сразу возникает проблема, которая связана с неаддитивностью такой величины, т. е.
сумма показателей комфортности двух рейсов не будет отражать их общую комфортность.
Например, есть две комбинации маршрутов:
- первый маршрут с двумя сегментами, первый рейд с комфортом 10, второй с комфортом 1;
- второй маршрут с двумя сегментами, первый рейд с комфортом 6, второй с комфортом 5.
Однако, учитывая необходимость учета суммарной комфортности двух маршрутов, наиболее целесообразно в данной ситуации использовать их средние значения вместе со стандартным отклонением, что позволило бы оценить «разброс» уровней комфортности.
То есть при первоначальном рассмотрении мы обращаем внимание на средний комфорт, а затем, исходя из значения стандартного отклонения, считаем, насколько эти комфорты отличаются друг от друга.
Таким образом, этот критерий распадается на два очень «близких».
Хотя, с другой стороны, даже без тщательного рассмотрения понятно, что предположение о такой «измеримости» уровня комфорта весьма далеко от реальности, ведь уровни классов у нас известны заранее.
А во-вторых, также очевидно, что комфортность всего путешествия находится в некоторой функциональной зависимости от других критериев, например, продолжительности полета, количества пересадок с их продолжительностью, рейтинга авиакомпании и ее авиаперевозок.
флот. Имеет ли смысл ориентироваться на этот критерий – вопрос.
Ведь в основе подхода лежит система учета совокупности «оптимальных» путей.
Поэтому в дальнейшем мы будем использовать представление комфорта в виде двух показателей: среднего арифметического значения показателей комфорта полета и их стандартного отклонения.
Продолжительность трансферов Существует два типа согласования маршрута:
- трансферы (заранее согласованные между авиакомпаниями);
- стыковка.
полет в другой.
Поэтому для объединения рейсов на таком маршруте необходимо рассчитать достаточное время, необходимое для совершения стыковки.
Здесь мы имеем диссонанс, ведь зачастую такие рейсы могут быть исключены из вариантов предложения, но, в связи с наличием такого критерия, возникают ситуации, когда стыковка с временным ожиданием более суток является «оптимальной».
для нашего пассажира.
Поэтому имеет смысл не отбрасывать маршруты со слишком длительными пересадками, поскольку, даже если они и редки, они все равно могут быть востребованы.
Перегруженность аэропорта Показатель загруженности аэропорта можно оценить при расчете «оптимальных» маршрутов с оценкой степени их наполненности на основе продажи билетов на рейсы с учетом участия конкретного аэропорта в маршруте.
Очевидно, что при таком предположении минимальное время стыковки будет иметь некоторую функциональную зависимость от загруженности аэропорта.
Количество передач Количество трансферов само по себе является спорной величиной.
Ведь зачастую именно так можно снизить стоимость всего маршрута.
С другой стороны, есть категория пассажиров, для которых наличие даже одной пересадки создает ряд проблем.
Не следует забывать о ситуациях, когда маршрут с пересадкой является наиболее «оптимальным» в связи с тем, что на нужный маршрут остались дорогие билеты бизнес-класса или, например, остались билеты с тарифом без возможности обмена.
/refund, что влечет за собой возможность отказа от предложенного варианта.
Но в число пересадок входит еще один подкритерий – это вероятность переезда из одного аэропорта в другой.
Поэтому создание стыковок зачастую является сложной задачей, ведь при расчете маршрута необходимо учитывать время на передвижение между аэропортами, а это влечет за собой необходимость заказа билетов на транспорт внутри города для проезда до подпунктов.
Критерии «время в пути» и «стоимость» являются полностью аддитивными величинами, поэтому опираются на прямые показатели с ранговой системой.
И все бы ничего, если бы не необходимость включения общего времени в пути с расчетом времени прибытия в аэропорт или отправления из него в пункт назначения, а также на стыковках с учетом необходимости дополнительных расходов.
для перемещения между аэропортами.
На данном этапе я позволю себе пренебречь этим уточнением.
Иерархическая структура глобальной цели
Предположим, что под определением «оптимальность» следует понимать лучшее всегда и для всех, и не только для пассажиров, но и для авиакомпаний, аэропортов и, возможно, впоследствии, для других поставщиков туристических услуг.В этом случае единственный выход — разбить единую, очень сложную цель на подцели.
Такое разделение может выглядеть так: 
Совершенно очевидно, что для удовлетворения всех сфер интересов потребуется достижение менее «глобальных», но в некоторой степени противоречивых целей.
Как этого добиться? Возможно, это отличная тема для другой статьи.
Но забегая вперед, можно сказать, что разбиение сложной цели на более простые подцели также связано с оптимизацией и теорией графов, а именно с поиском оптимальных иерархических структур.
Система принятия решений довольно тесно связана с такими методами, как критерии Лапласа, Вальда, Сэвиджа и Гурвица, поэтому, имея массив «кратчайших» маршрутов, я не мог не выяснить, какой из них будет наиболее «оптимальным».
на их основе.
Одним из наиболее универсальных подходов к решению задач многокритериальной оптимизации является поиск оптимальных по Парето и Слейтеру решений.
Если оценить массив «кратчайших» маршрутов с помощью критерия оптимальности Слейтера, то оптимальным путем будет тот, который является лучшим по всем критериям одновременно.
Путь считается оптимальным по Парето, если все остальные пути лучше его по какому-то одному параметру, но хуже по другому, т. е.
невозможно улучшить путь хотя бы по одному критерию, не ухудшив его по остальным.
Все решения оптимальности по Парето и Слейтеру можно легко продемонстрировать графически для задачи минимизации с двумя критериями: 
Зелёным цветом обозначено множество точек с параметрами оптимальных критериев Парето, жёлтым – оптимальных по Слейтеру.
Множество оптимальных точек по Слейтеру содержит также множество оптимальных по Парето точек.
В рамках рассматриваемой задачи все эти точки будут представлять собой концы векторов, исходящих из начала семимерного пространства.
В заключение могу сказать, что это лишь верхушка айсберга, позволяющая дать первоначальное представление о том, с чем сталкиваются поисковые системы при создании оптимальных маршрутов.
Теги: #математика #Алгоритмы #Транспорт #авиация
-
Ноутбук Trave-Tm5742Z-P612G32Mn От Acer
19 Oct, 24 -
Условный Рефлекс
19 Oct, 24 -
Йемен
19 Oct, 24 -
Azure Stack: Немного Теории
19 Oct, 24 -
Искусственный Интеллект. Прогноз 2029 Г.
19 Oct, 24
