Public Transportation using Buses in City

Question

I am developing a Journey Planner website. There are few things that are simple in this case currently i.e. Right now the website will only be able to plan bus routes, the timings of buses are not currently available. So this means we only have bus routes stored in the db and since bus timings are not available so waiting times for traveler are not relevant as well. What is available is the time and distance covered between two stops for an individual bus.

I think that using an undirected weighted graph storing the time and distance costs of each bus stop for each individual bus would be the way to go. Then I could use Dijkstra algorithm to calculate the shortest path between two locations entered by the user based on either time or distance as per user preference. I would find out whether two or three buses are required through simple C# functions if the bus routes intersect at stops and then using those intersection stops for the traveler to change the bus. But there would be an individual graph for each bus. An alternative (not sure if this is correct) way would be to use a graph containing every bus stop of city as nodes and then using this technique to find out the way to travel between two stops. Which is the correct approach? Should I use A* algorithm in place of Dijkstra algo?

A few general points for the design: I would like the app to be extensible so I could add other transportation means later when the need arises. Moreover the bus times could also be added later if possible without major changes to the website. I have seen quite a few experts here who have worked on much complex projects of transportation. So please help me out with the best way to implement this functionality in the most scalable, modular and extensible fashion.

Answer 1

A graph is going to have to be a directional graph - bus stops on opposite sides of the roads (even in a country like the UK that rarely has medians) are NOT the same stop!

Answer 2

I started a similar application last summer and never finished it, but I do have some advice on this graph, and how to structure your data.

My plan was to have each stop as a node, and a path between each of these nodes for every time a bus went through. For example, if a bus stopped every half hour over a 6 hour period, then there would be 12 paths between the two nodes. Time was the main driver behind "cost" of the path, so typically the soonest path would be the one chosen.

Before starting the application would query the database for all paths in the next 5 hours (adjust as appropriate). It would then crunch with Dijkstra's algorithm.

Other things to factor in cost are the actual money cost of the route, transfers (and their cost), stops with no roofs (if you tend to have bad weather), etc.

This plan worked well for me. I live in an area with 3 bus systems.

Finally, it may do you some good to structure your data in a similar way to the Google Transit Feed Specification, as many agencies produce this type of data that you could import.