Разработка и исследование информационно справочной системы поиска оптимальных путей проезда на пассажирском транспорте

На правах рукописи

Железов Роман Владимирович РАЗРАБОТКА И ИССЛЕДОВАНИЕ ИНФОРМАЦИОННО СПРАВОЧНОЙ СИСТЕМЫ ПОИСКА ОПТИМАЛЬНЫХ ПУТЕЙ ПРОЕЗДА НА ПАССАЖИРСКОМ ТРАНСПОРТЕ Специальность 05.12.13 – Системы, сети и устройства телекоммуникаций.

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Москва – 2009

Работа выполнена на кафедре телекоммуникационных сетей и систем в Московском физико-техническом институте (государственном университете).

Научный консультант: доктор технических наук, профессор Вишневский Владимир Миронович доктор технических наук, профессор,

Официальные оппоненты:

академик РАН Кузнецов Николай Александрович Институт радиотехники и электроники РАН кандидат технических наук Березка Михаил Павлович, Научно-исследовательский и проектно конструкторский институт информатизации, автоматизации и связи на железнодорожном транспорте (НИИАС)

Ведущая организация: Институт проблем управления им. В.А.Трапезникова РАН

Защита состоится 24 марта 2009 г. в 1500 на заседании диссертационного совета Д.212.156.04 при Московском физико-техническом институте (ГУ) по адресу:

141700, г. Долгопрудный, Московская обл., Институтский пер., д. 9, ауд. 204 Новый корпус.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (ГУ).

Автореферат разослан февраля 2009 г.

Ученый секретарь диссертационного совета Д.212.156.04, к.т.н., доцент Л.П.Куклев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Предоставление справочной информации об оптимальных путях проезда на пассажирском транспорте является необходимым условием для качественного обслуживания пассажиров. Полнота предоставленной информации не только помогает пассажиру, но и повышает эффективность пассажирских перевозок, уменьшает нагрузку на транспортные сети за счет оптимизации пассажиропотока.

Первые электронные справочные системы расписаний транспорта появились в 80-х годах прошлого века. На постсоветском пространстве функционируют системы «ЭКСПРЕСС» – на железнодорожном транспорте, «СИРЕНА» – на воздушном транспорте. В Европе широкое распространение получили системы «HAFAS» и «EFA».

К сожалению, уровень справочно-информационного обслуживания пассажиров далек от совершенства. В настоящее время в России даже в рамках отдельных видов транспорта отсутствует возможность поиска маршрута проезда с пересадкой. Исключение составляют автоматизированные информационные системы на воздушном транспорте, которые способны находить маршруты с пересадкой. Принимая во внимание размер транспортной системы России и то, что количество железнодорожных станций превосходит количество аэропортов в сотни раз, данная задача на железнодорожном транспорте является более сложной, чем на воздушном.

Еще сложнее - задача поиска интермодального пути (пути проезда с использованием нескольких видов транспорта), которая пока в полной мере не решается ни одной из существующих автоматизированных систем. При этом следует отметить, что транспортная сеть в Российской Федерации весьма неоднородна: есть населенные пункты, в которые можно попасть только по воздуху;

имеются регионы, лишенные железнодорожного транспорта;

есть населенные пункты, до которых можно добраться только автотранспортом.

Поэтому создание информационно-справочной системы с использованием современных телекоммуникационных технологий, которая объединит информацию из действующих автоматизированных систем на различных видах транспорта с целью получения наиболее полной справочной информации о возможности проезда с учетом пересадок и наличия мест является актуальной проблемой.

Научные исследования по поиску оптимальных путей проезда на пассажирском транспорте проводили M. Muller-Hannemann, F. Schulz, D.

Wagner, C. Zaroliagis, G. S. Brodal, R. Jacob, M. Schnee, K. Weihe, E. Pyrga, В. А.

Жожикашвили, В.М. Вишневский, В. К. Попков и др. Большую работу по практическому исследованию алгоритмов поиска пути и сравнению их производительности провели D. Wagner и T. Willhalm. Однако недостатком известных работ является слабое внимание к требованиям, неизбежно возникающим при реализации единой информационно-справочной системы с использованием современных телекоммуникационных технологий. Так, в работах упомянутых авторов предлагается проводить длительные предварительные вычисления при обновлении данных, что накладывает ограничения на возможность актуализации информации в реальном времени.

Цель диссертации. Целью настоящей диссертационной работы является построение моделей и методов реализации информационно-справочной системы, объединяющей информацию о разных видах пассажирского транспорта, на базе эффективного алгоритма поиска пути проезда с учетом расписаний, возможных пересадок между видами транспорта и наличия свободных мест. Для достижения поставленных целей в работе решены следующие основные задачи:

1. Проведение сравнительного анализа существующих методов и алгоритмов поиска пути с учетом расписаний движения транспорта.

2. Разработка сетевой модели взаимодействия справочной системы с существующими информационными системами на транспорте.

3. Разработка эффективного алгоритма поиска пути проезда на пассажирском транспорте с учетом пересадок и наличия мест.

4. Разработка базы данных и программного комплекса для обслуживания справочной системы.

5. Исследование производительности предложенных алгоритмов и разработанной информационно-справочной системы.

6. Разработка интернет-портала для доступа к информационно-справочной системе.

Методы исследования. Для достижения поставленной цели в диссертационной работе используются методы теории вероятностей, теории массового обслуживания, теории графов, а также имитационное моделирование.

