5 ms·

Anyone who's interested in this might want to check out the OSRM project, which uses a much more complex routing algorithm to efficiently find paths through the

Anyone who's interested in this might want to check out the OSRM project, which uses a much more complex routing algorithm to efficiently find paths through the entire OSM graph, instead of just a tiny subset: http://map.project-osrm.org/ http://map.project-osrm.org/ (Also, it's open-source.)

mastazi 10y ago
Are there any instructions? It took me a long while to figure out how to drop pins (the placeholder text says you have to press Enter, but you actually need to use the mouse), and now I have no idea how to display the route.
- danpat 10y ago
  You can type place names into the entry boxes on the front-end - they get converted to lon/lat using a geocoding database. OR you can drop pins on the map.
  - kornish 10y ago
    Is the geocoding database public as well? If so, do you know where it's hosted?
    - maxerickson 10y ago
      It's https://nominatim.openstreetmap.org/ https://nominatim.openstreetmap.org/. There's a use policy: http://wiki.openstreetmap.org/wiki/Nominatim_usage_policy http://wiki.openstreetmap.org/wiki/Nominatim_usage_policy
- alex_minimax 10y ago
  I've got the two markers but no route being displayed, is there a third step (firefox and chrome)?
Doctor_Fegg 10y ago
OSRM is wonderful. I run bike routing for North America and Western Europe using a heavily customised instance of OSRM (based on OSM data, of course): http://cycle.travel/map http://cycle.travel/map
cabalamat 10y ago
Their data is wrong, at least for Edinburgh.
- fermuch 10y ago
  You have the power to help improve it.
danpat 10y ago
I'm one of the OSRM devs. To expand on this comment a bit - OSRM still uses Dijkstra, so if you understand that, you already basically understand what OSRM does. What OSRM does in order to speed things up is optimize the graph structure - we still use Dijkstra, but the search completes in a handful of steps, rather than hundreds of thousands. There are quite a few techniques like this. OSRM implements an approach called Contraction Hierarchies. We scan over the graph, inserting "shortcuts" that skip over nodes. As long as you follow a few basic rules, you can repeatably insert shortcuts all over the graph. This gives you a routing graph that is equivalent, but a Dijkstra search will typically complete in a handful of iterations. We hope one day to implement several other speedup techniques - each has advantages/disadvantages, depending on what you want to do. Contraction Hierarchies lead to very fast queries (~5ms for a cross-the-US route), but the pre-processing time is very long (~6hrs on a beefy machine for the OSM planet). Any updates to the graph require complete re-processing (new/removed roads, adjusted road speeds, etc). Other techniques compromise search performance for a bit more flexibility - faster update times, query customization (i.e. "avoid highways"). It's a really fascinating corner of CS theory to work in, I really enjoy it :-) This paper: https://arxiv.org/pdf/1504.05140.pdf https://arxiv.org/pdf/1504.05140.pdf "Route Planning in Transportation Networks" gives an excellent overview of current search speedup techniques. It's a bit hefty, but if you're interested in knowing what's the state of the art, this is a good place to start.
- amelius 10y ago
  > but the pre-processing time is very long Could you elaborate on why the preprocessing time is long? I didn't study contraction hierarchies, but to me it seems that computing shortcuts in a planar graph is the perfect fit for a divide-and-conquer approach.
  - lorenzhs 10y ago
    You want the shortcuts to be long, so you can't just recursively divide the graph. The Wikipedia article does a fairly good job of explaining CH: https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies

mastazi 10y ago

Are there any instructions? It took me a long while to figure out how to drop pins (the placeholder text says you have to press Enter, but you actually need to use the mouse), and now I have no idea how to display the route.

danpat 10y ago
You can type place names into the entry boxes on the front-end - they get converted to lon/lat using a geocoding database. OR you can drop pins on the map.
- kornish 10y ago
  Is the geocoding database public as well? If so, do you know where it's hosted?
  - maxerickson 10y ago
    It's https://nominatim.openstreetmap.org/ https://nominatim.openstreetmap.org/. There's a use policy: http://wiki.openstreetmap.org/wiki/Nominatim_usage_policy http://wiki.openstreetmap.org/wiki/Nominatim_usage_policy
alex_minimax 10y ago
I've got the two markers but no route being displayed, is there a third step (firefox and chrome)?

Doctor_Fegg 10y ago

OSRM is wonderful. I run bike routing for North America and Western Europe using a heavily customised instance of OSRM (based on OSM data, of course): http://cycle.travel/map http://cycle.travel/map

cabalamat 10y ago

Their data is wrong, at least for Edinburgh.

fermuch 10y ago
You have the power to help improve it.

danpat 10y ago

I'm one of the OSRM devs. To expand on this comment a bit - OSRM still uses Dijkstra, so if you understand that, you already basically understand what OSRM does. What OSRM does in order to speed things up is optimize the graph structure - we still use Dijkstra, but the search completes in a handful of steps, rather than hundreds of thousands. There are quite a few techniques like this. OSRM implements an approach called Contraction Hierarchies. We scan over the graph, inserting "shortcuts" that skip over nodes. As long as you follow a few basic rules, you can repeatably insert shortcuts all over the graph. This gives you a routing graph that is equivalent, but a Dijkstra search will typically complete in a handful of iterations. We hope one day to implement several other speedup techniques - each has advantages/disadvantages, depending on what you want to do. Contraction Hierarchies lead to very fast queries (~5ms for a cross-the-US route), but the pre-processing time is very long (~6hrs on a beefy machine for the OSM planet). Any updates to the graph require complete re-processing (new/removed roads, adjusted road speeds, etc). Other techniques compromise search performance for a bit more flexibility - faster update times, query customization (i.e. "avoid highways"). It's a really fascinating corner of CS theory to work in, I really enjoy it :-) This paper: https://arxiv.org/pdf/1504.05140.pdf https://arxiv.org/pdf/1504.05140.pdf "Route Planning in Transportation Networks" gives an excellent overview of current search speedup techniques. It's a bit hefty, but if you're interested in knowing what's the state of the art, this is a good place to start.

amelius 10y ago
> but the pre-processing time is very long Could you elaborate on why the preprocessing time is long? I didn't study contraction hierarchies, but to me it seems that computing shortcuts in a planar graph is the perfect fit for a divide-and-conquer approach.
- lorenzhs 10y ago
  You want the shortcuts to be long, so you can't just recursively divide the graph. The Wikipedia article does a fairly good job of explaining CH: https://en.wikipedia.org/wiki/Contraction_hierarchies https://en.wikipedia.org/wiki/Contraction_hierarchies