Настройка Dijkstra для транзитной маршрутизации - минимизировать изменения маршрута

Question

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

Я хотя бы попытался использовать вариант Дейкстры, чтобы найти лучший маршрут. При поиске следующих ребер, которые нужно рассмотреть, алгоритм смотрит только на ребра, время вылета которых совпадает с текущим временем поездки. Существует несколько частей графика, на которых автобусы прибывают и отправляются из одной и той же серии серий остановок одновременно. Чтобы предотвратить ненужное переключение автобусов, я добавляю стоимость к изменениям маршрута при выборе лучшего ребра. Это сработало на удивление хорошо и довольно быстро.

Проблема, с которой я столкнулся, заключается в выборе первого автобуса. Рассмотрим следующий сценарий:

Дейкстра предпочтет сесть на автобус А, потому что он прибывает на остановку 2 первым. Если вы собираетесь остановить 2, это здорово. Но если вы собираетесь остановиться на 3-м автобусе, автобус B - лучший выбор, и общая стоимость для обоих одинакова. Я не думаю, что смогу избежать жадного характера Дейкстры, но он работает так хорошо для всего остального, я не хочу отказываться от него, если мне не нужно.

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

Answer 1

Ответы были действительно полезны. Я закончил тем, что сделал немного другое, но вдохновленный идеями здесь. Как правило, каждой остановке назначены «выходы» для каждого автобусного маршрута с ребрами, выходящими из остановки. Чтобы автобус A дошел до остановки 3, ему нужно войти в остановку 2, а затем выйти на выезде «B». За входы на станцию ​​взимается дополнительная плата. Автобусы могут обойти станцию ​​бесплатно, если маршруты совпадают. Таким образом, автобусу «B» никогда не нужно входить в остановку 2, чтобы перейти к остановке 3, а шине А. это необходимо.

Это позволяет любому автобусу быть кратчайшим маршрутом до остановки 2 и позволяет обоим автобусам добраться до остановки 3. Но если вы собираетесь остановиться до остановки 3 от остановки 1, то запуск на автобусе B будет наиболее дешевым маршрутом, поскольку он не ' нужно пройти через станцию ​​и понести дополнительные расходы.

Answer 2

Вы можете использовать простые Дейкстры на большом графике, построенном следующим образом:

• Узлы описываются тройками (L, T, B). Каждый раз, когда автобус B прибывает или отправляется из местоположения L во время T, создайте узел (L, T, B).
• Создание направленного ребра для каждого сегмента автобусного маршрута. То есть, если автобус B отправляется из местоположения L1 во время T1 и прибывает в местоположение L2 во время T2, добавьте ребро (L1, T1, B) -> (L2, T2, B) со стоимостью T2 - T1 (или любой другой разумной стоимостью). , может быть в зависимости от тарифа).
• Добавить ребра, соответствующие "остановке в автобусе". Если автобус B прибывает в пункт L во время T1 и позже отправляется из того же места во время T2, добавьте ребро (L, T1, B) -> (L, T2, B) со стоимостью T2 - T1.
• Добавить ребра, соответствующие "переключению шин". Добавьте направленное ребро от N1 = (L, T1, B1) до N2 = (L, T2, B2) со стоимостью T2 - T1 + epsilon, если верно следующее:
  • N1 - это узел "прибытия" (автобус B1 прибывает в L в момент T1)
  • N2 является узлом "отправления" (автобус B2 отправляется с L в момент T2)
  • T1 < T2 и B1 != B2

На этом графике стоимость пути - это общее время плюс c * epsilon, где c - это количество смен шины. epsilon представляет «стоимость» переключения шин. Например, если кто-то одинаково предпочитает «оставаться в автобусе» и «переключаться на автобусы, но экономить 2 минуты», то epsilon должно составлять 2 минуты.

Вы также можете добавить «минимальное время переключения» S, изменив неравенство T1 < T2 на T1 + S < T2. Это исключит ребра, где T1 и T2 настолько близки, что кто-то не может разумно переключать автобусы вовремя.

Answer 3

Другое предложение

Вместо добавления узлов. Вы можете просто больше краев. Вместо представления автобусного маршрута (A -> B -> C), как вы представляете его следующим образом:

A -> B

A -> C

B -> C

Для каждого ребра вы прибавляете к стоимости времени, которое требуется, чтобы сесть на автобус и сойти с него.

Answer 4

Похоже, вам нужно добавить стоимость перевода на свой график.

Первое, что приходит мне в голову, вероятно, не лучшее решение, это добавлять дополнительные узлы вокруг ваших остановок. Таким образом, вместо StopB у вас будет

Стоп-Б сойти с автобуса-А Стоп-B Стоп-Б сесть на Автобус-Б

Для каждой остановки вам придется делать это на всех автобусах.

Возможно, есть лучшие варианты. Это первое, что я могу придумать за 2 минуты.