Алгоритмы поиска пути (маршрутизация, планирование поездки, ...) на графиках с временными ограничениями - PullRequest
Новая
       28

Алгоритмы поиска пути (маршрутизация, планирование поездки, ...) на графиках с временными ограничениями

26 голосов
/ 30 августа 2011

У меня есть база данных автобусных / железнодорожных / ... остановок и времени прибытия / отправления на каждую дату и так далее. Я ищу способ поиска самого быстрого (самого короткого / самого дешевого / наименьшего количества переходов) между двумя местоположениями. Я хотел бы иметь произвольные местоположения в будущем, используя данные OpenStreetMap для обхода между остановками и от остановок до начала / конца, однако на данный момент я просто хочу найти путь между двумя остановками в базе данных.

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

Я обнаружил формат GTFS , используемый в Google Transit . Хотя мой город не предоставляет общедоступный канал данных (даже частный), у меня уже есть вся важная информация, содержащаяся в GTFS, и преобразование будет тривиальным.

Существует некоторое основанное на GTFS программное обеспечение, такое как OpenTripPlanner , которое также может выполнять маршрутизацию пешеходов / автомобилей / велосипедов с использованием OpenStreetMap .

Однако , код маршрутизации недостаточно хорошо задокументирован (по крайней мере, из того, что я нашел), и мне все это не нужно.

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

Итак, вопрос , учитывая список остановок, маршрутов и времени прибытия / отправления / путешествия, как я могу легко найти самый быстрый путь от остановки A до остановки B?

1 Ответ

16 голосов
/ 30 августа 2011
  1. Смоделируйте вашу проблему как график .Каждая станция будет Vertex, а каждый автобус / поезд - Edge.
  2. создайте функцию w:Edges->R, которая указывает время / деньги / ... для каждого края.
  3. Теперь у вас есть типичная проблема минимального пути, которая может быть решена с помощью алгоритма Дейкстры , который находит минимальный путь ко всем вершинам из данного источника.

(*) Для «наименьших переходов» ваш вес фактически равен 1 для каждого ребра, поэтому вы даже можете оптимизировать его, запустив двунаправленный BFS вместо dijkstra, как я объяснил в этом посте [Это объясняется для социальной дистанции, но на самом деле это тот же алгоритм].

РЕДАКТИРОВАТЬ
какизменение нестатической природы графика [для времени], которое вы упомянули в комментариях [для цены и количества переходов, то, что я упомянул выше, по-прежнему применимо, поскольку эти графики являются статическими], вы можете использовать расстояние векторный алгоритм маршрутизации , который фактически предназначен для работы с динамическими графами и представляет собой распределенную разновидность алгоритма Беллмана Форда .
Идея алгоритма:

  • периодически, каждая вершина отправляет свой «вектор расстояний» своим соседям [вектор указывает, сколько «стоит» проехать от отправляющеговершина, друг к другу вершина.
  • Соседи пытаются обновить свои таблицы маршрутизации [по какому краю лучше всего перейти к каждой цели]
  • для вашего случая каждый узел знает, что являетсясамый быстрый способ добраться до своих соседей, [время в пути + время ожидания], и он [вершина / станция] добавляет это число к каждому элементу в векторе расстояния, чтобы знать, как и сколько времени это займет, чтобыдобраться до места назначения.Когда автобус уходит, время прохождения должно быть пересчитано для всех узлов [из этого источника], и новый вектор должен быть отправлен его соседям
...