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?

  • 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.