Strategy to find your best route via Public Transportation only?

Question

Finding routes for a car is pretty easy: you store a weighted graph of all the roads and you could use Djikstra's algorithm [1]. A bus route is less obvious. With a bus you have to represent things like "wait 10 minutes for the next bus" or "walk one block to another bus stop" and feed those into your pathfinding algorithm.

It's not even always simple for cars. In some cities, some roads are one-way-only into the city in the morning, and one-way-only out of the city in the evening. Some advanced GPSs know how to avoid busy routes during rush hour.

How would you efficiently represent this kind of time-dependent graph and find a route? There is no need for a provably optimal solution; if the traveler wanted to be on time, they would buy a car. ;-)

[1] A wonderful algorithm to mention in an example because everyone's heard of it, though A* is a likelier choice for this application.

Answer 1

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)