Научная новизна:

- разработан новый алгоритм поиска оптимального пути проезда на пассажирском транспорте с минимальным количеством пересадок и минимальным временем в пути с учетом наличия свободных мест;

- разработана модель интеграции существующих систем на транспорте в единую информационно-справочную систему;

- предложена модель сети, описывающая функционирование справочной системы с учетом топологии сети и пропускных способностей различных уровней сети;

- предложены эффективные методы ускорения алгоритма поиска пути, позволяющие использовать алгоритм на практике.

Практическая ценность и реализация результатов. Разработанные алгоритмы и методы явились основой для создания справочного интернет-портала http://transport.marshruty.ru. Портал обеспечивает получение справок о возможности проезда с пересадками между двумя любыми пунктами Российской Федерации и ближнего зарубежья с использованием различных видов транспорта. Апробированная технология используется в разработке информационной системы ГУП МО «МОСТРАНСАВТО» и ЗАО «Транспортные Автоматизированные Информационные Системы», что подтверждено соответствующими актами о внедрении. Разработанные алгоритмы и программное обеспечение могут быть использованы и на других видах транспорта. Получено свидетельство о государственной регистрации программы для ЭВМ (№ 2008614887 от 10 октября 2008 года).

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на:

- Международном семинаре «Распределенные компьютерные и телекоммуникационные сети. Теория и приложения» (DCCN-2007, Москва);

- Международном семинаре «Распределенные компьютерные и телекоммуникационные сети. Теория и приложения» (DCCN-2005, София, Болгария);

Научных конференциях «Технологии Microsoft в теории и практике программирования» (2006, 2007, Москва);

Семинарах ИППИ РАН им. А. А. Харкевича;

Конференции молодых ученых и специалистов «Информационные технологии и системы» ( ИТиС-2007, Звенигород) Научных конференциях МФТИ в 2004 и 2005г. (Долгопрудный).

Публикации. По теме диссертации опубликовано 9 научных работ, список которых приведен в конце автореферата, в том числе две статьи в рецензируемых научных журналах, утвержденных в перечне ВАК.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего наименований, и приложения. Работа изложена на 145 страницах и содержит рисунков и 7 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность диссертационной работы, ее научная новизна и практическая значимость результатов.

В первой главе делается обзор отечественных и зарубежных информационных систем на транспорте и существующих алгоритмов поиска путей на графе. Особое внимание уделяется специализированным алгоритмам поиска пути в пространстве. Описаны существующие подходы к поиску маршрута с учетом расписаний движения транспорта, рассматриваются сетевые модели и архитектуры кэширования, которые используются при проектировании справочной системы.

В параграфе 1.2 описана отечественная система резервирования железнодорожных билетов «ЭКСПРЕСС». Первая система электронного резервирования «ЭКСПРЕСС-1» начала работу в Москве в 1972 году. В году была внедрена новая система – «ЭКСПРЕСС-2». В последующие годы количество региональных центров «ЭКСПРЕСС-2» достигло 29, которые обслуживали большинство государств бывшего СССР. В январе 2002 года в Москве заработала система «ЭКСПРЕСС-3». ЭКСПРЕСС-3 – это комплексная система обслуживания пассажиров, которая включает в себя средства децентрализованной подготовки и публикации расписаний, а также средства информационного обслуживания пользователей.

Первая автоматизированная система резервирования авиационных билетов «СИРЕНА» была введена в действие в 1972 году. Исчерпав свой технологический ресурс, она была заменена в 1981 году системой «СИРЕНА-2».

Спустя несколько лет было разработано несколько альтернативных проектов, на смену которым пришла распределительная система “Сирена-Трэвел”, введенная в промышленную эксплуатацию в 2001 году.

Помимо глобальных автоматизированных систем, охватывающих всю территорию Российской Федерации, существуют региональные справочные системы в отдельных городах и регионах. Обычно эти системы обслуживают автобусные компании, осуществляющие перевозки в отдельных регионах.

Несмотря на невысокую сложность задачи поиска пути проезда в отдельном регионе, эти системы не имеют возможности поиска с пересадкой. На данный момент даже такая актуальная задача, как справка о проезде с пересадкой на автобусах и электропоездах Московской области, не решается ни одной из систем.

В параграфе 1.3 описываются о зарубежные информационные системы на пассажирском транспорте. В Европе наибольшее распространение получили две системы: «HAFAS» – на железнодорожном транспорте, «EFA» – на городском и пригородном транспорте. HAFAS - наиболее известная в Европе на сегодняшний день информационная справочная система на наземном транспорте для больших расстояний. Система используется государственными и частными железными дорогами в нескольких странах Европы. Несколько лет назад начала работать новая справочная система «EU-Spirit». Система позволяет находить пути проезда между интересующими точками в различных регионах Европы. Она основывается на существующих локальных, региональных и национальных справочных информационных системах, которые соединены посредством разработанных программных и телекоммуникационных интерфейсов. Известно, что результат справки для некоторых запросов в этих системах оказывается не самым оптимальным. Основной причиной такого поведения является то, что поисковый алгоритм справочной системы использует неточные методы, чтобы уменьшить пространство поиска.

В параграфе 1.5 дано описание эффективного алгоритма для поиска оптимальных путей в различных пространствах - A* (читается как "А звездочка"). Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута, идущего через этот узел. Типичная формула эвристики выражается в виде:

