Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I am building a bus routes map for Chennai. I use Postgis. In our database we have one table having all the routes along with unique ids given for them. Second table comprises of bus stop names with its latitude and longitudes. The third table joins the first and second table based on their ids. We have track records for the routes.

I want to construct a function for finding the shortest route between 2 stops which don’t have a common route. For eg, Two stops A and B exist which don’t have any common routes. Say there are 3 other stops- C,D,E. I want to find out which route should I take to travel the shortest distance. If I leave from A, should I get off at C and from C take a bus to B, or get off at C take another bus to D and from there another bus to B, or go to E and then take a bus. Basically I want to find the shortest path for two stops without a common route. Since my database is enormous that needs to be considered while choosing an Algorithm cause it shouldn’t slow down the process.

Could someone please suggest a suitable algorithm which doesn’t take much time?

share|improve this question
2  
you might need PgRouting(pgrouting.org/)..an excellent practical solution written by our GisSe admin is here..underdark.wordpress.com/2011/02/07/… –  vinayan Aug 25 '12 at 10:03
    
Yeah, pgRouting will be ideal for your situation. You can also have a look at workshop.pgrouting.org after that introduction by @underdark. –  okello Aug 25 '12 at 10:57
    
If this is a transportation planning exercise, you're better off aggregating the stops into a multi-tier system going from more aggregate to disaggregate. The bigger zones tell you about regional traffic, then as the zones get smaller, you can tell more about traffic dynamics and patterns. Determining a Transit O/D (between each stop) is not that beneficial from the grand scheme of things –  dassouki Aug 26 '12 at 3:39
    
shortest route is not necessarily the best solution to the problem, since most customers will want a shortest time solution, which depends on the bus schedules. Of course, that's a much harder problem and requires additional data. –  Llaves Aug 26 '12 at 5:09
    
to add to @Llaves comment, perhaps look into shortest "Cost" where cost is a function of time, distance, $, and any other variable you would like to add to it –  dassouki Aug 26 '12 at 10:59
show 1 more comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.