6 ms·

I worked on this problem for a private company. We ended up doing quite a bit to accomplish this: hired a team to edit OSM data, and wrote our own router. What

I worked on this problem for a private company. We ended up doing quite a bit to accomplish this: hired a team to edit OSM data, and wrote our own router. What we learned is that OSM data can be quite terrible at times in minute ways that made it look decent but made routing nearly impossible. I believe this effort is still ongoing and in at least the areas where that company has clients the OSM data is now much more pristine. I sort of wish the router got open sourced, but then again it was not great for long distance routing since we were doing mostly local stuff. For example, routing across the US would have taken pretty close to exponential time. Interestingly, we could not make Google Maps, or any other maps work for this besides OSM for two reasons: the data wasn't good enough and the roads were not uniquely and stably identified in the routes these API's produced. Lastly, I will say that the biggest challenge to using OSM at scale, aside from varying quality of data was lack of good servers and documentation. Some of their secondary services run on one-off slowish hardware with pretty strict rate limits. We would run our own, except the documentation (and the packaging) for OSM software was leaving something to be desired. That is to say if you want to help OSM, there are plenty of ways to do so.

Doctor_Fegg 12y ago
"What we learned is that OSM data can be quite terrible at times in minute ways that made it look decent but made routing nearly impossible." This is exactly why we've exposed routing on the front page of osm.org. I run my own site with OSM-based routing, http://cycle.travel/map http://cycle.travel/map . When I first got the routing engine up and running, I literally spent the next fortnight fixing routing bugs in OSM - "I'd go that way, why doesn't the router agree?". By putting routing front-and-centre, we're hoping that our dedicated contributors - and OSM contributors are nothing if not dedicated! - will do exactly that: they'll find an error and fix it. In the UK and Germany this'll just be little slip-ups, turn restrictions and so on, but in the US there are whole counties that need serious fixup. That's why I submitted the pull request for this[1] and why I'm delighted it's now live. OSM is already a great display map; by making routing more visible, we can make it a great routable map too. [1] https://github.com/openstreetmap/openstreetmap-website/pull/716 https://github.com/openstreetmap/openstreetmap-website/pull/...
- grizzles 12y ago
  It says it uses a 3rd party service. Can you clarify why OSM isn't dogfooding it's own router? Though I'm a huge fan of OSM that sounds like a bit of a let down.
  - dima55 12y ago
    Because there is no "own router".
  - maxerickson 12y ago
    OSM is primarily a data project. There isn't currently any notion of providing centralized end user services. The various services on openstreetmap.org don't have terribly strict usage policies, but they all pretty much ask heavy users to set up their own instance (or use other resources; for example, Mapquest has quite generous free usage, and there are lots of paid OSM tile hosters). If you click the stack on the right tool bar, you get a layers menu, where 4 of the styles are rendered and served by other projects. So the routing is similar to that, showcasing how the data can be used.
    - nroets 12y ago
      Yes, it's great that it's possible to use OSM for many different purposes. However, all these compromises on the front page are too complicated for end users and scare them off. End users expect services that seamlessly work together. If centralization is needed to achieve that, then yes, OSMF needs centralization.
      - ZeroGravitas 12y ago
        The front page isn't intended for end users in the sense of "people looking for a map or directions", it's mainly focused on people who intend to map. People find it hard to get out of the "Google Maps" mindset, just as everyone approached Linux as a "Cheap Windows" when in reality it can be so much more. OSM's strategy (and data) aren't perfect, but they're growing the pie rather than fighting for a larger slice and doing pretty well with it. Just like using Linux has become a no-brainer for all sorts of projects from smartphones to supercomputer clusters to educational toys OSM is well on it's way to being the default peer-produced commons for geographical data. Whether that usage happens on one site or a million different commercial, government, non-profit and amateur sites isn't important.