где - значение оценки, назначенное узлу, - наименьшая стоимость прибытия в узел из точки старта, - эвристическое приближение стоимости пути к цели от узла. A* гарантированно находит кратчайший путь, до тех пор, пока эвристическое приближение является допустимым, то есть оно никогда не превышает действительного оставшегося расстояния до цели.

Существует два основных подхода к моделированию информации о расписаниях как задачи поиска кратчайшего пути: время-расширенный и время-зависимый. Эти подходы рассмотрены в параграфе 1.6. Общее свойство подходов в том, что результат вычисляется применением некоторого алгоритма поиска кратчайшего пути к специально построенному графу. Время расширенный граф конструируется таким образом, что каждый узел соответствует определенному времени (прибытия или отправления) на станцию, а ребра между узлами представляют либо элементарные соединения между двумя событиями, либо время ожидания на станции. На практике это приводит к созданию графа большой размерности. Что касается время-зависимого подхода, то идея состоит в том, чтобы избежать создания узлов графа для каждого события. Вместо этого время-зависимый граф строится так, что каждый узел представляет станцию, и два узла считаются связанными ребром, если соответствующие станции связаны элементарным соединением. Вес ребра присваивается «на лету» и зависит от времени, когда конкретное ребро будет использовано алгоритмом поиска кратчайшего пути. В задаче о расписаниях используются следующие понятия: станции (либо остановки, порты и др.), маршруты (поезда, автобусы), курсирующие между станциями, времена отправления и прибытия маршрутов на станции, и дни курсирования. Задача поиска формулируется следующим образом: имеется набор маршрутов Z, набор станций B, и набор элементарных соединений С элементы которого с - кортеж пяти величин в форме. Каждое элементарное соединение понимается как маршрут Z, отправляющийся со станции в момент времени, и прибывающий на станцию в момент времени. Длина элементарного соединения с, обозначается length(c), это время, которое прошло между прибытием и отправлением с. Расписание действует для числа N дней курсирования. Каждому маршруту соответствует битовое поле из N битов, определяющих, в какие дни маршрут курсирует. На станции возможна пересадка с одного маршрута на другой, если время между отправлением и прибытием на станцию S больше, либо равно минимальному времени пересадки для этой станции. Для станций расположенных близко друг к другу возможно прохождение пешком, которое описывается введением, так называемых пеших ребер между станциями. Формально, мы рассматриваем пешее ребро как элементарное соединение с, где маршрут Z, времена отправления и прибытия и не определены, но length(c) определено и равно времени пешего перехода.

Пусть – последовательность элементарных соединений (включая пешие ребра), с заданными отправлениями и прибытиями для каждого элементарного соединения,. Полагаем, что времена прибытия и отправления включают также даты прибытий и отправлений и учитывают время, прошедшее с первого дня поездки. Время, где, М – кол-во минут в сутках,. Последовательность P называется постоянным соединением от станции до станции, если удовлетворяет следующим условиям:

Наиболее известная частная задача о расписаниях называется также задачей наискорейшего прибытия. Запрос определяет станцию отправления A, станцию прибытия B и время отправления. Соединение допустимо, если отправление из А не происходит раньше заданного. Критерий оптимизации – минимизировать разницу между временем прибытия и заданным временем отправления. В другой задаче минимального количества пересадок необходимо отыскать путь с наименьшим количеством пересадок для станций А и B, вообще не принимая во внимание времена прибытий и отправлений.

Представленные подходы могут быть использованы для моделирования реальной задачи, учитывающей сложные условия, например, время пересадок.

Чтобы учесть времена пересадки во время-расширенной модели, на графе создается копия всех узлов прибытия и отправления со станции, которые мы называем узлами пересадки. Для каждого узла прибытия существует два исходящих ребра: одно ребро к отправлению того же маршрута, второе ребро – к узлу пересадки со временем больше или равным сумме времен прибытия в узел и минимальным временем требуемым на пересадку на данной станции.

Часто пассажиры заинтересованы в том, чтобы найти самый дешевый путь из А в B в заданном интервале времени. К сожалению, тарифная система в большинстве стран настолько сложна, что практически невозможно решить такую задачу поиска точно и одновременно быстро. Даже в стандартных тарифах стоимость проезда обычно не аддитивна. Еще хуже обстоит дело, если требуется учесть специальные тарифы. Многокритериальная оптимизация по нескольким критериям необходима, когда пассажиру требуется найти путь с минимальным количеством пересадок, который начинается после заданного времени и не заканчивается слишком поздно. Вычисление оптимального пути по нескольким критериям сводится к решению задачи поиска кратчайшего пути по нескольким критериям (MOSP, multi-objective shortest path) – основная задача в области многоцелевой оптимизации. Задача многокритериальной оптимизации обычно NP – полная. Так как даже для очень простых графов (цепь узлов, соединенных ребрами) в задаче с двумя критериями количество решений в наборе Парето растет экспоненциально. Поэтому на практике для нахождения решения многокритериальной задачи используются приближенные подходы.

Исследования известных алгоритмов поиска по расписаниям показали, что без применения специальных ускоряющих техник производительность оказывается недостаточной. Средняя производительность особенно важна в системах с центральным сервером, который должен обрабатывать тысячи запросов одновременно, например, в Интернет или на транспортных терминалах (вокзалах, аэропортах). Техника «ограничения угла» использует информацию о пространственном расположении географических объектов. На этапе препроцессинга применяется алгоритм Дийкстры, чтобы вычислить кратчайшие пути из узла до всех других станций. Результаты вычислений не сохраняются, так как это потребовало бы слишком много места, но сохраняются два значения углов и, которые сопоставляются ребру графа. Пусть ребро соединяющее событие c другим событием на время-расширенном графе и пусть и – станции, к которым принадлежат эти события.

