Я делаю планировщик поездок (или приложение общего расписания) для всех видов общественного транспорта в моей стране (автобус / поезд / воздух).
Состояние проекта находится на промежуточном этапе, теперь мне немного сложно выполнить более сложную часть приложения.
Чтобы описать текущий статус:
Данные хранятся в базе данных MySQL, смоделированной как GTFS (General (Google) Transit Feed Specification).
Я получаю прямые маршруты, просто запрашивая базу данных (объединение двух временных таблиц, я считаю это достаточно эффективным)
В настоящее время это сделано на PHP, но при необходимости я могу переработать его на Java.
Итак, когда есть прямая связь между двумя точками, все в порядке. Сложнее всего совершить путешествие, когда нет прямых линий.
Допустим, пользователь хочет отправиться из city A в city D, но поскольку между этими городами нет прямых линий, ему нужно проехать через city B и city C.
Как я могу получить оптимизированные маршруты и трансферы в этой ситуации?
Мои идеи пока что тяготеют к использованию графика, но в этом случае мне нужен Зависящий от времени направленный взвешенный мультиграф, и я действительно не знаю в данный момент, как реализовать Time- Зависимая часть.
Получить только маршрут можно с помощью алгоритмов Dijkstra, A* или Floyd–Warshall, но поскольку вылеты бывают в разное время, я не уверен, как это будет реализовано, чтобы получить оптимальное решение. Мне нужно учитывать продолжительность сегмента (от A до B, от B до C), время ожидания передачи, возможно, расстояние тоже.
Чтобы уточнить, мне не нужен ни один результат. Я хочу получать ежедневный список всех отправлений из city A, которые могут привести пользователя к city D, с пересадками, если это необходимо.
По сути, я пытаюсь получить что-то вроде этого (взято с Болгарских железных дорог или, если уж на то пошло, с любого другого железнодорожного узла), список всех отправлений за выбранный день с Sofia на Kystendil с пересадкой в Radomir при необходимости:
Что касается части решения графа, я могу создать приложение на Java, используя jGraphT, кэшировать результаты (они меняются один раз в несколько месяцев, может быть), и использовать их в PHP (или вызывать приложение через PHP).
Если я не совсем ясен, спросите, пожалуйста.
Я знаю, что это делается так много раз (решения есть почти на любом веб-сайте поездов), но я не знаю, по каким терминам даже искать.
Итак, мой вопрос: может ли кто-нибудь дать мне совет, как решить эту проблему?
Или, по крайней мере, по каким терминам мне искать идеи и как это делать.
Может быть, какие-нибудь предложения для других сайтов в сети StackExchange.
Спасибо.
