4 ms·
Ask HN: How is routing done on maps?
Ask HN: How is routing done on maps?
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).
- rchiniquy 18y agoCheck out http://www.openstreetmap.org 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*.
- SingAlong 18y agoYeah, 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)
- rchiniquy 18y agoYeah, 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 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 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/ 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 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 http://wiki.openstreetmap.org/wiki/Rana/Modules#route
- SingAlong 18y agoI 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
- rchiniquy 18y agoSure 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).
- gojomo 18y agoThough 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?)
- weaksauce 18y agoI 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....
- gojomo 18y agoAFAICT, they prefer shortest time route, not shortest distance.
- frisco 18y agoI'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/thread/1b5d38969d72dc0c http://groups.google.com/group/Google-Maps-API/browse_thread...