Рассмотрим угловой сектор между углами и с вершиной в точке. Углы и определяются таким образом, что конечные точки кратчайших путей, проходящих через ребро, будут внутри сектора. Позднее, во время работы алгоритма ребра могут быть проигнорированы поиском, если целевой узел не входит в угловой сектор. Основная идея другой техники «выбора станций» применяется во многих планировщиках маршрута на транспорте. Пусть – означает маршрутный граф. Пусть - набор выбранных узлов, из которых строится вспомогательный граф. Вспомогательный граф и веса ребер создаются и задаются только один раз на этапе препроцессинга. После этого любой запрос может быть обработан на вспомогательном графе и путь будет соответствовать кратчайшему пути на графе. Техника «поиска в направлении цели» использует потенциальную функцию на наборе узлов. Веса ребер в очереди изменяются так, чтобы направить поиск по графу в сторону цели. Пусть – эта потенциальная функция. Новый вес ребра определяется как «Иерархический поиск» требует препроцессинга на котором исходный граф G = (V, E) разбивается на несколько уровней и дополняется кратчайшими путями между определенными узлами. Чтобы найти кратчайший путь между узлами, алгоритму Дийкстры достаточно рассмотреть меньший подграф многоуровневого графа.

Еще одна интересная техника использует понятие «радиуса достижения». Если – вершина на кратчайшем пути P из в, то радиус достижения по отношению к есть минимум от длины префикса P (часть пути от s к v) и длины суффикса (часть пути от к ). Радиус достижения узла – это максимум по всем кратчайшим путям, которые содержат. Вычислив предварительно для всех узлов можно использовать эту информацию во время работы алгоритма Дийкстры. Техника «прямоугольника кратчайших узлов» похожа на метод «ограничения угла». На этапе препроцессинга обрабатываются все деревья кратчайших путей. Для каждого ребра, вычисляется набор узлов, кратчайшие пути к которым проходят через ребро, и для каждого, сохраняется ограничивающий прямоугольник. Во время работы алгоритма можно оперативно определить, по какому ребру необходимо двигаться дальше, исключая из рассмотрения те ребра, которые заведомо не ведут к цели.

В параграфе 1.8 сделан обзор архитектур распределенных систем кэширования в Интернет. Кэширование данных - фундаментальная технология, позволяющая уменьшить время доступа к объекту данных. Пусть N – общее число документов. Пусть – условная вероятность того, что пришедший запрос относится к документу i. Расположим документы в порядке их популярности, где документ i – i-ый по популярности документ. Полагаем, что, i = 1, 2, …N имеет Zipf распределение, где В случае бесконечного кэша и конечного числа запросов, количество попаданий как функцию количества запросов можно получить следующим образом:.

Асимптотическое поведение коэффициента попаданий Это поведение можно очевидным образом получить приближением H(R):

В случае ограниченного размера кэша объемом С документов, на который поступает бесконечный поток запросов, асимптотическое значение коэффициента H(C) может быть вычислено так:

Вероятностное распределение того, что следующий запрос к документу придет через k запросов, определяется как Эффективность кэша в Интернет сильно зависит от корреляции интересов в группе пользователей. Чтобы повысить эффективность кэширования, несколько кэшей объединяют в систему. Существует два основных подхода к построению больших систем кэширования: иерархический и распределенный. В иерархическом кэшировании кэши располагаются на различных сетевых уровнях. В распределенном кэшировании не устанавливается промежуточных кэшей. Сетевая топология моделируется в виде дерева. Пусть O – плотность ветвей дерева. Пусть N – общее число документов и S – размер документа, документы обновляются с периодичностью, запросы к документу, в кэше учреждения распределены по закону Пуассона со средней интенсивностью I,i Тогда общее число запросов к документу равно tot,I = I,i O2H и тоже распределено по Пуассону. Пусть интенсивность запросов к кэшу учреждения для всех N документов, распределена по закону.

Zipf:

где константа определяет, насколько пологим будет Zipf распределение и как:

В иерархическом кэшировании имеет место меньшее время соединения, чем в распределенном кэшировании. Но распределенное кэширование имеет меньшее время передачи, чем иерархическое кэширование, так как больше трафика проходит через менее загруженный нижний сетевой уровень. Что касается нагрузки на сеть, то при иерархическом кэшировании она суммарно меньше, чем при распределенном, так как иерархическое кэширование использует промежуточные кэши. С другой стороны, распределенное кэширование хорошо распределяет сетевую нагрузку на систему, в отличие от иерархической, где могут возникать перегруженные узлы системы.

Разработке алгоритмов и архитектуры справочной системы посвящена вторая глава диссертации. В начале главы предложен оригинальный алгоритм поиска пути. Далее рассмотрены технологии взаимодействия с внешними автоматизированными системами. В третьей части описан цикл обработки клиентского запроса. В четвертой части рассмотрены основные моменты проектирования архитектуры и предложена аналитическая модель информационной системы.

