Как построить оптимальный путь для железнодорожных поездок?
Добрый день.
Пытаюсь разработать планировщик поездок железнодорожным транспортом.
Имеется граф поездов, вершинами которого являются станции, а ребрами соответственно поезда. Одну пару вершин может соединять несколько ребер -> из одной станции в другую может идти несколько поездов.
Так-же в свойствах ребер есть время "в пути", время прибытия и время отправления.
Нужно найти оптимальный путь из вершины А в вершину Б, с учетом времени пересадки (и соответственно ожидания поезда).
Подскажите, пожалуйста, в какую сторону копать?
Пробовал применить алгоритм дейкстры - но не смог разобраться с пересадками (там всегда ищется минимальное время в пути, соответственно алгоритму очень "выгодно" менять поезда, что совсем не выгодно реальному человеку).
Т.е. получается что приходится "расширять" условия задачи: требуется искать не только по одному критерию - времени в пути, но еще и по количеству пересадок, а алгоритм дейкстры "не умеет" искать по двум критериям.
К тому-же, очень хотелось бы иметь возможность искать несколько альтернативных путей.
Может быть есть какое-то другое "решение" или алгоритмы? Думаю я не первый столкнулся с такой задачей, хотелось бы знать в каком направлении копать.
И еще вопрос - время начала пути известно? Иными словами, вам просто надо найти путь из A в Б или есть условие, что из А можно выехать не раньше 12,00 например?
Perzh: сейчас веса в графе проставлены по времени движения; так-же есть время прибытия на станцию, время отправления со станции, легко вычисляется время стоянки (в дальнейшем думаю еще будет цена, но пока такой информации нет) + я пытался во время выполнения прибавлять к времени в пути время стоянки.
Время начала движения не важно (т.е. можно выезжать в любое время), пока даже не учитывая расписание (пока предполагаем что каждый поезд ходит каждый день).
Visphord: не могу придумать(или найти) как "допилить" дейкстру чтобы:
а) минимизировать время в пути и кол-во пересадок: сейчас получается (на примере Москва-Самара): с точки зрения алгоритма вполне логично доехать до станции "Рязань2" за 8460 на поезде 046V, чем на 010J за 10200, а вот для человека такой вариант неприемлем, и мне хотелось бы его исключить.
Москва Казанская-[№046V:8460]-Рязань-2=8460
Рязань-2 - Рязань-1=8460
Рязань-1-[№010J:16740]-Рузаевка=26580
Рузаевка-[№010J:13440]-Сызрань-1=40020
Сызрань-1-[№010J:5940]-Самара=45960
В идеале конечно получить на выходе: поезда без пересадок за время(стоимость) X1, поезда с 1 пересадкой за время(стоимость) X2, поезда с 2 пересадками за время(стоимость) X3, ...
б) найти не один кратчайший путь, а например 5 кратчайших путей: тут пока не придумал ничего кроме как: временно выкинуть из графа поезд с наибольшей стоимостью и попробовать найти еще 1 кратчайший путь (минималистичная вариация алгоритма Йена) -- но работает не во всех случаях.