mtmail 12y ago
"Some of their secondary services run on one-off slowish hardware with pretty strict rate limits." Well everything has a cost and while OSM wants to make their website useful for mappers you shouldn't rely on data API to build a business. For example for the geocoding service there are quite a few abusers who'd run (or try) 1 million requests per day. The hardware is actually quite fast and expensive. (I'm biased. We're running a geocoding SaaS based on open data http://geocoder.opencagedata.com/ http://geocoder.opencagedata.com/)
- IgorPartola 12y ago
  Right. Which is why we wrote our own storage and API and the router on top of it.
RyJones 12y ago
the very simple algorithm we used for Streets & Trips to start was "get to an interstate on both ends, then route the middle bit" with a bias towards staying on larger roads longer. as it turns out you don't get optimal results but you do get pretty good results with very little computation.
- teraflop 12y ago
  The algorithm behind OSRM is actually fairly new, and quite clever. By generating some expensive lookup tables up front, it's possible to do exact shortest-path route finding on huge near-planar graphs (like, say, all the roads in the USA) in a matter of milliseconds, or even microseconds. It's a great example of how theoretical CS research can have a huge impact on practical applications. http://en.wikipedia.org/wiki/Contraction_hierarchies http://en.wikipedia.org/wiki/Contraction_hierarchies http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf http://algo2.iti.kit.edu/documents/routeplanning/geisberger_... (PDF)
  - frik 12y ago
    Can you point to the actual code?
    - dbaupp 12y ago
      Looks like it might be https://github.com/Project-OSRM/osrm-backend/tree/master/contractor https://github.com/Project-OSRM/osrm-backend/tree/master/con... , but I don't know for sure.
  - karussell 12y ago
    It is not a lookup table - think more of some additional shortcuts you introduce for a certain mode. This way you get lots of speed but loose flexibility. In GraphHopper you can enable and disable it, the code is here https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java https://github.com/graphhopper/graphhopper/blob/master/core/...
  - 12y ago
frik 12y ago
OSM needs open source layers and open source routing code. The related mailing lists are rarely used as no one contribute back and only want to run a closed layer or routing service. The OSM project needs the opposite, to dogfood it. Otherwise the data won't be tuned to work better with certain layers and routing.
- karussell 12y ago
  Two engines of the three included on osm.org are open source or what do you mean??
- rmc 12y ago
  Here is the source code for 2 of the routing engines that are used: https://github.com/Project-OSRM https://github.com/Project-OSRM https://github.com/graphhopper https://github.com/graphhopper
lucb1e 12y ago
> OSM data can be quite terrible at times in minute ways that made it look decent but made routing nearly impossible Please do elaborate! I often spend a lot of time just figuring out what the best practices are to map. I'd like to make the map data perfect for all uses but I don't know what kind of tags are needed when I'm mapping.
- nicky0 12y ago
  One example I often run into is where dissimilar ways meet. For example a footpath that crosses a road. The path and the road should share a node. If not, then it will look fine on the rendered map but it won't be routable. (Of course, if the path is bridged over the road with no access between them then they shouldn't share a node.)
  - Doctor_Fegg 12y ago
    Good example. Another common example is one-way streets. If you have several sections of a street with conflicting one-way markings like this: ----> . <---- . ----> then the street becomes unroutable (assuming no intersections at the .s). I found this was a fairly common issue on the entry/exit flares at roundabouts.
- ZeroGravitas 12y ago
  There's various automated tools to do this: http://wiki.openstreetmap.org/wiki/Quality_assurance#Error_detection_tools http://wiki.openstreetmap.org/wiki/Quality_assurance#Error_d...
ZeroGravitas 12y ago
It's worth noting that the OSM community has been aware of the routing deficiencies for a long time, so this isn't something that an outsider needed to tell them. See for example this 2009 project which ran a router on the data between the 250 largest cities in the US and found (primarily due to the Tiger sourced data) that entire counties could be cut off from neighbours at boundaries. http://wiki.openstreetmap.org/wiki/TIGER_fixup/250_cities http://wiki.openstreetmap.org/wiki/TIGER_fixup/250_cities They just started with the most important connectivity problems and worked their way down. As the data improved more and more corporate users found it close enough for their needs and started contributing the fixes they needed in a positive feedback loop. There's now various commercial organisations either fixing the map directly for their own benefit or providing lists of issues for the community to address through projects like Maproulette (http://maproulette.org/ http://maproulette.org/) which can point you to random (or nearby) issues for you to fix based on various automated checks (e.g. rivers running uphill) or open data like a list of soccer pitches in France.
- teddyh 12y ago
  I tried maproulette.org. It wanted me to “sign in”, but it turned out it wanted me to log in to OSM, so that was fine. But then OSM asked me to verify MapRoulette to “allow reading my user preferences”. Since it wasn’t obvious what constitutes my preferences or not – my OSM account’s e-mail address has the caption “will never be shown publicly” on it, but would MapRoulette be given my e-mail address? I decided not to risk it and closed the tab.
  - Doctor_Fegg 12y ago
    No, it doesn't include your email address.