В параграфе 2.1 разработан оригинальный алгоритм поиска, который строго решает поставленную двухкритериальную задачу. На первом этапе проводится поиск по «виртуальному» графу. Этот поиск находит все пути с одинаковым минимальным количеством пересадок. Найденные пути анализируются на следующем шаге алгоритма, где для каждого из них проверяется допустимость с учетом дней курсирования и наличия мест, и решается задача наискорейшего прибытия. Затем среди допустимых путей выбирается наискорейший. В том случае, если все пути оказались недопустимы, то повторяется первый этап поиска по графу с исключением найденных ранее путей. Основные функциональные части алгоритма: (i) алгоритм оптимистического поиска в графе, (ii) методы выбора наискорейшего пути из оптимистически найденных на графе, (iii) проверка наличия свободных мест. В графе хранится информация обо всех допустимых транспортных маршрутах и решается задача поиска пути с минимальным количеством пересадок. Все узлы графа, между которыми можно проехать без пересадки, соединим ребрами веса 1. Поиск такого пути можно производить с помощью двунаправленного алгоритма Дийкстры. В реализации алгоритма необходимые ребра рассчитываются динамически, и по окончании работы алгоритма память освобождается. В противном случае потребовался бы значительный объем памяти для хранения данных. В оригинальном алгоритме подсчитывается не минимальное число пересадок, а минимальное число маршрутов, которое на единицу больше числа пересадок. Известны два распространенных способа представить граф: как набор смежных вершин или как матрицу смежности. Алгоритм реализован на встроенном языке базы данных и работает с таблицами и записями. Хранение расписаний в таблицах и реализация алгоритма на уровне базы данных оказывается на практике достаточно эффективной и не требует избыточного преобразования данных. Для каждой записи о расписании хранится идентификатор узла, идентификатор маршрута, время прибытия, время отправления и другая информация. Алгоритм Дийкстры, хотя и может быть применим к данной задаче, но не является достаточно быстрым для практической реализации в справочной системе.

Существующие техники ускорения не могут быть использованы в информационной системе. В них используется длительный препроцессинг данных и хранение вспомогательной информации для каждого ребра.

Препроцессинг может длиться десятки часов даже на современных вычислительных комплексах, а это неприемлемо, когда информация обновляется в режиме реального времени из внешних автоматизированных систем. Кроме того, в оригинальной реализации информация о ребрах графа вообще не хранится в системе, поэтому предложены несколько методов ускорения поиска, лишенные указанных недостатков. Метод пересадочного графа заключается в выделении потенциальных узлов пересадки. В процессе обновления данных о расписаниях, можно анализировать упомянутые в расписании станции и определять потенциальные узлы пересадки. Важно, что список станций пересадок обновляется в режиме реального времени и не требует масштабных вычислений. В результате создается пересадочный граф меньшего размера.

Другой метод - балансировка двунаправленным поиском - заключается в выборе прямого или обратного поиска на каждом шаге итерации с учетом количества смежных станций. В работе этого метода используется информация о количестве смежных станций, которая может быстро вычисляться в режиме реального времени. Еще один возможный подход - это ускорение последней итерации. Последняя итерация поиска требует больше времени, чем предыдущие, так как поиск охватывает все большее количество станций. Для каждой станции вычисляется ограничивающий прямоугольник станций, достижимых без пересадок. На последнем шаге итерации используется информация об ограничивающем прямоугольнике каждой станции для выяснения, может ли станция быть пересадкой или ее заведомо нужно исключить. Еще один эффективный метод ускорения - это метод ускорения А*.

Он основан на эвристическом алгоритме А* и превосходит алгоритм Дийкстры в быстродействии. Хотя А* в данной задаче и не является точным подходом, но на практике его можно эффективно применить, и найденное решение с высокой вероятностью оказывается оптимальным. Важно, что все предложенные методы ускорения могут применяться в оригинальном алгоритме поиска совместно.

Данные о расписаниях непрерывно обновляются, и все вспомогательные данные должны вычисляться быстро. Поэтому для построения пересадочного графа анализируются только станции, расписание по которым изменилось. После того, как пути с минимальным количеством пересадок найдены, проводится проверка их допустимости, и выбирается наискорейший путь. Поиск кратчайшего пути оказывается вычислительно менее сложной задачей, чем первый шаг поиска по графу. Данные о наличии свободных мест - быстро обновляющаяся часть транспортной информации. Если пропускная способность канала связи с внешними системами ограничена, то физически невозможно поддерживать актуальность такой информации в справочной системе. Но при большом количестве клиентских запросов перенаправление их в автоматизированную систему приводит к перегрузке канала связи. Если использовать кэширование, то нет необходимости обращаться к источникам и нагружать канал связи при каждом запросе, но тогда возникает ряд других проблем. Поэтому выбор способа зависит от параметров источника. Когда существует много объектов данных, что является более естественным, то задача существенно усложняется. Для каждого объекта данных выбирается своя стратегия репликации. Полная стоимость всех запросов определяется выражением:

Для решения сложной задачи поиска пути цикл обслуживания запроса включает несколько основных шагов, описанных в параграфе 2.3:

1. Поиск возможных путей на графе между пунктами отправления и прибытия без учета дней курсирования.

2. Первичная фильтрация найденных путей и исключение недопустимых по дате поездки, виду транспорта.

3. Выбор из оставшихся вариантов оптимального пути по заданному критерию.

4. Проверка выбранного пути на наличие свободных мест.

Каждый из этапов характеризуется средним временем обработки и вероятностью «промаха». В диссертации проанализирован цикл обслуживания запроса, что позволяет разработать методы повышения производительности.

