Введение
Глава 1. Обзор алгоритмов и информационных систем на пассажирском транспорте . 7
1.1 Проблема поиска пути проезда на пассажирском транспорте 7
1.2 Справочное обслуживание пассажиров в россии 7
1.2.1 Система «экспресс» 9
1.2.2 Система «СИРЕНА» 10
1.2.3 Другие источники справочной информации в России 10
1.3 Зарубежный опыт разработки информационных систем на транспорте 11
1.4 Алгоритмы поиска кратчайшего пути на графе 14
1.5 Алгоритм для поиска пути в пространстве 18
1.6 Алгоритмы поиска маршрута на пассажирском транспорте 19
1.6.1 Подходы к поиску маршрута и формулировка задачи 19
1.6.2 Базовое моделирование: Задача наискорейшего прибытия 23
1.6.3 Моделирование реальной задачи 25
1.6.4 Многокритериальная оптимизация 29
1.6.5 Приближенные подходы при многокритериальной оптимизации 31
1.6.6 Производительность известных алгоритмов поиска 34
1.7 Методы ускорения алгоритмов поиска на транспорте 35
1.8 Архитектуры построения распределенных систем кэширования 38
1.8.1 Кэширование данных 39
1.8.2 Обзор архитектур кэширования в интернет 41
1.8.3 Аналитическая модель распределенного кэширования 44
1.8.4 Сравнение архитектур кэширования и ограничения моделей 46
1.9 Постановка задачи поиска пути 47
Глава 2. Разработка алгоритмов и архитектуры информационно-справочной системы 50
2.1 Разработка оригинального алгоритма поиска 50
2.1.1 Алгоритм оптимистического поиска на графе 51
2.1.2 Оригинальное представление графа в памяти компьютера 52
2.1.3 Методы ускорения алгоритма поиска на графе 53
2.1.4 Препроцессинг данных в реальном времени 56
2.1.5 Выбор наискорейшего пути из найденного набора 57
2.1.6 Проверка наличия свободных мест 58
2.2 Взаимодействие с источниками данных 58
2.2.1 Постановка задачи о взаимодействии с источником 59
2.2.2 Вы бор архитектуры в зависимости от параметров 61
2.3 Цикл обслуживания запроса 63
2.4 Аналитический выбор архитектуры справочной системы 66
2.4.1 Постановка задачи выбора архитектуры 68
2.4.2 Аналитическая модель 69
2.4.3 Сетевой уровень запроса 71
2.4.4 Частота запросов к серверам 72
2.4.5 Время передачи документа 72
2.4.6 Время полной обработки запроса 73
Глава 3. Программная реализация информационно-справочной системы 75
3.2 Специализированная база данных 77
3.3 Средства подготовки исходных данных 78
3.4 Средства импорта данных в базу данных системы 82
3.4.1 Загрузка географических данных 83
3.4.2 Импорт данных о расписаниях 85
3.4.3 Корректировка данных в графе 85
3.5 Реализация алгоритма поиска. модуль ядра 87
3.6 Программа управления системой 88
3.7 Подсистема интеграции с внешними системами 89
3.7.1 Описание процесса взаимодействия 89
3.7.2 Интеграция с системой «ЭКСПРЕСС». Эмулятор терминала 91
3.7.3 Программа контроля процесса взаимодействия 92
3.8 Интернет-портал доступа к справочной системе 92
Глава 4. Анализ результатов поиска и исследование информационно-справочной системы 100
4.1 Сравнение результатов поиска с известными маршрутами проезда 100
4.1.1 Поиск прямого маршрута 100
4.1.2 Поиск пути проезда с пересадкой на одном виде транспорта 101
4.1.3 Поиск пути с пересадкой на нескольких видах транспорта 102
4.1.4 Поиск пути с пересадкой с учетом даты поездки 103
4.1.5 Поиск пути с пересадкой вузле с несколькими станциями 103
4.1.6 Поиск пути с несколькими пересадками и с фильтрацией по виду транспорта 104
4.2 Исследование разработанной информационно-справочной системы 106
4.2.1 Плотность графа железных дорог 106
4.2.2 Длина маршрутов поездов дальнего следования 108
4.2.3 Распределение количества пунктов назначения от числа пересадок... 109
4.2.4 Распределение количества пунктов назначения от расстояния 111
4.2.5 Зависимость количества запросов от расстояния между пунктами... 113
4.2.6 Суммарное время обработки запросов информационно-справочной
системой 114
4.2.7 Зависимость времени обработки запроса от расстояния 115
4.3 Производительности модификаций алгоритма поиска 116
Заключение 118
Выводы по теме диссертации 118