deleted 12y ago
[deleted]

Doctor_Fegg 12y ago

"What we learned is that OSM data can be quite terrible at times in minute ways that made it look decent but made routing nearly impossible." This is exactly why we've exposed routing on the front page of osm.org. I run my own site with OSM-based routing, http://cycle.travel/map http://cycle.travel/map . When I first got the routing engine up and running, I literally spent the next fortnight fixing routing bugs in OSM - "I'd go that way, why doesn't the router agree?". By putting routing front-and-centre, we're hoping that our dedicated contributors - and OSM contributors are nothing if not dedicated! - will do exactly that: they'll find an error and fix it. In the UK and Germany this'll just be little slip-ups, turn restrictions and so on, but in the US there are whole counties that need serious fixup. That's why I submitted the pull request for this[1] and why I'm delighted it's now live. OSM is already a great display map; by making routing more visible, we can make it a great routable map too. [1] https://github.com/openstreetmap/openstreetmap-website/pull/716 https://github.com/openstreetmap/openstreetmap-website/pull/...

grizzles 12y ago
It says it uses a 3rd party service. Can you clarify why OSM isn't dogfooding it's own router? Though I'm a huge fan of OSM that sounds like a bit of a let down.
- dima55 12y ago
  Because there is no "own router".
- maxerickson 12y ago
  OSM is primarily a data project. There isn't currently any notion of providing centralized end user services. The various services on openstreetmap.org don't have terribly strict usage policies, but they all pretty much ask heavy users to set up their own instance (or use other resources; for example, Mapquest has quite generous free usage, and there are lots of paid OSM tile hosters). If you click the stack on the right tool bar, you get a layers menu, where 4 of the styles are rendered and served by other projects. So the routing is similar to that, showcasing how the data can be used.
  - nroets 12y ago
    Yes, it's great that it's possible to use OSM for many different purposes. However, all these compromises on the front page are too complicated for end users and scare them off. End users expect services that seamlessly work together. If centralization is needed to achieve that, then yes, OSMF needs centralization.
    - ZeroGravitas 12y ago
      The front page isn't intended for end users in the sense of "people looking for a map or directions", it's mainly focused on people who intend to map. People find it hard to get out of the "Google Maps" mindset, just as everyone approached Linux as a "Cheap Windows" when in reality it can be so much more. OSM's strategy (and data) aren't perfect, but they're growing the pie rather than fighting for a larger slice and doing pretty well with it. Just like using Linux has become a no-brainer for all sorts of projects from smartphones to supercomputer clusters to educational toys OSM is well on it's way to being the default peer-produced commons for geographical data. Whether that usage happens on one site or a million different commercial, government, non-profit and amateur sites isn't important.

mtmail 12y ago