Архитектура справочной системы должна обеспечивать высокую производительность при большом количестве пользовательских запросов.

Справочная система рассматривается в параграфе 2.4 как распределенная информационная система. Предлагается аналитическая модель системы, которая позволяет оценить время обработки справочных запросов. Одна из особенностей задачи, которая учитывается в модели - географическое распределение запросов от пользователей. Существует два вида источников данных: (i) региональные автоматизированные системы (охватывают транспорт отдельного города или региона) и (ii) глобальные автоматизированные системы на транспорте (охватывают одну или несколько стран). Подавляющее большинство пользователей интересует справочная информация по тому региону, где они находятся, поэтому нецелесообразно копировать региональную информацию на межнациональный уровень. Что касается глобальных автоматизированных систем, запросы к ним поступают со всех регионов, и объем данных слишком велик, чтобы поддерживать их актуальную копию в информационной системе.

Предполагается, что запросы к данным, распределены по закону Пуассона со средней интенсивностью I,i. Считается, что все документы запрашиваются независимо друг от друга, то есть пренебрегается любая корреляция между запросами. Пусть интенсивность запросов к кэшу нижнего уровня для всех N документов, распределена по закону Zipf:

.

, где константа определяет, насколько пологим будет Zipf распределение и определяется как:

Общая задержка T при получении документа состоит из задержки времени соединения и времени передачи где – математическое ожидание времени полной передачи документа.

Время соединения зависит от количества сетевых связей, которое необходимо пройти от справочной системы до источника данных. Пусть количество связей, которое прошел запрос к документу i, прежде чем достиг нужного сервера. Время соединения с сервером глобальной системы определяется:

Время соединения с удаленным сервером локальной системы определяется выражением:

Чтобы достичь удаленного локального сервера, запрос сначала поднимается вверх по сетевой иерархии, а затем опускается вниз к локальному серверу, содержащему документ, проходя при этом связей. Сетевой уровень, до которого поднимается запрос (вероятность того, что количество связей, которое пришлось преодолеть больше или равно – это:

где – вероятность того, что нет запросов к документу i в поддереве с корнем в в интервале времени [0,.

В результате получаем вероятность:

Чтобы вычислить времена передачи, сначала определяется суммарная частота запросов на каждом сетевом уровне. Суммарная частота к глобальной внешней системе определяется выражением:

.

Вероятность обработки на каждом сетевом уровне Суммарная частота запросов к локальной системе определяется выражением для,и, для.

Время передачи данных из различных систем рассматривается в параграфе 2.4.

Время передачи из глобальной информационной системы :

где – время передачи из соответствующего сетевого уровня глобальной информационной системы. Время передачи из региональной информационной системы определяется выражением:

где – время передачи через соответствующий сетевой уровень из локальной информационной системы.

Пусть – средний размер документов. Теория очередей M/D/1 дает для запросов к глобальным системам выражение:

.

Аналогично для запросов к локальным системам:

.

Время полной обработки запроса выводится в параграфе 2.4 и определяется наибольшим из времен взаимодействия с информационными системами. Время установления соединения с удаленной локальной системой оказывается больше этого времени для глобальной системы:

Программной реализации справочной системы посвящена третья глава диссертации. В главе описан комплекс программ и реализация алгоритмов, которые обеспечивают функционирование информационно-справочной системы.

Программный комплекс включает в себя следующие компоненты:

1. Специализированная база данных геоинформации и расписаний.

Средства подготовки данных для геоинформационной системы и БД.

2.

Средства импорта данных из промежуточного формата XML.

3.

Реализация алгоритмов поиска маршрута на транспорте.

4.

Службы интеграции с другими информационными системами, включающие:

5.

интеграционный сервис, функционирующий в режиме on-line;

a.

b. эмулятор терминала системы ЭКСПРЕСС.

Справочный интернет-портал для доступа к информационной системе.

6.

Специализированная база данных оптимизирована для хранения и анализа информации по транспорту. Она содержит несколько десятков таблиц и реализацию базовых алгоритмов работы с данными, которые запрограммированы в хранимых процедурах на языке T-SQL. Каждый объект в базе данных имеет как координатную привязку, так и привязку к совокупному графу вершин и соединений.

Средства подготовки данных для системы описаны в параграфе 3.3.

Особенности информационной системы потребовали создания специального программного инструментария – среды визуального описания транспортного графа. Программа представляет собой Windows-приложение, написанное на языке C++. С ее помощью можно описать фрагменты единого графа. Результаты работы программы сохраняются в файлы формата XML. Для каждого региона создается отдельный XML файл, где указывается расположение региональных транспортных узлов. Таким способом можно последовательно описать все фрагменты железнодорожной и автобусной сети. С помощью разработанной программы было описано большинство железнодорожных станций, вокзалов, платформ на территории всего бывшего СССР и некоторых прилегающих стран, а также основные автобусные станции нескольких регионов России.

После того, как географические данные подготовлены в формате XML, они загружаются в систему с помощью программы импорта данных. Программа подключается к базе данных системы, получает на вход данные в формате XML и вносит изменения в БД. Текущая база данных загружена из нескольких десятков файлов XML и образует граф из более чем двадцати тысяч вершин.

Процесс загрузки состоит из следующих шагов: считывание данных из файла, анализ данных, устранение неоднозначностей, формирование объектной структуры, сохранение данных. Программа импорта состоит из двух функциональных модулей: (i) загрузчик географических данных, (ii) загрузчик расписаний. Загрузчик географических данных обрабатывает подготовленные оператором файлы данных. Алгоритм импорта географических объектов запрограммирован следующим образом: 1) распознавание названия и типа объекта;

2) поиск объектов в базе данных с похожим названием;

