Содержание к диссертации
Введение
Глава 1. Обзор алгоритмов и информационных систем на пассажирском транспорте . 7
1.1 Проблема поиска пути проезда на пассажирском транспорте 7
1.2 Справочное обслуживание пассажиров в россии 7
1.2.1 Система «экспресс» 9
1.2.2 Система «СИРЕНА» 10
1.2.3 Другие источники справочной информации в России 10
1.3 Зарубежный опыт разработки информационных систем на транспорте 11
1.4 Алгоритмы поиска кратчайшего пути на графе 14
1.5 Алгоритм для поиска пути в пространстве 18
1.6 Алгоритмы поиска маршрута на пассажирском транспорте 19
1.6.1 Подходы к поиску маршрута и формулировка задачи 19
1.6.2 Базовое моделирование: Задача наискорейшего прибытия 23
1.6.3 Моделирование реальной задачи 25
1.6.4 Многокритериальная оптимизация 29
1.6.5 Приближенные подходы при многокритериальной оптимизации 31
1.6.6 Производительность известных алгоритмов поиска 34
1.7 Методы ускорения алгоритмов поиска на транспорте 35
1.8 Архитектуры построения распределенных систем кэширования 38
1.8.1 Кэширование данных 39
1.8.2 Обзор архитектур кэширования в интернет 41
1.8.3 Аналитическая модель распределенного кэширования 44
1.8.4 Сравнение архитектур кэширования и ограничения моделей 46
1.9 Постановка задачи поиска пути 47
Глава 2. Разработка алгоритмов и архитектуры информационно-справочной системы 50
2.1 Разработка оригинального алгоритма поиска 50
2.1.1 Алгоритм оптимистического поиска на графе 51
2.1.2 Оригинальное представление графа в памяти компьютера 52
2.1.3 Методы ускорения алгоритма поиска на графе 53
2.1.4 Препроцессинг данных в реальном времени 56
2.1.5 Выбор наискорейшего пути из найденного набора 57
2.1.6 Проверка наличия свободных мест 58
2.2 Взаимодействие с источниками данных 58
2.2.1 Постановка задачи о взаимодействии с источником 59
2.2.2 Вы бор архитектуры в зависимости от параметров 61
2.3 Цикл обслуживания запроса 63
2.4 Аналитический выбор архитектуры справочной системы 66
2.4.1 Постановка задачи выбора архитектуры 68
2.4.2 Аналитическая модель 69
2.4.3 Сетевой уровень запроса 71
2.4.4 Частота запросов к серверам 72
2.4.5 Время передачи документа 72
2.4.6 Время полной обработки запроса 73
Глава 3. Программная реализация информационно-справочной системы 75
3.2 Специализированная база данных 77
3.3 Средства подготовки исходных данных 78
3.4 Средства импорта данных в базу данных системы 82
3.4.1 Загрузка географических данных 83
3.4.2 Импорт данных о расписаниях 85
3.4.3 Корректировка данных в графе 85
3.5 Реализация алгоритма поиска. модуль ядра 87
3.6 Программа управления системой 88
3.7 Подсистема интеграции с внешними системами 89
3.7.1 Описание процесса взаимодействия 89
3.7.2 Интеграция с системой «ЭКСПРЕСС». Эмулятор терминала 91
3.7.3 Программа контроля процесса взаимодействия 92
3.8 Интернет-портал доступа к справочной системе 92
Глава 4. Анализ результатов поиска и исследование информационно-справочной системы 100
4.1 Сравнение результатов поиска с известными маршрутами проезда 100
4.1.1 Поиск прямого маршрута 100
4.1.2 Поиск пути проезда с пересадкой на одном виде транспорта 101
4.1.3 Поиск пути с пересадкой на нескольких видах транспорта 102
4.1.4 Поиск пути с пересадкой с учетом даты поездки 103
4.1.5 Поиск пути с пересадкой вузле с несколькими станциями 103
4.1.6 Поиск пути с несколькими пересадками и с фильтрацией по виду транспорта 104
4.2 Исследование разработанной информационно-справочной системы 106
4.2.1 Плотность графа железных дорог 106
4.2.2 Длина маршрутов поездов дальнего следования 108
4.2.3 Распределение количества пунктов назначения от числа пересадок... 109
4.2.4 Распределение количества пунктов назначения от расстояния 111
4.2.5 Зависимость количества запросов от расстояния между пунктами... 113
4.2.6 Суммарное время обработки запросов информационно-справочной
системой 114
4.2.7 Зависимость времени обработки запроса от расстояния 115
4.3 Производительности модификаций алгоритма поиска 116
Заключение 118
Выводы по теме диссертации 118
- Другие источники справочной информации в России
- Приближенные подходы при многокритериальной оптимизации
- Оригинальное представление графа в памяти компьютера
- Средства импорта данных в базу данных системы
Введение к работе
Первые электронные справочные системы по расписанию транспорта появились в 80-х годах прошлого века. К настоящему времени уровень созданных автоматизированных систем различен для разных видов транспорта: от региональных систем бронирования и продажи билетов на отдельных автовокзалах до межгосударственных отраслевых систем с тысячами терминалов и десятками центров обработки данных на железнодорожном и воздушном транспорте. На постсоветском пространстве функционируют крупнейшие системы «ЭКСПРЕСС» - на железнодорожном транспорте [63], «СИРЕНА» - на воздушном транспорте [67]. В Европе известны системы HAFAS [13] и EFA [8]. Первая используется многими европейскими железнодорожными компаниями, вторая применяется в основном для обслуживания пригородного сообщения в отдельных регионах Европы. Системы реализованы на разнородной технике, отличаются принципами построения, программной и логической структурой.
Анализ зарубежных и отечественных информационных систем на транспорте выдвигает проблему создания единой информационно-справочной системы с целью повышения качества обслуживания пассажиров. Интегрированная информационно-справочная система позволит объединить информацию из действующих систем бронирования и продажи билетов с целью получения наиболее полной справочной информации о возможности проезда на пассажирском транспорте с учетом пересадок между разными видами транспорта и с учетом наличия свободных мест.
Цель интеграции автоматизированных систем междугородних пассажирских перевозок - предоставление пассажирам подробной справочной информации о возможных путях проезда, внедрение современных телекоммуникационных технологий, повышение эффективности использования транспортных средств.
В настоящее время в Российской Федерации отсутствует возможность справочно-информационного обслуживания пассажиров при поездках с пересадкой на авиационном, автобусном, железнодорожном и других видах транспорта. Это в значительной мере затрудняет возможность качественного обслуживания пассажиров, желающих приобрести билеты на маршруты, связанные с пересадкой с одного вида транспорта на другой. В связи этим назрела необходимость создания в Российской Федерации единой информационно-справочной системы, которая обеспечит пассажиров информацией не только при поездках на отдельных видах транспорта, но и при одновременном использовании железнодорожного, автобусного, авиационного и других видов пассажирского транспорта в одной поездке. Работы по созданию и развитию систем такого класса активно ведутся в США [66], Европе [51] и отдельных странах СНГ [55]. Быстрое развитие информационных технологий, в частности телекоммуникационных сетей, интернет-технологий, геоинформационных технологий и т.д. является объективной базой для реализации такой системы.
Разрабатываемая система должна обеспечивать пассажиров справочной информацией о маршрутах транспорта внутри города, области, страны, включая:
информацию об актуальных расписаниях для каждого вида транспорта;
выбор оптимальных маршрутов по критерию стоимость и продолжительность поездки для пересадочных маршрутов на железнодорожном и автобусном транспорте;
информацию о маршрутах с пересадкой внутри каждого вида транспорта;
информацию о маршрутах транспорта внутри узлов пересадки при необходимости переезда между железнодорожными и автобусными вокзалами;
информацию о пригородных маршрутах подъезда к железнодорожным вокзалам.
Другие источники справочной информации в России
Обратимся к зарубежному опыту разработки справочных систем поиска маршрута с пересадкой, так как в России таких систем просто нет. Наибольшее распространение в Европе получили две системы: HAFAS — на железнодорожном транспорте, EFA - на городском и пригородном транспорте. Эмпирически установлено, что результат справки удовлетворителен для большинства запросов. Тем не менее для некоторых запросов результат поиска оказывается не самым оптимальным. Главной причиной такого поведения является то, что алгоритм поиска внутри системы использует эвристические методы с целью уменьшить пространство поиска и сократить время обработки запроса. Это связано с тем, что системы используются в реальном времени большим числом пользователей. Такие системы не гарантируют оптимального решения.
Описывая зарубежные справочные системы, стоит упомянуть предшественников этих систем. Примерно в 1988 году в Дании и Германии железнодорожные компании начали использование систем электронных расписаний. Так появились системы TRAINS и ARIADNE. Обе системы работали в два этапа, при этом на первом этапе эвристически ограничивалось пространство поиска, поэтому результаты поиска были приемлемыми, но не оптимальными.
Система «TRAINS»
Информационная система TRAINS, которая использовалась датскими железными дорогами (NS) в качестве прототипа, была описана Tulp и Siklossy [37]. Модель системы базировалась на графе, в узлах которого располагались города. Имелось два уровня сети: «статический», который состоял из ребер, стоимость которых определялась расстоянием, и «динамический», где ребра включали информацию о времени прибытия и отправления поездов. Алгоритм использовал статический уровень, чтобы выявить нужную часть графа, без учета информации о времени. После этого путь может быть вычислен модификацией алгоритма Дийкстры. Необходимо отметить, что это обрезание было эвристическим и могло приводить к потере оптимального пути. Методы, которые будут описаны ниже, не допускают такой потери.
Система «ARIADNE»
Бауман и Шмит [2] описали алгоритм, называемый ARIADNE, который можно считать предшественником HAFAS [13], справочной информационной системы, которая в настоящее время используется немецкими железными дорогами Deutsche Bahn AG и многими другими транспортными компаниями по всему миру. Как и в TRAINS алгоритм рассматривает две сети: статический граф, топографически описывающий граф железных дороги, и динамическую сеть включающую информацию о днях курсирования, видах поездов. Алгоритм ARIADNE работает в два этапа. На первом этапе производится поиск подходящего пути в статическом графе с помощью двунаправленного алгоритма Дийкстры. На выходе этого этапа получается подграф транспортной сети, который может быть проанализирован на втором этапе. Необходимо заметить, что при таком подходе оптимальное решение тоже может быть потеряно. На втором этапе динамический подграф используется для вычисления подходящих путей, удовлетворяющих различным критериям: время в пути, стоимость, количество пересадок.
Система «HAFAS» На сегодняшний день HAFAS самая известная в Интернет информационная справочная система на наземном транспорте для больших расстояний. Система используется государственными и частными железными дорогами в 7 странах Европы. Кроме этого, система работает с пригородными маршрутами (около 30 транспортных компаний и 5 региональных транспортных сетей в Германии). Суммарно HAFAS используется в 16 странах и на трех континентах. За годы прошедшие с создания системы, алгоритмы HAFAS непрерывно совершенствовались. Сейчас возможен поиск не только наискорейшего пути, но и путей с низкой стоимостью. В пиковое время сервер Deutsche Bahn AG обслуживает 1,600,000 запросов в час, используя HAFAS-Algorithm. HAFAS работает на нескольких платформах, от TANDEM и IBM мейнфреймов до карманных операционных систем Windows СЕ и Pocket PCs, а также на HP-UX или Linux. Система «EU-SPIRIT»
EU-Spirit - это справочная интернет система для пассажиров в Европе [11]. Она основывается на существующих локальных, региональных и национальных справочных информационных системах, которые соединены посредством разработанных программных интерфейсов. Система позволяет получать справочную информацию для случаев, когда пассажир едет из одного региона в другой, позволяет находить маршруты между остановками, адресами, интересующими точками в различных регионах Европы. Информационная система в текущий момент охватывает следующие страны: Германия, Дания, Люксембург, Швеция.
Основная функция системы - виртуальное соединение существующих информационных систем. Внешние системы соединены через интегрирующие компоненты и таким образом может быть найден общий путь с учетом всех источников информации. Пользователь может войти в систему, используя любую из подключенных информационных систем. Независимые внешние системы взаимодействуют через центральные компоненты:
RODI (Ring Origin Destination Identificator) - блок поиска точек назначения. Компонента предназначена для нахождения точек старта и финиша, введенных пользователем в запросе. Для этого компонента связывается с соответствующими серверами данных.
RCC (Ring connection composer) - блок объединения маршрута. Работа блока заключается в объединении результатов поиска. Блок взаимодействует с серверами внешних информационных систем, которые выступают в качестве пассивных источников данных.
RRDB (Ring Reference database) — база данных системы. В базе данных, в числе прочего, хранится информация обо всех возможных пунктах пересадки между системами. Пункты пересадки - все пункты, где можно произвести пересадки между различными транспортными системами (локальными и межрегиональными)
Данные в базе RRDB необходимы для работы алгоритмов и включают: Таблицы соответствия, географических объектов (станция, остановки, поезда) между разными внешними системами Дополнительная информация о пеших ребрах, которые соединяют платформы, станции или зоны работы различных транспортных компаний в транспортных узлах (например, пеший маршрут от железнодорожной платформы к автобусной остановке) Информация об участвующих в системе серверах (доступность, сервисные возможности систем)
Приближенные подходы при многокритериальной оптимизации
Конечная цель информационной системы предложить пользователю небольшой набор лучших возможных путей. В этом случае поиск всего набора Парето оптимальных решений поднимает две проблемы: (і) не каждое Парето оптимальное решение действительно подходит для пользователя, (іі) многие лучшие пути почти не отличаются. Первая из этих двух проблем может быть решена фильтрацией. Для решения второй проблемы необходимо рассмотрение приближенных Парето оптимальных наборов. Текущие исследования идут в двух направлениях: (1+е) — Парето [27] и концепция е-эффективности [17,42].
Несмотря на множество исследований в области многокритериальной оптимизации [9,10], только недавно было проведено системное изучение сложности задачи построения приближенного набора Парето [27]. (1 + е) - Парето набор Ре это набор подходящих решений, который для любого оптимального решения и любого е 0 имеет решение Ре, которое не далее чем (1 4- е) от оптимального по всем критериям. Хотя эта концепция и не нова (она была ранее использована в контексте многокритериальных кратчайших путей [14,41]), Papadimitriou и Yannakakis в своей работе [27] показали, что для любой многокритериальной задачи оптимизации, существует (1 + е) Парето набор размера Ре = 0((—J ), где Д число битов, необходимых для представления значений целевых функций. В частности Ре может быть получен О і (—J ) вызовами к GAP процедуре, которая решает следующую задачу: дан вектор значений а, необходимо подсчитать решение, которое превосходит а, или выяснить, что для всех критериев нет решения в (1 + е) раз лучше, чем а. Расширение этого метода заключается в том, чтобы проводить постоянную аппроксимацию наименьшего возможного набора Парето. Для случаев двух и трех критериев расширение рассмотрено в [38] и также показано, что для d 3 возникают непреодолимые трудности.
Отдельно от предыдущих результатов есть новая работа на тему улучшенных алгоритмов аппроксимации (FPTAS) для многокритериальных кратчайших путей от Tsaggouris и Zaroliagis [36]. В этой работе представлен новый и достаточно простой алгоритм для создания набора (1 + е) - Парето для многокритериальной задачи кратчайшего пути, который превосходит другие подходы. Алгоритм можно считать обобщением алгоритма Беллмана-Форда. На каждом раунде і для каждого узла v алгоритм поддерживает d-мерную метку, представляющую приближенный набор Парето для всех Парето оптимальных s-v путей с не более чем і ребрами. Когда ребра (u,v) рассматривается в раунде і, алгоритм выполняет (вместо релаксации) операцию extend&merge. Эта специальная операция дополняет метку узла и в раунде і — 1 ребром (и, v) и склеивает результирующий набор с меткой в V, сохраняя решение, которое превосходит все остальные. Этот алгоритм полиномиально ограничивает размер всех меток, в отличие от предыдущего метода, который хранит все не превосходящие решения и таким образом приводит к экспоненциально растущему набору меток.
M"uller-Hannemann и Schnee [20] обобщили эту концепцию также известную как є-эффективности [17, 42] и применили ее к информации о расписаниях. В s-эффективности, решение р превосходит (в свободном Парето смысле) другое решение q если fSjp) + h-iijp.q) fiifl) , для всех 1 і d, и /}(р) + hi(jp,q) fi(q), по крайней мере для одного }, 1 j d, где hi(p,q) подобранная функция релаксации. Идея состоит в том, чтобы сделать больше пар путей взаимно несравнимыми путем переопределения связей превосходства по заданному критерию. Например, если мы не хотим подавлять путь с немного большим временем, скажем, менее чем 5 минут разницы, тогда мы можем определить, что путь А будет превосходить путь В по критерию времени в пути только если время в пути А + 5 минут меньше, либо равно времени В. Еще примеры того как применяется релаксированное доминирование описаны в [20].
В этом подходе используется сервисная функция, которая транслирует (линейно или нелинейно) различные критерии в единую стоимость. Например, обычно можно минимизировать время в пути и длину маршрута; оба критерия могут быть переведены в меру стоимости, где первое переводится линейно, а последнее нелинейно (малое время обычно имеет относительно низкую стоимость, а большое время - значительно большую стоимость). В нормализованном подходе ищется единственный оптимум в наборе Парето (все подходящие решения, которые оптимизируют сервисную функцию). Мы различаем случай, когда все критерии линейно влияют на единую стоимость и случай, когда один или несколько критериев нелинейны.
Прямолинейный подход может быть выражен как относительная важность критериев оптимизации по весу и последующая оптимизация весовой суммы. Этот подход сводит многокритериальную задачу к задаче с одним параметром, которая может быть решена стандартным алгоритмом Дийкстры (используется модель, где каждый критерий неотрицателен и аддитивен). Как частный случай, установка всех весов кроме одного в нулевое значение, делает задачу однокритериальной. Такой подход имеет два серьезных недостатка. Первый, неизбежно будут потеряны хорошие пути, так как подход находит только одно решение (а не все Парето оптимальные). Другой недостаток такого подхода -проблемы выбора подходящих весовых параметров. Каждый пассажир имеет свои предпочтения. И он, либо сама система, может установить параметры неверно, так как никто обычно не знает систему предпочтений конкретного пользователя.
Случай нелинейной сервисной функции наиболее интересный, так как отражает реальную картину при поиске оптимального пути. Опыт показывает, что пассажиры оценивают значения критериев нелинейно [15]: малые значения имеют относительно меньший вес, а большие относительно больший. Также большинство транспортных систем имеют нелинейную структуру оплаты проезда [12]. В конечном счете, самой интересной теоретической моделью является минимизация монотонной нелинейной сервисной функции. В этом случае проблема вычисления оптимального пути сводится к так называемой неаддитивной задаче кратчайшего пути (NASP): имея направленный граф, ребра которого соответствуют d-мерным векторам стоимости, задача состоит в нахождении пути, который минимизирует определенную d-параметрическую функцию стоимости. Не очень давно Tsaggouris и Zaroliagis [36] продемонстрировали первый FPTAS for NASP. В частности, они показали, как FPTAS для многокритериальной задачи можно использовать для любого количества параметров и для более общих сервисных функций, которые включают полиномы ограниченного порядка с неотрицательными коэффициентами. Для многокритериального случая, FPTAS для NASP было независимо представлено в [1]
Лексикографический порядок - еще один способ выбрать одно особое Парето оптимальное лексикографическое решение. Алгоритм Дийкстры работает не только для неотрицательных весов ребер, но и для полуколец [31]. В нашем случае веса ребер и метки узлов из d значений в лексикографическом порядке. В упрощенной версии время-расширенного подхода лексикографически первое решение может быть посчитано для любого d-значений как вес ребер. Например, если d=2, то первый элемент время в пути, а второй - количество пересадок, то среди всех быстрых путей находится один с минимальным числом пересадок. В реальной версии время-расширенного подхода могут быть использованы только те критерии, где первый критерий время в пути. Это ограничение возникает из-за 24-часового цикла и ребер стоянки, принадлежащим каждой станции. Специальный случай - пара весов ребер со временем в пути в качестве первого критерия.
Оригинальное представление графа в памяти компьютера
Алгоритм Дийкстры является точным алгоритмом применимым к данной задаче, но не является достаточно быстрым для практического применения в справочной системе. Необходимо его усовершенствование с целью повышения производительности. В предыдущих главах были описаны несколько методов ускорения поиска применимые к частным задачам на транспортных сетях.
Например, очень эффективен «угловой алгоритм» выдерживающий направление на цель. В этом алгоритме производится препроцессинг(предварительная обработка) графа и дополнение каждого ребра информацией о двух углах. Углы обозначают сектор, в котором находятся все узлы путь, до которых через данное ребро будет кратчайшим. Этот метод успешно применяется для поиска на графе автомобильных дорог. Преимущество этого алгоритма в плане ускорения поиска доказано в работах нескольких авторов [61].
Но укажем причины, по которым данный алгоритм не может быть использован для ускорения оригинального алгоритма. В описываемой реализации информация о ребрах графа вообще не хранится в системе. А использование «углового поиска» потребует создание дополнительной структуры для хранения углов для каждого ребра. В предыдущем параграфе было показано, что это дополнительно потребует хранения десятков миллионов записей. Ведь у каждого транспортного маршрута десятки станций и, следовательно, соединяющих ребер. По одной дороге между соседними пунктами может проходить маршрут сотен поездов. Ребро каждого маршрута потребует отдельного вычисления углов. Объединять ребра разных маршрутов нельзя, так как это приведет к потере информации используемой при поиске на графе. В результате невозможно будет проводить поиск с дополнительной фильтрацией (по классу маршрута, по наличию мест) Использование методов ускорения «угловым поиском» или «ограничивающим прямоугольником» требует препроцессинга. Препроцессинг может длиться сутки даже на современных вычислительных комплексах. Это неприемлемо, когда данные в БД обновляются ежеминутно, поступая в режиме реального времени из внешних справочных систем.
Хотя упомянутые методы ускорения неприменимы, для оригинального алгоритма разработаны специальные методы:
Пересадочный подграф
Методы построения многоуровневых графов для решения задачи поиска пути на железнодорожном транспорте исследованы в [34]. Но там показано, что операция построение дополнительных уровней требует достаточно много времени. Поэтому построение многоуровневых графов неприменимо для задачи, где данные обновляются в реальном времени. Однако в процессе обновления данных о расписаниях, можно анализировать упомянутые в расписании станции и определять потенциальные узлы пересадки. Так если через станцию проходит только один маршрут, то станция заведомо не является станцией пересадки. Такую станцию можно исключить из списка возможных пересадок. Другой случай - все маршруты на рассматриваемой станции присутствуют на предыдущей и последующей станции. Значит, исключение станции из списка пересадок не исключит возможность нахождения оптимального пути. Так как пассажир может совершить пересадку на предыдущей или последующей станции. И такая поездка будет иметь столько же пересадок и такую же продолжительность. Важно, что список станций пересадок обновляется в режиме реального времени и не требует масштабных вычислений.
В результате создается пересадочный подграф меньшего размера. Поиск пути производится на нем значительно быстрее за счет меньшего количества информации, с которой приходится оперировать.
Утверэюдение. Если не существует транспортных маршрутов, которые обгоняют любые другие транспортные маршруты на участке перед исключенной станцией, а после исключенной станции наоборот отстают, то метод ускорения с помощью пересадочного подграфа будет точным.
Балансировка двунаправленным поиском
Пусть необходимо найти путь проезда между А и Б и используется однонаправленный алгоритм Дийкстры. Экспериментально выяснено, что время работы при прямом поиске (из А) и при обратном поиске (из Б) может отличаться в сотни, а то и тысячи раз. Например, если пункт А - Москва, а пункт Б - Дальнегорск (город в Приморском крае), то А (Москва) имеет на три порядка больше смежных станций, чем Б. Поэтому прямой поиск потребует на порядок больше времени.
Балансировка двунаправленным поиском заключается в выборе прямого или обратного поиска на каждом шаге итерации с учетом количества смежных станций. Для работы этого метода по каждому пункту необходима информация о количестве смежных станций. Вычисление такой информации не требует длительного препроцессинга. Данные о количестве смежных станций могут корректироваться в режиме реального времени при обновлении расписаний из внешних систем.
Ускорение последней итерации
Экспериментально выяснено, что время поиска растет экспоненциально от количества пересадок. И последняя итерация поиска требует в несколько раз больше времени, чем все предыдущие. Так как на каждой итерации поиск охватывает все большее количество станций. Поэтому уменьшение длительности последней итерации наиболее эффективно, с точки зрения уменьшения времени работы алгоритма в целом. Для каждой станции вычисляется ограничивающий прямоугольник станций достижимых без пересадок. На последнем шаге итерации используется информация об ограничивающем прямоугольнике каждой станции для выяснения, может ли станция находится на возможном пути или ее заранее можно вычеркнуть. Возникает вопрос, как определить последнюю итерацию. Итерация является последней, если в порядке рассмотрения узлов найден хоть один путь.
Средства импорта данных в базу данных системы
После того как пользователь указал параметры запроса и нажал кнопку «Поиск» в работу вступает главный модуль системы — модуль поиска пути.
На основе выбранных параметров создается программный класс, содержащий все настройки, и передается в класс поиска пути. Используя идентификаторы пунктов назначения и отправления, класс получает базовую информацию о них, как то: географические координаты объектов, тип объектов, класс транспортного узла (железнодорожный, автомобильный). В том числе определяется прямое расстояние между объектами.
После этого алгоритм пытается найти прямой маршрут без пересадок между заданными пунктами. Если прямой маршрут не найден, то алгоритм начинает поиск сложного маршрута. В зависимости от параметров выбирается модификация алгоритма поиска на графе, которая будет использована для оптимистического поиска возможных путей. Алгоритм поиска реализован на языке Transact-SQL в виде процедуры базы данных.
В процедуру передается идентификатор узла отправления и назначения, а также максимальное допустимое количество пересадок. Процедура возвращает таблицу данных, в которой содержится информация о найденных путях проезда.
Таблица данных обрабатывается, и по ней конструируются структуры, описывающие найденные пути проезда. На этом шаге пути программно анализируется, и удаляются дублирующие друг друга пути. Например, процедура базы данных может найти вариант проезда с пересадкой на Казанском вокзале и одновременно с пересадкой в Москве. Так как гипер-узел Москва включает в себя Казанский вокзал, то путь через Казанский вокзал удаляется.
На этом же шаге сравнивается длина найденных путей проезда. Пути сортируются в порядке возрастания длины. Если путей много (по умолчанию 3), то на этом шаге отсекаются слишком длинные пути, путем сравнения с самым коротким путем. (Если длина пути оказывается в 1.5 раза длиннее самого короткого, то он отсекается). При использовании этого эмпирического ограничения алгоритм перестает быть точным, но на практике этого практически не наблюдается. Для такой ошибки должна возникнуть ситуация, что все найденные N путей недопустимы, а отсечение удалило нужный путь.
Если в параметрах поиска явно указывается пункт пересадки, то такой путь не удаляется. Затем алгоритм приступает к анализу каждого из найденных путей. Рассматриваются по порядку все участки пути. Для каждого участка определяется время отправления и прибытия наискорейшего маршрута. По условию ограничений алгоритма, от времени прибытия на последующий пункт определяется временное окно длительностью одни сутки. Если для следующего участка пути найден маршрут, удовлетворяющий временному окну, то аналогично рассматривается последующий
участок пути. Если на следующем участке нет транспортных маршрутов, удовлетворяющих временному окну, то путь считается недопустимым. В результате такого анализа пути вычисляется наискорейшее время прибытия для него.
После того как из списка удалены недопустимые пути, и для каждого доступных путей посчитано наискорейшее время прибытия, список путей снова сортируется. Теперь сортировка производится по критерию времени наискорейшего прибытия. На этом шаге алгоритм эмпирически отсекает слишком долгие пути (если их найдено много), сравнивая их с наискорейшим из них. Теоретически, это снова может привести к потере оптимального пути. На практике это опять же практически не происходит. Так как мала вероятность, что все (несколько) из найденных более быстрых путей недопустимы при последующей фильтрации по наличию мест.
На последнем шаге лучший из найденных путей отправляется на проверку в модуль взаимодействия с внешними системами. Информация о пути дополняется данными о наличии мест. В случае, если путь оказывается недопустим из-за отсутствия мест, в подсистему взаимодействия передается следующий по списку наискорейший путь. Надо заметить, что практически невозможно проверить сразу все пути, так как это повлечет слишком большое количество обращений во внешние системы. В связи с тем, что эти обращения требуют много времени, это нецелесообразно.
Процесс работы подсистемы протекает следующим образом. Когда пользователь отправляет в запрос в систему, то сначала выполняются первые шаги алгоритма поиска: (і) находятся возможные пути проезда, (и) проверяются даты курсирования маршрутов. В итоге имеется набор найденных путей, которые требуют проверки во внешних системах на наличие мест (а для некоторых маршрутов и дней курсирования).
Информационный пакет с найденными путями передается в модуль взаимодействия. Модуль взаимодействия анализирует найденные пути и определяет, для каких маршрутов необходимо произвести уточнение данных, и обращается за ними в подсистему взаимодействия.
В подсистеме сначала производится поиск нужных данных во внутреннем кэше вьшолненных запросов. В этот кэш попадают результаты предыдущих запросов к внешним системам и сохраняются там некоторое время.
Для тех данных, которые не найдены в кэше, подсистема отправляет запрос во внешние системы. Способ отправки запроса зависит от специфики внешней системы. Запрос может быть синхронным или асинхронным.
Если запрос синхронный, то обслуживающий процесс выполняет его немедленно. Происходит online обращение во внешнюю систему по соответствующему протоколу (обычно TCP). Но такой способ взаимодействия подходит только для внешних систем, которые быстро способны обслужить запрос. Так как процесс «зависает» до получения ответа из внешней системы и происходит неэффективное использование ресурсов ИСС.
Поэтому предпочтителен асинхронный способ взаимодействия, который используется в большинстве случаев (например, при взаимодействии с системой ЭКСПРЕСС). Если данные не найдены, то модуль взаимодействия передает запрос в очередь, организованную на основе таблицы в базе данных. В полях таблицы сохраняется уникальный идентификатор запроса, время его отправки, флаг приоритета, адрес источника и параметры запроса (откуда, куда, дата, какие данные). Зная идентификатор запроса, модуль взаимодействия может обратиться в базу данных, чтобы получить информацию о статусе обработки запроса. Текущий справочный пакет передается пользователю, и система ожидает получения данных из внешних систем.
Когда в очереди появляются запросы на обслуживание, к работе подключается программа-сервис взаимодействия. Программа берет запрос из очереди последовательно, с учетом времени формирования и приоритета. Так, запросы пользователей в режиме реального времени имеют больший приоритет по сравнению с сервисными запросами. Запрос, взятый на облуживание, помечается в базе данных флагом «обслуживается».
Запрос из очереди трансформируется сервисом в новый запрос понятный внешней системе. Для пунктов назначения и отправления определяется их идентификатор во внешней системе и подставляется в формируемый запрос. Определяется адрес обращения к внешней системе и необходимая команда.
После того как пакет запроса подготовлен, сервис обращается в соответствующий источник (внешнюю систему), получает оттуда информацию и сохраняет в кэш. После этого изменяет статус запроса в очереди на значение «обслужен». Этот флаг затем может обнаружить модуль взаимодействия и обновить информацию, которая показывается пользователю.
Одновременно могут работать несколько сервисов взаимодействия, и они могут быть запущены на нескольких вычислительных машинах, просматривая единую очередь запросов. Сервисы могут специализироваться на обслуживании запросов к определенным внешним системам. То есть одни программы-сервисы могут работать с ЭКСПРЕСС, другие сервисы с другими внешними системами. Взаимодействие с системой ЭКСПРЕСС работает через специальный сервис-эмулятор терминала.
