Public Transportation using Buses in City

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 locatio开发者_如何学Cns 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.

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!

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.

I think the most important optimization is separating stations where you can change routes and stations where you can't. Then you just need to consider stations where you can change route as intermediate stations in your graph. This should make the graph so small that Dijkstra is fine.

I'm distinguishing nodes with only two edges by simply cutting them out of the graph and instead connecting their two neighbors with an edge of the added length. Then I do pathfinding on this reduced graph which should be much faster. i.e. only consider stations where one might switch routes.

Maybe you can have some use of paddydubs work for TransportDublin found on github.

I coded such an algorithm for a test application. I had a dictionary for each stop, as source and as destination. The algorithm was recursive. Each step of the recursion was like this: Given source and target, it would generate a list of routes going into target, list of routes leaving source. If there were any common stops, we were done, we report the route. If not, then I generate neighboring stops for source, and recurse. The next recursion generates list of neighboring stops for sink, recurse. Before recursion I recorded the previous path of course, and at the end I would have a list.

I do remember I had to place some cutoff conditions because the recursion would sometimes get stuck in certain "bad" regions.

I also looked at this paper:

www.citeulike.org/user/rchauhan/article/819528

I am interested if you managed to solve this problem in a different way.