3) добавление объекта в базу данных;

4) обновление топологических связей.

Реализация алгоритма поиска и модуль ядра описаны в параграфе 3.7.

Используя идентификаторы пунктов назначения и отправления, модуль собирает необходимую информацию о географических объектах. Если прямой маршрут не найден, то алгоритм начинает поиск сложного маршрута. Хранимая процедура возвращает таблицу данных, в которой содержится информация о найденных путях проезда. Алгоритм рассматривает все найденные пути и для каждого из них вычисляет наискорейшее время прибытия. После того как из списка удалены недопустимые пути, и для каждого из доступных путей вычислено наискорейшее время прибытия, список путей сортируется по времени наискорейшего прибытия. На последнем этапе лучший из найденных путей отправляется на проверку в модуль взаимодействия с автоматизированными системами.

Взаимодействие с внешними системами представляет отдельную подсистему, в которую входят: модуль интеграции в составе модуля поиска пути;

сервис интеграции с внешними системами;

эмулятор терминала ЭКСПРЕСС;

программа контроля взаимодействия с внешними системами.

Подсистема работает следующим образом. Когда пользователь делает запрос, то сначала выполняются основные шаги алгоритма поиска: (i) находятся возможные пути проезда, (ii) проверяются даты курсирования маршрутов. После того как найден предполагаемый оптимальный путь, делается внутренний запрос в подсистему взаимодействия, которая формирует запрос во внешние системы.

Способ отправки запроса зависит от особенностей внешней системы. Если запрос синхронный, то обслуживающий процесс выполняет его немедленно.

Если используется асинхронный способ взаимодействия, например, с системой ЭКСПРЕСС, то запрос ставится в очередь. Когда в очереди появляются запросы на обслуживание, к работе подключается программа-сервис взаимодействия.

Запрос берется из очереди и трансформируется сервисом в запрос по протоколу, поддерживаемому автоматизированной системой. Одновременно могут работать несколько сервисов взаимодействия, запущенные на нескольких вычислительных машинах и просматривающие единую очередь запросов.

Сервисы могут специализироваться на обслуживании запросов к определенным внешним системам. Взаимодействие с системой ЭКСПРЕСС осуществляется через специальный сервис-эмулятор терминала. При получении запроса, для которого необходимо получить информацию из системы ЭКСПРЕСС, эмулятор терминала преобразует запросы системы в пакеты BSC-3 сети ЭКСПРЕСС, инкапсулирует их в пакеты TCP/IP и передает на шлюз доступа в ЭКСПРЕСС.

Далее шлюз обменивается информацией с ХОСТ-ЭВМ и возвращает ответ эмулятору. Процесс протекает асинхронно: один запрос системы может отображаться в серию запросов-ответов между эмулятором и ХОСТ-ЭВМ.

Для получения справочной информации о возможности проезда через сеть Интернет разработан справочный портал. Портал обеспечивает пользователей справочной информацией о маршрутах пассажирского транспорта России, ближнего и дальнего зарубежья. Сайт предоставляет следующую информацию:

- поиск пунктов пересадки, когда нет прямого пути проезда;

- поиск путей только на указанном виде транспорта (автобусы, поезда);

- поиск пути проезда между двумя пунктами с пересадкой в третьем явно указанном пункте;

- поиск интермодального пути проезда (на разных видах транспорта);

- поиск пути проезда в заданную дату (маршруты транспорта, которые не удовлетворяют указанной дате, не отображаются в результатах);

- поиск пути проезда со всех вокзалов города, или явное указание с какого вокзала искать путь;

- отображение найденных путей проезда на интерактивной карте;

- отображение схемы всех прямых маршрутов транспортного узла.

Рисунок 1. Результат поиска пути проезда Бобруйск-Дальнегорск В главе 4 продемонстрированы результаты использования информационно справочной системы, и проведено исследование ее работы. В параграфе 4. приводятся примеры результатов поиска по различным видам запросов:

- поиск маршрута с пересадкой на одном виде транспорта;

- поиск маршрута с одной пересадкой на нескольких видах транспорта;

- поиск маршрута с одной пересадкой в крупном транспортном узле;

- поиска маршрута с несколькими пересадками на одном виде транспорта.

В параграфе 4.2 проводится статистический анализ транспортного графа. Проводится три серии вычислений по исследованию плотности графа вокруг Москвы, Калининграда и Владивостока.

Результаты исследования приведены в таблицах и на графиках. Исследования зависимости количества станций как функции удаленности от исследуемой станции подтверждают высокую неоднородность транспортного графа.

Например, на расстоянии 500 км от Москвы расположено более 3000 станций, а на таком же расстоянии от Владивостока - только 195 станций. Аналогичный статистический анализ проводится для Рисунок 2. Результат поиска пути пересадочного графа. Вид графиков и проезда по Московской области данные таблиц показывают аналогичную картину неоднородности для пересадочного графа. Далее в главе исследуются транспортные маршруты поездов дальнего следования.

