Ask HN: How is routing done on maps? | Hacker News Reader

Ask HN: How is routing done on maps?

6 pointsSingAlong9 comments

I've seen Google and Yahoo doing routing on maps but now even a small startup in my locality have a routing API (so it sounds that its not expensive). How do they find out routes on maps?

Is there any method to do it? I'm trying to solve a problem that needs routing data and would like to know the route points of service roads etc, which Google or Yahoo Maps do not show (they mark only the shortest routes).

View on HN

I'm pretty sure Google uses a variant of Dijkstra's algorithm by default.

Here's a thread where they go through how to use Dijkstra's manually with the GMaps API:

http://groups.google.com/group/Google-Maps-API/browse_thread...

Check out http://www.openstreetmap.org. They provide open-source map data and code (like rana which has a module for routing) that does least-cost routing. There are a variety of approaches based on simple graph algorithms like naive A*.

Yeah, but I need to have the routing points right?

naive A* Can you explain?

And what's rana? All I need is route points between places even for service roads via programatic access (an API). I would like links to free resources (I'm a student)

Yeah, I wasn't sure what kind of answer you were looking for. OSM provides exports of the street data which gives you the ability to either:

A. Run a pre-existing routing program on it, such as http://wiki.openstreetmap.org/index.php/Rana, or

B. Write your own (which would require knowledge of algorithms such as http://en.wikipedia.org/wiki/A*_search_algorithm)

There are also services where people do these things for you, and for low volume, they might not mind if you programmatically scrape their results. A good example is http://www.batchgeocode.com/

Properly, Rana isn't intended as a package for programmatic access, but it does include code which does what you want:

* http://wiki.openstreetmap.org/wiki/PyrouteLib - Pyroute is probably exactly what you want.

* Rana's routing module: http://wiki.openstreetmap.org/wiki/Rana/Modules#route

I just tried Gosmore (found about it on the OSM wiki). installing it on my ubuntu seems to be a bit tricky, so I haven't yet installed it (some errors).

Rana and Pyroute sound cool to me since they are in PYthon. And the software requirements to run rana or Pyroute match my system (linux). So I'll choose one of those after trying both.

Thanks for the tip

Sure thing. You may as well try Pyroute first, since the system requirements there are a subset of the Rana requirements (it doesn't require GTK or Cairo, etc).

Though Google shows the shortest route by default, you can drag the line to select alternate routes, and the instant updating suggests the other paths are already locally loaded. So their APIs may already provide (or leak) enough info for you.

But even if they don't, you can probably buy the same data from their source or another provider. (See that little 'Tele Atlas' copyright at the bottom of Google Maps? Or 'NAVTEQ' at the bottom of Yahoo Maps?)

I haven't done a lot of research on this but don't they use a few metrics other than just the basic distance between the two end points? I would think it is a weighted average of a few metrics. Distance, average time(they have traffic data), number of stop lights, etc....

AFAICT, they prefer shortest time route, not shortest distance.

Reply on news.ycombinator.com