Составление маршрута на основе расписания при помощи алгоритма кратчайших путей
Ключевые слова и синонимы
Информационная система для пассажиров; поиск в расписании; планировщик поездок; планировщик путешествий
Постановка задачи
Рассмотрим задачу планирования маршрута для пассажиров общественного транспорта, идущего по графику. Здесь в качестве примера рассматривается железнодорожная система, но обсуждение в равной степени применимо к автобусам, легкорельсовому транспорту и аналогичным системам. Точнее говоря, задача состоит в том, чтобы построить информационную систему расписания, которая на основании подробных графиков движения всех поездов предоставит пассажирам хорошие маршруты, включая пересадку между разными поездами.
Решение этой задачи состоит из модели ситуации (например, можно ли в запросах указать ограничение на количество пересадок?), алгоритмического подхода, его математического анализа (всегда ли он возвращает наилучшее решение? гарантируется ли его быстрая работа во всех условиях?) и оценки его работы в условиях реального мира (могут ли путешественники действительно пользоваться созданными маршрутами? достаточно ли быстро работает его реализация на современных компьютерах и реальных данных?).
Основные результаты
Проблема подробно обсуждается в обзорной статье [6].
Моделирование
В упрощенной модели предполагается, что пересадка между поездами не занимает времени. В более реалистичной модели задается определенное минимальное время пересадки на каждой станции. Кроме того, необходимо определить целевую функцию оптимизационной задачи. Должен ли маршрут быть как можно более быстрым, или как можно более дешевым, или содержать как можно меньше пересадок? Существуют различные способы решения этой задачи, рассмотренные в [6]; все они берут начало в многоцелевой оптимизации – например, ограничения на ресурсы или решения, оптимальные по Парето. С практической точки зрения предпочтения пассажира обычно трудно смоделировать математически, но можно позволить пользователю самому выбрать лучший вариант из множества разумных маршрутов. Например, можно вычислить все маршруты, не уступающие какому-либо другому маршруту по всем рассматриваемым аспектам. На практике оказывается, что в реальных расписаниях количество таких маршрутов не слишком велико, поэтому такой подход является вычислительно реализуемым и удобным для пассажира [5]. Кроме того, структура тарифов у большинства железных дорог довольно сложна [4] – в основном потому, что тарифы обычно не аддитивны, то есть тариф за всю поездку не является суммой тарифов ее частей.
Алгоритмические модели
В литературе предлагаются две основные идеи по поволд того, как преобразовать эту ситуацию в задачу о кратчайшем пути на графе. В качестве примера рассмотрим упрощенную модель, в которой пересадка не занимает времени, в запросах указываются время начала поездки и станция, а результатом запроса должен быть маршрут с самым ранним временем прибытия в пункт назначения.
В модели, растянутой по времени [11, каждое событие прибытия и отправления в расписании является вершиной ориентированного графа. Дуги графа представляют собой последовательные события на одной станции и прямые согласования поездов. Длина дуги задается разницей во времени между ее конечными вершинами. Пусть s – вершина на станции отправления, время которой непосредственно следует за начальным временем. Кратчайший путь от s до любой вершины станции назначения является оптимальным маршрутом.
В модели, зависящей от времени [3, 7, 9, 10], вершины моделируют станции, а дуги означают наличие прямого (безостановочного) железнодорожного сообщения. Вместо длины ребра, дуги помечаются функциями обхода ребра, которые сообщают время прибытия в конечную точку дуги в зависимости от времени начала движения пассажира в начале дуги, отражая время, фактически проходимое поездом. Для решения этой зависящей от времени задачи о кратчайшем пути можно использовать модификацию алгоритма Дейкстры. Используя структуру этой ситуации, можно выбрать такое представление графа, которое позволяет оценивать функции обхода звеньев за константное время [3]. Для создания более реалистичных моделей пересадок можно использовать более сложный граф.
Кроме того, многие из методов ускорения вычислений кратчайших путей могут быть применены к результатам запросов к графу.
Применение
Основным направлением применения являются информационные системы расписаний для транзитных перевозок, выполняемых по графику (автобусы, поезда и т. д.). Это распространяется и на планирование маршрутов, если в таких системах разрешены поездки – как, например, при детализированном моделировании трафика для вычисления самых быстрых маршрутов [2].
Открытые вопросы
Необходимо повышение скорости вычислений, в частности, для полной интеграции расписаний и многокритериального случая. Также хотелось бы расширить задачу на динамический случай, в котором отражается текущая реальная ситуация, то есть задержка или отмена поездов, а также другие временные изменения в расписании.
Экспериментальные результаты
Цитируемая литература, как правило, содержит экспериментальные результаты [2, 4, 5, 6, 7, 8, 9, 10, 11]. Зависящий от времени подход может быть значительно быстрее, чем растянутый по времени. В частности, для упрощенных моделей наблюдается ускорение в диапазоне 10–45 раз [8, 10]. Для более детализированных моделей производительность обоих подходов оказывается сравнимой [6].
См. также
- Конкурс по реализации алгоритмов поиска кратчайших путей
- Маршрутизация в дорожных сетях с транзитными узлами
- Алгоритм поиска кратчайших путей с единственным источником
Литература
1. Gerards, B., Marchetti-Spaccamela, A. (eds.): Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'03) 2003. Electronic Notes in The oretical Computer Science, vol. 92. Elsevier (2004)
2. Barrett, C.L., Bisset, K., Jacob, R., Konjevod, G., Marathe, M.V.: Classical and contemporary shortest path problems in road networks: Implementation and experimental analysis of the TRANSIMS router. In: Algorithms - ESA 2002: 10th Annual European Symposium, Rome, Italy, 17-21 September 2002. Lecture Notes Computer Science, vol. 2461, pp. 126-138. Springer, Berlin (2002)
3. Brodal, G.S., Jacob, R.: Time-dependent networks as models to achieve fast exact time-table queries. In: Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'03), 2003, [1 ], pp. 3-15
4. Muller-Hannemann, M., Schnee, M.: Paying less for train connections with MOTIS. In: Kroon, L.G., Mohring, R.H. (eds.) Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'05), Dagstuhl, Germany, Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany 2006. Dagstuhl Seminar Proceedings, no. 06901
5. Muller-Hannemann, M., Schnee, M.: Finding all attractive train connections by multi-criteria pareto search. In: Geraets, F., Kroon, L.G., Schobel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization, International Dagstuhl Workshop, Dagstuhl Castle, Germany, June 20-25, 2004, 4th International Workshop, ATMOS 2004, Bergen, September 16-17, 2004, Revised Selected Papers, Lecture Notes in Computer Science, vol. 4359, pp. 246-263. Springer, Berlin (2007)
6. Muller-Hannemann, M., Schulz, F., Wagner, D., Zaroliagis, C.D.: Timetable information: Models and algorithms. In: Geraets, F., Kroon, L.G., Schobel, A., Wagner, D., Zaroliagis, C.D. (eds.) Algorithmic Methods for Railway Optimization, International Dagstuhl Workshop, Dagstuhl Castle, Germany, June 20-25, 2004, 4th International Workshop, ATMOS 2004, Bergen, September 16-17, 2004, Revised Selected Papers, Lecture Notes in Computer Science, vol. 4359, pp. 67-90. Springer (2007)
7. Nachtigall, K.: Time depending shortest-path problems with applications to railway networks. Eur. J. Oper. Res. 83,154-166 (1995)
8. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Experimental comparison of shortest path approaches for timetable information. In: Proceedings 6th Workshop on Algorithm Engineering and Experiments (ALENEX), Society for Industrial and Applied Mathematics, 2004, pp. 88-99
9. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Towards realistic modeling of time-table information through the time-dependent approach. In: Proceedings of the 3rd Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'03), 2003, [1 ], pp. 85-103
10. Pyrga, E., Schulz, F., Wagner, D., Zaroliagis, C.: Efficient models for timetable information in public transportation systems. J. Exp. Algorithmics 12, 2.4 (2007)
11. Schulz, F., Wagner, D., Weihe, K.: Dijkstra's algorithm on-line: An empirical case study from public railroad transport. J. Exp. Algorithmics 5 1-23 (2000)