Pathfinding (routing, trip planning, ...) algorithms on graphs with time restrictions
I have a database of bus/train/... stops and the arrival/departure times on each date and so on. I'm looking for a way to do a search for the fastest(shortest/cheapest/least transitions) trip between two locations. I would like to have arbitrary locations in the future, using OpenStreetMap data to do walking between stops and from stops to start/end, however for the time being I just want to find path between two stops in the database.
The problem is I can't seem to find much info about this subject, for example this Wikipedia page has a lot of text with absolutely no useful information in it.
What I've found is the GTFS format, used in Google Transit. While my city doesn't provide a public data feed (not even a private one), I already have all the important information that the GTFS contains and making a transformation would be trivial.
There is some GTFS-based software, like like OpenTripPlanner that can also do pedestrian/car/bike routing using OpenStreetMap.
However, the routing code isn't well documented (at least from I've found) and I don't need the whole thing.
All I'm looking for is some good overview of the algorithms I could use, their performance, maybe some pseudocode.
So, the question is, given a list of stops, routes and arrival/departure/travel times, how can I easily find the fastest path from stop A to stop B?
Answer
- Model your problem as a graph. Each station will be a Vertex, and each bus/train will be an Edge.
- create a function
w:Edges->R,that indicates the time/money/... for each edge. - now, you have a typical minimum path problem, which can be solved by Dijkstra algorithm, which finds minimum path to all vertices from a given source.
(*) For 'least transitions', your weight is actually 1 for each edge, so you can even optimize this by running a BFS or even bi-directional BFS instead of dijkstra, as I explained in this post [It is explained for social distance, but it is the same algorithm actually].
EDIT
as an edit to the non-static nature of the graph [for timing] you mentioned on comments [for price and number of transitions, what I have mentioned above still applies, since these graphs are static], you can use a distance vector routing algorithm, which actually meant to work for dynamic graphs, and is a distributed variation of Bellman Ford algorithm.
The algorithm idea:
- periodically, every vertex sends its "distances vector" to its neighbors [the vector indicates how much it 'costs' to travel from the sending vertex, to each other vertex.
- Its neighbors try to update their routing tables [through which edge is it best to move to the each target]
- for your case, each node knows what is the fastest way to get to its neighbors, [travel time + wait time] and it [the vertex/station] adds this number to each entree in the distance vector, in order to know how to and how much time it will take, to get to the destination. When a bus leaves, the travel time should be re-calculated to all nodes [from this source], and the new vector should be sent to its neighbors