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

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

Железов Роман Владимирович

РАЗРАБОТКА И ИССЛЕДОВАНИЕ ИНФОРМАЦИОННО-СПРАВОЧНОЙ СИСТЕМЫ ПОИСКА ОПТИМАЛЬНЫХ ПУТЕЙ ПРОЕЗДА НА ПАССАЖИРСКОМ ТРАНСПОРТЕ

Специальность 05.12.13 — Системы, сети и устройства телекоммуникаций.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

003463330

Москва-2009

003463330

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

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

Кузнецов Николай Александрович Институт радиотехники и электроники РАН

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

им. В.А.Трапезникова РАН

Защита состоится 24 марта 2009 г. в 15— на заседании диссертационного совета Д.212.156.04 при Московском физико-техническом институте (ГУ) по адресу: 141700, г. Долгопрудный, Московская обл., Институтский пер., д. 9, ауд. 204 Новый корпус.

С диссертацией можно ознакомиться в библиотеке

Московского физико-технического института (ГУ). //

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

Ученый секретарь

диссертационного совета Д.212.156.04, к.т.н., доцент

Научный руководитель: Официальные оппоненты:

^^ Л.П.Куклев

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

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

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

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

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

Научные исследования по поиску оптимальных путей проезда на пассажирском транспорте проводили М. M'uller-Hannemann, F. Schulz, D. Wagner, С. Zaroliagis, G. S. Brodai, R. Jacob, M. Schnee, К. Weihe, E. Pyrga, В. А. Жожикашвили, В.М. Вишневский, В. К. Попков и др. Большую работу по практическому исследованию алгоритмов поиска пути и сравнению их производительности провели D. Wagner и T. Willhalm. Однако недостатком известных работ является слабое внимание к требованиям, неизбежно возникающим при реализации единой информационно-справочной системы с использованием современных телекоммуникационных технологий. Так, в работах упомянутых авторов предлагается проводить длительные предварительные вычисления при обновлении данных, что накладывает ограничения на возможность актуализации информации в реальном времени.

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

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

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

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

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

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

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

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

4

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

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

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

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

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

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

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

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

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

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

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

Конференции молодых ученых и специалистов «Информационные технологии и системы» ( ИТиС-2007, Звенигород)

Научных конференциях МФТИ в 2004 и 2005г. (Долгопрудный).

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

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

СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность диссертационной работы, ее научная новизна и практическая значимость результатов.

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

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

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

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

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

В параграфе 1.3 описываются о зарубежные информационные системы на пассажирском транспорте. В Европе наибольшее распространение получили две системы: «ИАРАв» - на железнодорожном транспорте, «ЕРА» - на городском и пригородном транспорте. НАБАБ - наиболее известная в Европе на сегодняшний день информационная справочная система на наземном транспорте для больших расстояний. Система используется государственными и частными железными дорогами в нескольких странах Европы. Несколько лет назад начала работать новая справочная система «Еи-$р1пЬ>. Система позволяет находить пути проезда между интересующими точками в различных регионах Европы. Она основывается на существующих локальных, региональных и национальных справочных информационных системах, которые соединены посредством разработанных программных и телекоммуникационных интерфейсов. Известно, что результат справки для некоторых запросов в этих системах оказывается не самым оптимальным. Основной причиной такого поведения является то, что поисковый алгоритм справочной системы использует неточные методы, чтобы уменьшить пространство поиска.

В параграфе 1.5 дано описание эффективного алгоритма для поиска оптимальных путей в различных пространствах - А* (читается как "А-

звездочка"). Этот эвристический поиск сортирует все узлы по приближению наилучшего маршрута, идущего через этот узел. Типичная формула эвристики выражается в виде:

/00 = а(п) + А(п),

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

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

8

курсирования. Каждому маршруту соответствует битовое поле из N битов, определяющих, в какие дни маршрут курсирует. На станции 5 е В возможна пересадка с одного маршрута на другой, если время между отправлением и прибытием на станцию 8 больше, либо равно минимальному времени пересадки для этой станции. Для станций расположенных близко друг к другу возможно прохождение пешком, которое описывается введением, так называемых пеших ребер между станциями. Формально, мы рассматриваем пешее ребро как элементарное соединение с, где маршрут Д времена отправления и прибытия г^и не определены, но length(c) определено и равно времени пешего перехода.

Пусть Р = (с1д... ,ск) - последовательность элементарных соединений (включая пешие ребра), с заданными отправлениями ¿ер^Р) и прибытиями ащ(Р) для каждого элементарного соединения С;, 1 < ¡' < к. Полагаем, что времена прибытия и отправления включают также даты прибытий и отправлений и учитывают время, прошедшее с первого дня поездки. Время С = а * М + Ь, где а е [0,364], М - кол-во минут в сутках, Ъ 6 [О,М— 1]. Последовательность Р называется постоянным соединением от станции А - 5'1(с1) до станции В = 52(с(с), если удовлетворяет следующим условиям:

С; действует 1 день |с£ер((Р)/М], •^(Л) = 5-г(с£+1), йер^Р) = М),

