I have been involved in development of one journy planner system for Stockholm Public Transportation in Sweden. It was based on Djikstra’s algorithm but with termination before every node was visited in the system. Today when there are reliable coordinates available for each stop, I guess the A* algorithm would be the choise.
Data about upcoming trafic was extracted from several databases regularly and compiled into large tables loaded into memory of our search server cluster.
One key to a sucessfull algorith was using a path cost function based on travel and waiting time multiplied by diffrent weightes. Known in Swedish as “kresu”-time these weighted times reflect the fact that, for example, one minute’s waiting time is typically equivalent in “inconvenience” to two minutes of travelling time.
KRESU Weight table
- x1 – Travel time
- x2 – Walking between stops
- x2 – Waiting at a stop
during the journey. Stops under roof,
with shops, etc can get a slightly
lower weight and crowded stations a
higher to tune the algorithm. - The weight for the waiting time at the first stop is a function of trafic intensity and can be between 0.5 to 3.
Data structure
Area
A named area where you journey can start or end. A Bus Stop could be an area with two Stops. A larger Station with several platforms could be one area with one stop for each platform.
Data: Name, Stops in area
Stops
An array with all bus stops, train and underground stations. Note that you usually need two stops, one for each direction, because it takes some time to cross the street or walk to the other platform.
Data: Name, Links, Nodes
Links
A list with other stops you can reach by walking from this stop.
Data: Other Stop, Time to walk to other Stop
Lines/Tours
You have a number on the bus and a destination. The bus starts at one stop and passes several stops on its way to the destination.
Data: Number, Name, Destination
Nodes
Usually you have a timetable with the least the time for when it should be at the first and last stop in a Tour. Each time a bus/train passes a stop you add a new node to the array. This table can have millions of values per day.
Data: Line/Tour, Stop, Arrival Time, Departure Time, Error margin, Next Node in Tour
Search
Array with the same size as the Nodes array used to store how you got there and the path cost.
Data: Back-link with Previous Node (not set if Node is unvisited), Path Cost (infinit for unvisited)