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

• Автор: Железов, Роман Владимирович
• Шифр специальности: 05.12.13
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 148 с. : ил.

Введение

Глава 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 Производительности модификаций алгоритма поиска
Заключение
Выводы ПО ТЕМЕ диссертации
Перспективы развития информационно-справочной системы на транспорте

Приложения
Приложение 1. Схемы маршрутов некоторых транспортных узлов
Автомобильный пассажирский транспорт
Железнодорожный пассажирский транспорт
Приложение 2. Описание программы построения графов
ПриложениеЗ. Образцы ХМЬ файлов обрабатываемых системой
Приложение 4. Форматы шаблонов импорта расписаний
Формат N1
Формат N2
Формат N3 («Сетка»)
Приложение 4. Перечень сокращений
Приложение 5. Технические требования к оборудованию
Список использованной литературы

В экспериментах, упомянутых в [29], была также рассмотрена практическая однокритериальная задача. Решение задачи минимального количества пересадок значительно быстрее (по результатам эксперимента примерно в 4 раза) на маршрутном графе, чем на реальном время-расширенном графе. Это согласуется с тем фактом, что граф меньше, но также статичен, как и время-расширенный граф.
Что касается реальной задачи наискорейшего прибытия, картина выглядит по-другому: Среднее время работы на время-расширенном и время-зависимом графе почти равны, наблюдалась разница примерно в 1.5 раза. Сравнивая среднее время работы для решения упрощенной задачи наискорейшего прибытия с реальной задачей, время-расширеное решение работает немного быстрее (не более чем в 2 раза), в то время как упрощенная время-зависимая реализация оказалась быстрее в 5 раз.
Нахождение всех подходящих путей с учетом времени пути, стоимости, количества пересадок, естественно, гораздо сложнее, чем просто поиск наискорейшего пути. В реализации [20] такой поиск требует в 10 раз больше времени, чем поиск по одному критерию. Для многокритериальной задачи требуется более эффективная техника.
1.7 Методы ускорения алгоритмов поиска на транспорте
С теоретической точки зрения проблема поиска кратчайшего пути из одного узла в другой на графе с заданным весом ребер хорошо исследована. Так, с использованием кучи Фибоначчи реализация алгоритма Дийкстры работает со скоростью 0(m + n log п), где п — количество узлов и m - количество ребер [6]. Однако на практике возникают ограничения с использованием этого и других модификаций алгоритма. Сервер должен быть способен быстро обслужить большое количество запросов по поиску кратчайшего пути. Но, например, свободная память на запоминающем устройстве может быть ограничена. В этом параграфе описываются некоторые способы ускорения поиска с помощью известных алгоритмов, которые могут быть реализованы на практике.
Алгоритм называется сохраняющим расстояния, если он находит оптимальный путь для любого запроса. На практике алгоритмы, сохраняющие расстояния, используются не очень часто, так как время работы таких алгоритмов обычно оказывается недопустимо большим. Далее будут описаны техники, которые позволяют ускорить работу алгоритмов, сохранив точность поиска.
Некоторые источники описывают техники ускорения алгоритма Дийкстры, но не дают никаких практических сравнений и результатов [2], [14]. Много работ с научной точки зрения направлены на изучение дерева кратчайших путей из одной вершины. В других работах (например, в [5]) рассматривается структура очереди приоритетов. Техники ускорения алгоритма Дийкстры — это иной алгоритмический подход к рассматриваемой задаче. Речь будет идти о конкретных модификациях алгоритма