агг((Р) = сгер((Р) + lev.gthi.ci),

ГО, еслм2(С[+1) = ши с1 — пешее ребро ' \transfer(S2(ci')), в противном случае Наиболее известная частная задача о расписаниях называется также задачей наискорейшего прибытия. Запрос (А, В, £:0) определяет станцию отправления А, станцию прибытия В и время отправления £0. Соединение допустимо, если отправление из А не происходит раньше заданного £:0. Критерий оптимизации -минимизировать разницу между временем прибытия и заданным временем отправления. В другой задаче минимального количества пересадок необходимо отыскать путь с наименьшим количеством пересадок для станций А и В, вообще не принимая во внимание времена прибытий и отправлений.

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

9

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

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

Исследования известных алгоритмов поиска по расписаниям показали, что без применения специальных ускоряющих техник производительность оказывается недостаточной. Средняя производительность особенно важна в системах с центральным сервером, который должен обрабатывать тысячи запросов одновременно, например, в Интернет или на транспортных терминалах (вокзалах, аэропортах). Техника «ограничения угла» использует информацию о пространственном расположении географических объектов. На этапе препроцессинга применяется алгоритм Дийкстры, чтобы вычислить кратчайшие пути из узла до всех других станций. Результаты вычислений не сохраняются, так как это потребовало бы слишком много места, но сохраняются два значения углов a(v, w) и b(v,w), которые сопоставляются ребру графа. Пусть (r,w) -ребро соединяющее событие V с другим событием w на время-расширенном графе и пусть S„ и Sw - станции, к которым принадлежат эти события. Рассмотрим угловой сектор между углами a(y,w) и b(v,w) с вершиной в точке

Углы а и Ь определяются таким образом, что конечные точки кратчайших путей, проходящих через ребро, будут внутри сектора. Позднее, во время работы алгоритма ребра (V, IV) могут быть проигнорированы поиском, если целевой узел не входит в угловой сектор. Основная идея другой техники «выбора станций» применяется во многих планировщиках маршрута на транспорте. Пусть С = (V, Е) — означает маршрутный граф. Пусть V' - набор выбранных узлов, из которых строится вспомогательный граф С. Вспомогательный граф С и веса ребер создаются и задаются только один раз на этапе препроцессинга. После этого любой запрос может быть обработан на вспомогательном графе С и путь будет соответствовать кратчайшему пути на графе С. Техника «поиска в направлении цели» использует потенциальную функцию на наборе узлов. Веса ребер в очереди изменяются так, чтобы направить поиск по графу в сторону цели. Пусть X - эта потенциальная функция. Новый вес ребра (г, IV) определяется как ■■= 1(?,ц/) — А(и) + «Иерархический поиск»

требует препроцессинга на котором исходный граф в = (V, Е) разбивается на несколько уровней I +1 и дополняется кратчайшими путями между определенными узлами. Чтобы найти кратчайший путь между узлами, алгоритму Дийкстры достаточно рассмотреть меньший подграф многоуровневого графа. Еще одна интересная техника использует понятие «радиуса достижения». Если V - вершина на кратчайшем пути Р из 5 в Ь, то радиус достижения по отношению к Р, г (у, Я) есть минимум от длины префикса Р (часть пути от б к у) и длины суффикса (часть пути от V к Г). Радиус достижения узла и,г(у) - это максимум г(у,Р) по всем кратчайшим путям, которые содержат V. Вычислив предварительно г (г) для всех узлов можно использовать эту информацию во время работы алгоритма Дийкстры. Техника «прямоугольника кратчайших узлов» похожа на метод «ограничения угла». На этапе препроцессинга обрабатываются все деревья кратчайших путей. Для каждого ребра е е Е, вычисляется набор узлов 5(е), кратчайшие пути к которым проходят через ребро е, и для каждого е 6 Е, сохраняется ограничивающий прямоугольник 5(е). Во время работы алгоритма можно оперативно определить, по какому ребру необходимо двигаться дальше, исключая из рассмотрения те ребра, которые заведомо не ведут к цели.

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

