Map Routing, a la Google Maps?

Question

I've always been intrigued by Map Routing, but I've never found any good introductory (or even advanced!) level tutorials on it. Does anybody have any pointers, hints, etc?

Update: I'm primarily looking for pointers as to how a map system is implemented (data structures, algorithms, etc).

Answer 1

I've yet to find a good tutorial on routing but there are lots of code to read:

There are GPL routing applications that use Openstreetmap data, e.g. Gosmore which works on Windows (+ mobile) and Linux. There are a number of interesting [applications using the same data, but gosmore has some cool uses e.g. interface with websites.

The biggest problem with routing is bad data, and you never get good enough data. So if you want to try it keep your test very local so you can control the data better.

Answer 2

Barry Brumitt, one of the engineers of Google maps route finding feature, wrote a post on the topic that may be of interest:

The road to better path-finding 11/06/2007 03:47:00 PM

Answer 3

Take a look at the open street map project to see how this sort of thing is being tackled in a truely free software project using only user supplied and licensed data and have a wiki containing stuff you might find interesting.

A few years back the guys involved where pretty easy going and answered lots of questions I had so I see no reason why they still aren't a nice bunch.

Answer 4

Another thought occurs to me regarding the cost of each traversal, but would increase the time and processing power required to compute.

Example: There are 3 ways I can take (where I live) to go from point A to B, according to the GoogleMaps. Garmin units offer each of these 3 paths in the Quickest route calculation. After traversing each of these routes many times and averaging (obviously there will be errors depending on the time of day, amount of caffeine etc.), I feel the algorithms could take into account the number of bends in the road for high level of accuracy, e.g. straight road of 1 mile will be quicker than a 1 mile road with sharp bends in it. Not a practical suggestion but certainly one I use to improve the result set of my daily commute.

Answer 5

By Map Routing, you mean finding the shortest path along a street network?

Dijkstra shortest-path algorithm is the best known. Wikipedia has not a bad intro: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

There's a Java applet here where you can see it in action: http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html and Google you lead you to source code in just about any language.

Any real implementation for generating driving routes will include quite a bit of data on the street network that describes the costs associate with traversing links and nodes—road network hierarchy, average speed, intersection priority, traffic signal linking, banned turns etc.

Answer 6

A* is actually far closer to production mapping algorithms. It requires quite a bit less exploration compared to Dijikstra's original algorithm.