Далее находится зависимость количества достижимых пунктов назначения от минимального числа необходимых пересадок. Проводится серия вычислений для пунктов Москва, Калининград и Владивосток. Как и следовало ожидать, для проезда из Москвы в другие пункты в среднем требуется меньше пересадок, чем для проезда из Владивостока. Приводится анализ зависимости количества пунктов назначения от расстояния и заданного количества пересадок. Из графиков видно, что наиболее вероятное расстояние до пункта назначения, до которого можно добраться из Москвы минимум с одной пересадкой, составляет 800 км. Для Калининграда это расстояние составляет уже 1200 км, а для Владивостока - 6500 км.

В параграфе 4.2 проводится анализ справочных запросов, сделанных пользователями на сайте. За несколько месяцев пользователями выполнено около полумиллиона запросов. Анализ этих данных позволяет получить информацию о поездках, которые интересуют пользователей. Показано, что чем меньше расстояние между пунктами, тем больше пользователей интересуется возможностью проезда. На основе вышеупомянутых исследования проводится анализ суммарного времени обработки запросов информационно Рисунок 3. Результат поиска пути Псков справочной системой в зависимости от Петрозаводск только на электричках.

расстояния между пунктами. Отмечены возможные места пересадок.

Исследования показали, что наибольшее количество ресурсов система расходует на обработку запросов на средние расстояния. В параграфе 4.2 также исследуется зависимость времени обработки запроса от расстояния между пунктами. Математическое исследование дает хорошую аппроксимацию логарифмическим приближением. Таким образом, эмпирически получено, что среднее время поиска пропорционально логарифму от расстояния между пунктами. В параграфе 4.3 проводится анализ производительности методов ускорения и анализ особенностей алгоритма А*.

Показано, как изменение параметра эвристики влияет на точность алгоритма А*.

Приведены результаты сравнений производительности методов ускорения.

Результаты показывают, что наиболее эффективным методом ускорения оказывается метод балансировки поиском. Наибольшую производительность дает суперпозиция всех предложенных методов ускорения.

В заключении приводятся основные результаты и выводы диссертационной работы.

В приложение вынесены акты о внедрении, описания форматов используемых данных, описания вспомогательных программ, технические требования к оборудованию.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ В диссертации проведен сравнительный анализ методов и алгоритмов поиска пути с учетом расписаний движения транспорта, а также выявлены недостатки существующих алгоритмов.

Разработана сетевая модель взаимодействия информационно-справочной системы с существующими информационными системами на транспорте, позволяющая спроектировать оптимальную архитектуру справочной системы.

Разработан оригинальный алгоритм поиска оптимальных путей проезда на пассажирском транспорте с учетом пересадок и наличия мест.

Разработана база данных и комплекс программ для обслуживания справочной системы.

Проведены испытания разработанной справочной системы и сделаны оценки эффективности разработанных алгоритмов.

Разработан интернет-портал http://transport.marshruty.ru для доступа к информационно-справочной системе.

Созданная система предоставляет следующую справочную информацию о возможности проезда:

расписания для нескольких видов транспорта;

выбор оптимальных путей по критерию минимального количества пересадок и минимальному времени в пути на железнодорожном и автобусном транспорте;

учет наличия свободных мест на поезда при поиске пути проезда;

пригородные маршруты подъезда к железнодорожным вокзалам.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ [1] Вишневский В. М., Железов Р. В. Принципы построения и реализация автоматизированной информационно-справочной системы поиска оптимальных путей проезда на пассажирском транспорте // Проблемы Управления. – 2009. – №1. – С. 33 – 37.

[2] Железов Р. В. Новые технологии справочно-информационного обслуживания пассажиров // Железнодорожный транспорт. – 2008. – №8. – С. – 36.

[3] Вишневский В. М., Железов Р. В., Атанасова Т. А. Единая справочная информационная система на пассажирском транспорте // Труды междунар. сем.

“Распределенные компьютерные и телекоммуникационные сети” DCCN`2005. – М.: Техносфера, 2005. – С. 165 – 172.

[4] Железов Р. В. Поиск маршрута с учетом расписаний движения транспорта // Труды конф. “Информационные технологии и системы” ИТиС`07. М.: ИППИ РАН, 2007. – С. 171 – [5] Железов Р. В., Особенности алгоритма поиска маршрута на транспорте с учетом расписаний движения // Труды междунар. сем. “Распределенные компьютерные и телекоммуникационные сети” DCCN`2007. – М.: ИППИ РАН, 2007. – С. 28 – 32.

[6] Железов Р. В. Особенности архитектуры распределенной справочной системы на транспорте // Труды всеросс. конф. «Технологии Microsoft в теории и практике программирования». – М.: Вузовская книга, 2007. – С. 16 – 18.

[7] Железов Р. В. Реализация единой справочной системы пассажирского транспорта на базе технологий Microsoft // Труды всеросс. конф. «Технологии Microsoft в теории и практике программирования». – М.: МГТУ им. Н.Э.

Баумана, 2006. – С. 10 - 13.

[8] Железов Р. В., Оригинальный алгоритм поиска кратчайшего маршрута с пересадкой // Труды XLVII конф. МФТИ «Современные проблемы фундаментальных и прикладных наук». – М.: МФТИ, 2004. – С. 29 – 30.

[9] Железов Р. В. Проблема репликации в контексте «Единой справочной системы на транспорте» // Труды XLVIII конф. МФТИ «Современные проблемы фундаментальных и прикладных наук». – М.: МФТИ, 2005. – С. 33 – 35.