число документов. Пусть Pn(i) - условная вероятность того, что пришедший запрос относится к документу i. Расположим документы в порядке их популярности, где документ i - i-ый по популярности документ. Полагаем, что Pn(i), i = 1, 2, ...N имеет Zipfраспределение

PN( О = J,

где

(N ч -1

Z7 ■

¡=0 /

В случае бесконечного кэша и конечного числа запросов, количество попаданий как функцию количества запросов можно получить следующим образом: H(R) = Z^P^i) (1 - (1 - P„(Q)*l Асимптотическое поведение коэффициента попаданий Н(й) ~ Clin R. Это поведение можно очевидным образом получить приближением H(R): N Ш

H(R) = ^ - f(i) « ^ - « П ln(7to).

i=i i=i

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

С

H (С) =^Рд г(0 ~ ß In с.

¿=1

Вероятностное распределение d(k) того, что следующий запрос к документу придет через к запросов, определяется как

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

уровнях. В распределенном кэшировании не устанавливается промежуточных кэшей. Сетевая топология моделируется в виде дерева. Пусть О — плотность ветвей дерева. Пусть N - общее число документов и 8 - размер документа, документы обновляются с периодичностью Д, запросы к документу £, 1 < £ < N в кэше учреждения распределены по закону Пуассона со средней интенсивностью Лц Тогда общее число запросов к документу I равно Л,0ц = Ау 02Н и тоже распределено по Пуассону. Пусть интенсивность запросов к кэшу учреждения для всех N документов, [1, = Лц распределена по закону

¿и -

где константа а определяет, насколько пологим будет Z^pí распределение и <т как:

(к ч $

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

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

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

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

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

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

И!... ап

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

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

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

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

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

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

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

систем, запросы к ним поступают со всех регионов, и объем данных слишком велик, чтобы поддерживать их актуальную копию в информационной системе. Предполагается, что запросы к данным i, 1 < i < N распределены по закону Пуассона со средней интенсивностью Л^ Считается, что все документы запрашиваются независимо друг от друга, то есть пренебрегается любая корреляция между запросами. Пусть интенсивность запросов к кэшу нижнего уровня для всех N документов, ßi = Zittau . ßi распределена по закону Zipf:

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

(N ч"1 Й-

Общая задержка Т при получении документа состоит из задержки времени соединения Тс и времени передачи Г,

Е[Т] = Е[ТС] + E[Tt],

где £'[7'] — математическое ожидание времени полной передачи документа.

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

E[Tch] = 3d- Y, = 0 '1 ■

le{0,H,2h,2H+z)

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

E[Tcd] = 3d • ^Г P(Li = l)-2l + 4d- P(Lt = 2H + z) ■ (2H + z) .

1=0

Чтобы достичь удаленного локального сервера, запрос сначала поднимается вверх по сетевой иерархии, а затем опускается вниз к локальному серверу, содержащему документ i, проходя при этом 21 связей. Сетевой уровень Lt, до которого поднимается запрос (вероятность того, что количество связей, которое пришлось преодолеть больше или равно /) P(L; > Г) - это:

1 fÄ

Pfazo* jJ P(Li к UödT,

где P(Li 2 ¿|т) — вероятность того, что нет запросов к документу i в поддереве с корнем в I — 1в интервале времени [0, т]

P(L, > 1|т) =

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

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

ßi> * = О

h Olßr(l-hit,), О <КН

№ Olßr(l-hitR), Н<К2Н о02Hß, • (1 - hitN), 2Н < I < 2Н + z

Л

Вероятность обработки на каждом сетевом уровне hit; = Z'liC^p • P{i>i — 0)-

Суммарная частота запросов к локальной системе ß[ определяется выражением

ßf = Olß, • ((1 - hit,) + (fcit« - hit{)),

для О < I < 2H, и 02Hßi ■ (1 - hitff'), для 2H <1 <2H + z.

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

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

Б[Т?] = ]Г E\Jt\Li — Z] • P(Li = I) ,

l6{0,H,2/i,2H+Z}

где £[Ttft|L,- = i] - время передачи из соответствующего сетевого уровня глобальной информационной системы. Время передачи из региональной информационной системы £|Ttd] определяется выражением:

2H+Z

E[Ttd] = £ E[Ttd\Li = l]-P(Li = [), 1=0

где E[Tf\Li = i] - время передачи через соответствующий сетевой уровень из локальной информационной системы.

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

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

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

2" 1 г=о 1,1

_ ¡.-о^Лц-Д). (2H + z)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 1. Результат поиска пути проезда Бобруйск-Дальнегорск

В главе 4 продемонстрированы результаты использования информационно-справочной системы, и нроведено исследование ее работы. В параграфе 4.1 приводятся примеры результатов поиска по различным видам запросов: поиск маршрута с пересадкой на одном виде транспорта; поиск маршрута с одной пересадкой на нескольких видах транспорта; поиск маршрута с одной пересадкой в крупном транспортном узле; поиска маршрута с несколькими пересадками на одном виде транспорта.

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

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

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

Рисунок 2. Результат поиска пути проезда по Московской области

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

возможностью проезда. На основе вышеупомянутых исследования

проводится анализ суммарного времени

обработки запросов информационно-

Рисунок 3. Результат поиска пути Пекок-справочной системой в зависимости от „

[ Петрозаводск только на электричках.

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

Исследования показали, что наибольшее

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

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

В параграфе 4.2 проводится анализ справочных запросов, сделанных пользователями на сайте. За несколько

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

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

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

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

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

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

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

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Вишневский В. M., Железов Р. В. Принципы построения и реализация автоматизированной информационно-справочной системы поиска оптимальных путей проезда на пассажирском транспорте // Проблемы Управления. - 2009. -№1. - С. 33-37.

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

[3] Вишневский В. М., Железов Р. В., Атанасова Т. А. Единая справочная информационная система на пассажирском транспорте // Труды междунар. сем. "Распределенные компьютерные и телекоммуникационные сети" DCCN'2005. -M.: Техносфера, 2005. - С. 165 - 172.

[4] Железов Р. В. Поиск маршрута с учетом расписаний движения транспорта // Труды конф. "Информационные технологии и системы" ИТиС"07. -М.: ИППИРАН, 2007. - С. 171 - 173

[5] Железов Р. В., Особенности алгоритма поиска маршрута на транспорте с учетом расписаний движения // Труды междунар. сем. "Распределенные компьютерные и телекоммуникационные сети" DCCN'2007. - M.: ИППИ РАН, 2007.-С. 28-32.

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

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

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

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

Подписано в печать: 09.02.2009

Заказ № 1552 Тираж - 80 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение

Глава 1. Обзор алгоритмов и информационных систем на пассажирском транспорте.

1.1 Проблема поиска пути проезда на пассажирском транспорте.

1.2 Справочное обслуживание пассажиров в России.

1.2.1 Система «ЭКСПРЕСС».

1.2.2 Система «СИРЕНА».

1.2.3 Другие источники справочной информации в России.

1.3 Зарубежный опыт разработки информационных систем на транспорте.

1.4 Алгоритмы поиска кратчайшего пути на графе.

1.5 Алгоритм А* для поиска пути в пространстве.

1.6 Алгоритмы поиска маршрута на пассажирском транспорте.

1.6.1 Подходы к поиску маршрута и формулировка задачи.

1.6.2 Базовое моделирование: Задача наискорейшего прибытия.

1.6.3 Моделирование реальной задачи.

1.6.4 Многокритериальная оптимизация.

1.6.5 Приближенные подходы при многокритериальной оптимизации.

1.6.6 Производительность известных алгоритмов поиска.

1.7 Методы ускорения алгоритмов поиска на транспорте.

1.8 Архитектуры построения распределенных систем кэширования.

1.8.1 Кэширование данных.

1.8.2 Обзор архитектур кэширования в интернет.

1.8.3 Аналитическая модель распределенного кэширования.

1.8.4 Сравнение архитектур кэширования и ограничения моделей.

1.9 Постановка задачи поиска пути.

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

2.1 Разработка оригинального алгоритма поиска.

2.1.1 Алгоритм оптимистического поиска на графе.

2.1.2 Оригинальное представление графа в памяти компьютера.

2.1.3 Методы ускорения алгоритма поиска на графе.

2.1.4 Препроцессинг данных в реальном времени.

2.1.5 Выбор наискорейшего пути из найденного набора.

2.1.6 Проверка наличия свободных мест.

2.2 Взаимодействие с источниками данных.

2.2.1 Постановка задачи о взаимодействии с источником.

2.2.2 Выбор архитектуры в зависимости от параметров.

2.3 цикл обслуживания запроса.

2.4 Аналитический выбор архитектуры справочной системы.

2.4.1 Постановка задачи выбора архитектуры.

2.4.2 Аналитическая модель.

2.4.3 Сетевой уровень запроса.

2.4.4 Частота запросов к серверам.

2.4.5 Время передачи документа.

2.4.6 Время полной обработки запроса.

Глава 3. Программная реализация информационно-справочной системы

3.2 Специализированная база данных.

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

3.4 Средства импорта данных в базу данных системы.

3.4.1 Загрузка географических данных.

3.4.2 Импорт данных о расписаниях.

3.4.3 Корректировка данных в графе.

3.5 Реализация алгоритма поиска. Модуль ядра.

3.6 Программа управления системой.

3.7 Подсистема интеграции с внешними системами.

3.7.1 Описание процесса взаимодействия.

3.7.2 Интеграция с системой «ЭКСПРЕСС». Эмулятор терминала.

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

3.8 Интернет-портал доступа к справочной системе.

Глава 4. Анализ результатов поиска и исследование информационно-справочной системы

4.1 Сравнение результатов поиска с известными маршрутами проезда.

4.1.1 Поиск прямого маршрута.

4.1.2 Поиск пути проезда с пересадкой на одном виде транспорта.

4.1.3 Поиск пути с пересадкой на нескольких видах транспорта.

4.1.4 Поиск пути с пересадкой с учетом даты поездки.

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

4.1.6 Поиск пути с несколькими пересадками и с фильтрацией по виду транспорта

4.2 Исследование разработанной информационно-справочной системы.

4.2.1 Плотность графа железных дорог.

4.2.2 Длина маршрутов поездов дальнего следования.

4.2.3 Распределение количества пунктов назначения от числа пересадок.

4.2.4 Распределение количества пунктов назначения от расстояния.

4.2.5 Зависимость количества запросов от расстояния между пунктами.

4.2.6 Суммарное время обработки запросов информационно-справочной системой

4.2.7 Зависимость времени обработки запроса от расстояния.

4.3 Производительности модификаций алгоритма поиска.

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

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

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

В настоящее время в Российской Федерации отсутствует возможность справочно-информационного обслуживания пассажиров при поездках с пересадкой на авиационном, автобусном, железнодорожном и других видах транспорта. Это в значительной мере затрудняет возможность качественного обслуживания пассажиров, желающих приобрести билеты на маршруты, связанные с пересадкой с одного вида транспорта на другой. В связи этим назрела необходимость создания в Российской Федерации единой информационно-справочной системы, которая обеспечит пассажиров информацией не только при поездках на отдельных видах транспорта, но и при одновременном использовании железнодорожного, автобусного, авиационного и других видов пассажирского транспорта в одной поездке. Работы по созданию и развитию систем такого класса активно ведутся в США [66], Европе [51] и отдельных странах СНГ [55]. Быстрое развитие информационных технологий, в частности телекоммуникационных сетей, интернет-технологий, геоинформационных технологий и т.д. является объективной базой для реализации такой системы.

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

Заключение Выводы по теме диссертации

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

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

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

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

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

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

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

• Расписания транспорта для прямых маршрутов проезда между двумя пунктами;

• Поиск пунктов пересадки, когда прямого пути между двумя пунктами нет.

• Поиск пути проезда с использованием заданного вида транспорта (автобусы, поезда)

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

• Поиск пути проезда с ограничением на максимальное количество пересадок.

• Поиск пути проезда с интермодальными пересадками (разные видов транспорта)

• Поиск пути проезда в заданную дату. Маршруты транспорта, которые не удовлетворяют указанной дате, не отображаются в результатах поиска.

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

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

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

• Отображение интерактивной схемы беспересадочного сообщения от заданной станции.

Перспективы развития информационно-справочной системы на транспорте

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

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

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

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

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

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

1. Rodriguez P., Spanner С., Biersack E.W. Analysis of Web Caching Architectures: Hierarchical and Distributed Caching / IEEE/ACM Transactions on Networking'Ol (TON), August 2001, 684. Springer.

2. M'uller-Hannemann M., Schulz F., Wagner D., Zaroliagis C. Timetable Information: Models and Algorithms in Algorithmic Methods for Railway Optimization, Springer Berlin / Heidelberg, 2007

3. Brodal G. S., Jacob R. Time-dependent networks as models to achieve fast exacttime-table queries. Technical Report ALCOMFT-TR-Ol-176, BRICS, University of Aarhus,1. Denmark, 2001.

4. Cooke K. L., Halsey E. The shortest route through a network with time-dependent internodal transit times. Journal of Mathematical Analysis and Applications, 14:493^198, 1966.

5. DELFI. Durchg'angige elektronische Fahrplaninformation. http://www.delfi.de/.

6. Dijkstra E. W. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-271, 1959.

7. EFA. A timetable information system by Mentz Datenverarbeitung GmbH, M'unchen, Germany, http://www.mentzdv.de/.

8. Ehrgott M. Multicriteria Optimization. Springer, 2000.

9. Ehrgott M., Gandibleux X. Multiobjective combinatorial optimization. In Multiple Criteria Optimization — State of the Art Annotated Bibliographic Surveys, p. 369- 444. Kluwer Academic Publishers, Boston, MA., 2002.

10. EUSpirit. European travel information system, http://www.eu-spirit.com/.

11. Gabriel S., Bernstein D. The traffic equilibrium problem with non additive path costs. Transportation Science, 31(4):337-348, 1997.

12. HAFAS. A timetable information system by HaCon Ingenieurgesellschafit mbH, Hannover, Germany, http://www.hacon.de/hafas/.

13. Hansen P. Bicriteria path problems. In G. Fandel and T. Gal, editors, Multiple Criteria Decision Making Theory and Applications, volume 177 of Lecture Notes in Economics and Mathematical Systems, pages 109-127. Springer Verlag, Berlin, 1979.

14. Hensen D., Truong T. Valuation of travel times savings. Journal of Transport Economics and Policy, p. 237-260, 1985.

15. Kostreva M. M., Wiecek M. M. Time dependency in multiple objective dynamic programming. Journal of Mathematical Analysis and Applications, 173:289-307, 1993.

16. London P. e-solutions in vector minimization problems. Journal of Optimization Theory and Applications, 43:265-276, 1984.

17. Martins E. Q. V. On a multicriteria shortest path problem. European Journal of Operations Research, 16:236-245, 1984.

18. M'ohring R. Verteilte Verbindungssuche im "offentlichen Personenverkehr: Graphentheoretische Modelle und Algorithmen. In Angewandte Mathematik insbesondere Informatik, p. 192-220. Vieweg, 1999.

19. M'uller-Hannemann M., Schnee M. Finding all attractive train connections by multicriteria Парето search. In Proceedings of the 4th Workshop in Algorithmic Methods and Models for Optimization of Railways (ATMOS 2004).

20. M"uller-Hannemann M., K. Weihe Pareto shortest paths is often feasible in practice. In Algorithm Engineering WAE 2001, volume 2141 of LNCS, pages 185-198. Springer, 2001.

21. Nachtigal K. Time depending shortest-path problems with applications to railway networks. European Journal of Operations Research, 83:154-166, 1995.

22. Orda A., Rom R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM, 37(3), 1990.

23. Orda A., Rom R. Minimum weight paths in time-dependent networks. Networks, 21, 1991.

24. Pallottino S., ScutelKa M. G. Shortest path algorithms in transportation models: Classical and innovative aspects. In Equilibrium and Advanced Transportation Modelling, chapter 11. Kluwer Academic Publishers, 1998.

25. Papadimitriou C., Yannakakis M. On the approximability of trade-offs and optimal access of web sources. In Proc. 41st IEEE Symp. on Foundations of Computer Science FOCS 2000, p. 86-92. 2000.

26. Pyrga E., Schulz F., Wagner D., Zaroliagis C. Experimental comparison of shortest path approaches for timetable information. In Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments, p. 88-99. SIAM, 2004.

27. Rote G. Path problems in graphs. In G. Tinhofer, E. Mayr, H. Noltemeier, and M. Syslo, editors, Computational Graph Theory, pages 155-190. Springer, 1990.

28. Schulz F. Timetable Information and Shortest Paths. PhD thesis, Universit 'at Karlsruhe (TH), Fakult'at Informatik, 2005.

29. Schulz F., Wagner D., Weihe K. Dijkstra's algorithm on-line: An empirical case study from public railroad transport. Journal of Experimental Algorithmics, 5(12), 2000.

30. Schulz F., Wagner D., Zaroliagis C. Using multi-level graphs for timetable information in railway systems. In Proceedings 4th Workshop on Algorithm Engineering and Experiments (ALENEX), volume 2409 of LNCS, p. 43-59. Springer, 2002.

31. Theune D. Robuste und effiziente Methoden zur L'osung von Wegproblemen. Teubner Verlag, Stuttgart, 1995.

32. Tsaggouris G., Zaroliagis C. Improved FPTAS for multiobjective shortest paths with applications. Technical Report CTI TR 2005/07/03, Computer Technology Institute. And DELIS-TR-0238 (DELIS project), July 2005.

33. Tulp E., Sikl'ossy L. TRAINS, an active time-table searcher. In Eighth European Conf. on AI, p. 170-175, 1988.

34. Vassilvitskii S., Yannakakis M. Efficiently computing succinct trade-off curves. In Automata, Languages, and Programming ICALP 2004, volume 3142 of Lecture Notes in Computer Science, p. 1201-1213. Springer, 2004.

35. Wagner D., Willhalm T. Speed-up techniques for shortest path computations. In Algorithmic Methods for Railway Optimization, LNCS. Springer.

36. Wagner D., Willhalm T. Geometric speed-up techniques for finding shortest paths in large sparse graphs. In Proceedings of the 11th European Symposium on Algorithms (ESA 2003), volume 2832 of LNCS, p. 776-787. Springer, 2003.

37. Warburton A. Approximation of Pareto optima in multiple-objective shortest path problems. Operations Research, 35:70-79, 1987.

38. White D. J. Epsilon efficiency. Jorunal of Optimization Theory and Applications, 49:319-337, 1986.

39. Технический проект на комплект терминального оборудования "Экспресс-3" —■ М.: НИИМПС, 1997. — 170 стр.

40. Протокол BSC-3. Описание. — М.: НИИМПС, 1997. — 35 стр.

41. Олифер В. Г., Олифер Н. А. Компьютерные сети. Принципы, технологии, протоколы — СПб.: Питер, 2002. — 672с.

42. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы построение и анализ. — Москва.: МЦНМО: БИНОМ,2004. — 960 с.

43. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. — 512 с.

44. Кристофидес Н. Теория графов. Алгоритмический подход.—М.: Мир, 1978. 321 с.

45. Технический проект. Подсистема информационного обмена АСУ "Сирена-2". Документ 8, т. 1.— ИПУ,1983.

46. Международная система бронирования авиабилетов www.amadeus.com

47. Европейская справочная система, http://www.bahn.de

48. МЖА, портал доступа к системе «ЭКСПРЕСС», http://www.mza.ru

49. Сайт «Российские железные дороги», http://www.rzd.ru

50. Сайт Тверского автовокзала, http://www.tverbus.tvcom.ru

51. АСУ автобусного сообщения в Украине, http://www.bus.com.ua

52. Stout В. Алгоритмы поиска пути, статья 1997.http://algolist.manual.ru/maths/graphs/shortpath/smartmove.php

53. Статья по алгоритму A*. Amit's Thoughts on Path-Finding and A-Star http://theory.stanford.edu/~amitp/GameProgramming/index.html

54. Вишневский В.М.,Железов P.B., Атанасова Т.Н. «Единая справочная система на пассажирском транспорте Российской Федерации», Distributed Computer and Communication Networks, Техносфера, 2005 — с. 165-172.

55. Rina D., Pearl J. Generalized best-first search strategies and the optimality of A*, 1985, Journal of the ACM 32 (3): p. 505 536.

56. Russell S. J., Norvig P. Artificial Intelligence: A Modern Approach, 2003, pp. 97-104. ISBN 0-13-790395-2.

57. Wagner D., Willhalm T. Geometric Speed-Up Techniques for Finding Shortest Paths in Large Sparse Graphs. Konstanzer Schriften in Mathematik und Informatik Nr. 183, Januar 2003 ISSN 1430{3558}

58. Delling D., Holzer M., M'uller K., Schulz F., Wagner D. High-performance multi-level graphs. In Proc. Workshop on DIMACS Shortest-Path Challenge, 2007, http://il lwww.ira.uka.de/members/mholzer/publications/pdf/dhmsw-hpmlg-06.pdf.

59. Березка М.П. Система управления пассажирскими перевозками «Экспресс-3» http ://www. express-2 .ru/express-3 / frame, htm

60. Справочный сайт о расписаниях транспорта в России, http://www.tutu.ru

61. Статичные расписания транспорта в России http://all-transport.info/

62. Общественный транспорт Google-Transit http://www.google.com/transit67. "Сирена-Трэвел о системе": http://www.sirena-travel.ru/company/system/

63. Dantzig G. В. Linear Programming and Extensions. Princeton Univ. Press, Princeton, NJ, 1962.

64. Dreyfus D. An Appraisal of Some Shortest Path Algorithms. Technical Report RM-5433, Rand Corporation, Santa Monica, CA, 1967.

65. Goldberg A. V., Werneck R. F. Computing Point-to-Point Shortest Paths from External Memory. In Proc. 7th International Workshop on Algorithm Engineering and Experiments, pages 26{40. SIAM, 2005.

66. Nicholson T. A. J. Finding the Shortest Route Between Two Points in a Network. Computer J., 9:275-280, 1966.

67. Breslau L., Chao P., Fan L., Phillips G., Shenker S. On the implications of Zipf s lawfor Web caching. Proc. 3d Int. WWW Caching Workshop, Manchester, UK, June 1998.144

68. Claffy К., Braun H.-W., "Web traffic characterization: An assessment of the impact of caching documents from NCSA's web server," in Electronic Proc. 2nd World Wide Web Conf.'94: Mosaic and the Web, 1994.

69. Chankhunthod A. A hierarchical internet object cache, in Proc. 1996 USENIX Technical Conf., San Diego, CA, Jan. 1996.

70. Povey D., Harrison J. A distributed Internet cache, in Proc. 20th Australian Computer Science Conf., Sydney, Australia, Feb. 1997.

71. Tewari R., Dahlin M., Vin H. M., Kay J. S. Beyond hierarchies: Design considerations for disturbed caching on the Internet, in Proc. ICDCS '99 Conf., Austin, TX, May 1999.

72. Wessels D., Claffy K. Application of Internet cache protocol (ICP),version 2, Internet Engineering Task Force, Internet Draft:draft-wessels-icp-v2-appl-00. Work in Progress., May 1997.

73. Rousskov A., Wessels D. Cache digest, in Proc. 3rd Int. WWW Caching Workshop, June 1998, p. 272-273.

74. Fan L., Cao P., Almeida J., Broder A., Summary cache: A scalablewide-area web cache sharing protocol, in Proc. SIGCOMM'98, Feb. 1998, p. 254-265.

75. Valloppillil V., Ross K. W. Cache array routing protocol vl.l. Internet draft. Online], 1998, http://ds 1 .internic.net/internetdrafts/draft-vinod-carp-v 1 -03.txt

76. Karger D., Sherman A., Berkhemier A., Bogstad В., Dhanidina R., Iwamoto K., Kim В., Matkins L., Yerushalmi Y. "Web caching with consistent hashing," in Proc. 8th Int. World Wide Web Conf., May 1999.

77. Baentsch M., Baum L., Molter G., Rothkugel S., Sturm P. World Wide Web caching: The application-level view of the internet, IEEE Commun. Mag., p. 170-178, June 1997.

78. National Lab of Applied Network Research (NLANR). http://ircache.nlanr.net/

79. Vixie P., Wessels D. "RFC 2756: Hyper text caching protocol,"(HTCP/0.0), Jan. 2000.

80. Zipf G. K. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Reading, MA: Addison-Wesley, 1949.

81. Nonnenmacher J., Biersack E. W. Performance modeling of reliable multicast transmission, in Proc. IEEE INFOCOM'97, Apr. 1997.

82. Phillips G., Shenker S., Tangmunarunkit H. Scaling of multicast trees: Comments on the Chuang-Sirbu scaling law, in Proc. ACM SIGCOMM'99, Harvard, MA, Sept. 1999, pp. 4151.

83. Gribble S. Brewer E., System design issues for Internet middleware services: Deductions from a large client trace, in Proc. USENIX Symp. Internet Technologies and Systems, Dec. 1997.