"Some of their secondary services run on one-off slowish hardware with pretty strict rate limits." Well everything has a cost and while OSM wants to make their website useful for mappers you shouldn't rely on data API to build a business. For example for the geocoding service there are quite a few abusers who'd run (or try) 1 million requests per day. The hardware is actually quite fast and expensive. (I'm biased. We're running a geocoding SaaS based on open data http://geocoder.opencagedata.com/ http://geocoder.opencagedata.com/)

IgorPartola 12y ago
Right. Which is why we wrote our own storage and API and the router on top of it.

RyJones 12y ago

the very simple algorithm we used for Streets & Trips to start was "get to an interstate on both ends, then route the middle bit" with a bias towards staying on larger roads longer. as it turns out you don't get optimal results but you do get pretty good results with very little computation.

teraflop 12y ago
The algorithm behind OSRM is actually fairly new, and quite clever. By generating some expensive lookup tables up front, it's possible to do exact shortest-path route finding on huge near-planar graphs (like, say, all the roads in the USA) in a matter of milliseconds, or even microseconds. It's a great example of how theoretical CS research can have a huge impact on practical applications. http://en.wikipedia.org/wiki/Contraction_hierarchies http://en.wikipedia.org/wiki/Contraction_hierarchies http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf http://algo2.iti.kit.edu/documents/routeplanning/geisberger_... (PDF)
- frik 12y ago
  Can you point to the actual code?
  - dbaupp 12y ago
    Looks like it might be https://github.com/Project-OSRM/osrm-backend/tree/master/contractor https://github.com/Project-OSRM/osrm-backend/tree/master/con... , but I don't know for sure.
- karussell 12y ago
  It is not a lookup table - think more of some additional shortcuts you introduce for a certain mode. This way you get lots of speed but loose flexibility. In GraphHopper you can enable and disable it, the code is here https://github.com/graphhopper/graphhopper/blob/master/core/src/main/java/com/graphhopper/routing/ch/PrepareContractionHierarchies.java https://github.com/graphhopper/graphhopper/blob/master/core/...
- 12y ago

frik 12y ago

OSM needs open source layers and open source routing code. The related mailing lists are rarely used as no one contribute back and only want to run a closed layer or routing service. The OSM project needs the opposite, to dogfood it. Otherwise the data won't be tuned to work better with certain layers and routing.

karussell 12y ago
Two engines of the three included on osm.org are open source or what do you mean??
rmc 12y ago
Here is the source code for 2 of the routing engines that are used: https://github.com/Project-OSRM https://github.com/Project-OSRM https://github.com/graphhopper https://github.com/graphhopper

lucb1e 12y ago

> OSM data can be quite terrible at times in minute ways that made it look decent but made routing nearly impossible Please do elaborate! I often spend a lot of time just figuring out what the best practices are to map. I'd like to make the map data perfect for all uses but I don't know what kind of tags are needed when I'm mapping.

nicky0 12y ago
One example I often run into is where dissimilar ways meet. For example a footpath that crosses a road. The path and the road should share a node. If not, then it will look fine on the rendered map but it won't be routable. (Of course, if the path is bridged over the road with no access between them then they shouldn't share a node.)
- Doctor_Fegg 12y ago
  Good example. Another common example is one-way streets. If you have several sections of a street with conflicting one-way markings like this: ----> . <---- . ----> then the street becomes unroutable (assuming no intersections at the .s). I found this was a fairly common issue on the entry/exit flares at roundabouts.
ZeroGravitas 12y ago
There's various automated tools to do this: http://wiki.openstreetmap.org/wiki/Quality_assurance#Error_detection_tools http://wiki.openstreetmap.org/wiki/Quality_assurance#Error_d...

ZeroGravitas 12y ago

It's worth noting that the OSM community has been aware of the routing deficiencies for a long time, so this isn't something that an outsider needed to tell them. See for example this 2009 project which ran a router on the data between the 250 largest cities in the US and found (primarily due to the Tiger sourced data) that entire counties could be cut off from neighbours at boundaries. http://wiki.openstreetmap.org/wiki/TIGER_fixup/250_cities http://wiki.openstreetmap.org/wiki/TIGER_fixup/250_cities They just started with the most important connectivity problems and worked their way down. As the data improved more and more corporate users found it close enough for their needs and started contributing the fixes they needed in a positive feedback loop. There's now various commercial organisations either fixing the map directly for their own benefit or providing lists of issues for the community to address through projects like Maproulette (http://maproulette.org/ http://maproulette.org/) which can point you to random (or nearby) issues for you to fix based on various automated checks (e.g. rivers running uphill) or open data like a list of soccer pitches in France.

teddyh 12y ago
I tried maproulette.org. It wanted me to “sign in”, but it turned out it wanted me to log in to OSM, so that was fine. But then OSM asked me to verify MapRoulette to “allow reading my user preferences”. Since it wasn’t obvious what constitutes my preferences or not – my OSM account’s e-mail address has the caption “will never be shown publicly” on it, but would MapRoulette be given my e-mail address? I decided not to risk it and closed the tab.
- Doctor_Fegg 12y ago
  No, it doesn't include your email address.

deleted 12y ago

[deleted]