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

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

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

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

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

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

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

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

Ответ 1

Моделируйте свою проблему как graph. Каждая станция будет Vertex, и каждый автобус/поезд будет Edge.
создайте функцию w:Edges->R, которая указывает время/деньги/... для каждого ребра.
теперь у вас типичная проблема с минимальным пути, которая может быть решена Dijkstra algorithm, который находит минимальный путь ко всем вершинам из данного источника.

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

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

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