WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 | 4 |

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

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

АВТОРЕФЕРАТ

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

Москва – 2009

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

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

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

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

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

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

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

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

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

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

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

Первые электронные справочные системы расписаний транспорта появились в 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 битов, определяющих, в какие дни маршрут курсирует.

Pages:     || 2 | 3 | 4 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»