Routing on OpenStreetMap.org | Hacker News Reader

Routing on OpenStreetMap.org

blog.openstreetmap.org

319 pointsmaxerickson85 comments

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.

"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 . 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/...

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.

Because there is no "own router".

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.

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.

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.

I was trying to describe things as they are, not take a side.

The interest generated by this change demonstrates your point well enough, OSRM has been available at http://map.project-osrm.org/ with worldwide coverage for quite a while, and the other projects are also up for quite a while.

I even see a bunch of OSM enthusiasts who were apparently oblivious to the availability of the routing services (saying 'wow, it works good' sort of indicates they haven't seen it work before).

The routers are written by small teams that don't talk to each other. On the OSM routing mailing list, there was very little / no meaningful discussion in the last 2 or 3 years.

For one, it's anything but easy to write a fast and correct routing engine that produces good results. OSRM was (mainly) written by Dennis Luxen who literally has a PhD in route planning.

Secondly, if these projects already exist and are easy to integrate, I fail to see why it should be problematic for OSM to use them. OSRM is completely open source, anyone can spin up their own instance if they wanted to, so someone else can host it if the current server goes down. Open source routing engines like OSRM exist so that OSM doesn't need to roll their own. I'm having a hard time wrapping my head around how you construe this to be a bad thing.

OSM is much more decentralised than that. There isn't really a central OSM body that controls everything. 2 of the 3 routing engines used are written by members of the OSM community, are open source, and are designed to work with OSM data. Should we count them as "3rd party" or not? They aren't hosted on the main OSM servers, instead hosted on the servers of the respective projects.

OSM suffers because everyone creates his own (closed source) layer service and his own (closed source) routing service.

Instead the community should be on the OSM site and contribute to open layers hosted on the official page and open routing code so that the OSM map data can be tuned for it. But apparently it goes in the opposite direction :(

What you see on cycle.travel _is_ an open source router. They run https://github.com/Project-OSRM/osrm-backend Actually, I don't really see where you get that impression from. Very few commercial providers use their own routing stack. It is almost always OSRM or pgRouting if you want something that scales for world-wide routing.

I didn't know about cycle.travel until I read OSM's announcement this morning. The site is great even if a little slow. I planned a 110 km route mostly on unpaved roads and it did well. I run into a couple of glitches but I don't know if they happened because of the routing algorithm or the data. Is there a way to report them beside taking a screenshot?

Glad it went well! There's no automated "report a problem with this" but I'm always happy to take a look - either via the site forum or email, whichever's easiest.

I posted to the forum right now, same nick as here.

"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/)

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

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.

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://algo2.iti.kit.edu/documents/routeplanning/geisberger_... (PDF)

Can you point to the actual code?

Looks like it might be https://github.com/Project-OSRM/osrm-backend/tree/master/con... , but I don't know for sure.

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/...

If you are interested in further details on algorithms for route planning, check out http://i11www.iti.uni-karlsruhe.de/teaching/sommer2014/route... for a whole lecture on them (slides are in English). Each chapter also contains a list of relevant publications.

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.

Two engines of the three included on osm.org are open source or what do you mean??

Here is the source code for 2 of the routing engines that are used:

https://github.com/Project-OSRM https://github.com/graphhopper

> 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.

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.)

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.

There's various automated tools to do this:

http://wiki.openstreetmap.org/wiki/Quality_assurance#Error_d...

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

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/) 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.

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.

No, it doesn't include your email address.

Slightly off topic, but is there a way to make the OSM website use high-dpi images on devices like iPads? The map tiles look blocky when viewed on mobile safari. What's annoying is that when you zoom out, the tiles are shrunk and 'become high-res' but then the website loads lower-res tiles to draw over the top!

No; at present the osm.org tiles aren't generated at a retina scale.

This is most likely to be fixed in the medium term by moving to vector rendering via WebGL et al.

This OSM service supports retina: https://geodienste.lyrk.de/

Looks like this thing has quite a ways to go before it's ready for primetime, but this fills in the last gap I needed filled in order to switch fully over to OSM as my day-to-day map site/software/data/etc. Pretty spiffy; just needs some kinks worked out with the underlying data (I think) ;)

OpenStreetMap genuinely amazes me. I know their data is still a bit inconsistent, but in some areas they vastly exceed other online maps, but they are lacking in other areas.

It looks as though OSM is making great inroads as far as routing and addresses go, and so the next big thing will be getting the iD editor working well on mobile devices.

Great to see public rights of way being included in the walking directions.

At the moment there is a mixed content bug in the place lookup, so it doesn't work over https. I guess it will be fixed in short order though.

There's also not much fuzziness in the search. For example, "Tolado Ohio" will not be found.

Yeah, but without autocompletion this is hard IMO. You might want to try photon for that: http://photon.komoot.de/ and with routing see here: https://graphhopper.com/maps/ or https://www.komoot.de/plan

I noticed this too. But my main problem with the search is that it attempts to complete the address when your focus leaves the input.

Yeah for me it's trying to make calls to http://www.openstreetmap.org/http://nominatim.openstreetmap....

It kind of demonstrates how far behind they are with things like navigation, search etc. It's a shame because the actual mapping data behind OSM is absolutely fantastic.

We working to fix this right now ;-) (OSM sysadmin here)

Fixed thanks to TomH: http://git.openstreetmap.org/rails.git/commitdiff/2b7529a3f1...

> It kind of demonstrates how far behind they are with things like navigation, search etc

To quote from the link "Well, the first thing to note is that the philosophy of OpenStreetMap is not to offer a one-stop-shop on our main website, but to create truly open data to empower others to do great things with it."

The search has always been... odd, though.

Good thing OSM doesn't lock you out of the data at any level, so if you (or your company) want to write a better geocoder, do it. OSM is no walled garden.

We currently run two graphhopper routing servers in production for our bike route mapping website. They work fantastic and are fast even without the contraction hierarchies tricks used to speedup routing at the expense of flexibility. We occasionally get user reports of odd routing anomolies due to the underlying data, but they are actually not much more frequent than reports about google maps. I also evaluated osrm but the graphhopper folk run a great open source project. Felt much more comfortable throwing in with them than anyone else. Happy to share any details if anyone has questions, email in my profile.

First impression was pretty bad. Tried to get a route from my place to my parent's house a couple cities south, and it took a lot of fiddling with the string to get it to understand where I live. Didn't have any trouble finding my parent's home, but once I got both in the instructions it gave were pretty poor: http://a.pomf.se/msawni.png

I really want OSM to be good for this sort of thing, so I'll probably end up poking around and fixing the errors that led to this mess.

We'd love for you to get involved and help improve the map :)

Essentially this is a GIGO issue. If you ask for a route between any two places in the UK, or Germany, or France, or any other country with a strong OSM community, OSM will do fine - in fact, by bike or on foot, you'll get a better route than Google would give you.

We don't have as strong a community in the US. In SF, NYC etc. the data's pretty good. In rural Nevada it... isn't. It's still raw untouched TIGER (US census data) in most places.

So: hell yes, poke around and fix it. We would love OSM to be as good in the US as it is in Europe. And if anything isn't clear, pop in here or on IRC and ask. We're a friendly community.

I've found it to be pretty hit-and-miss. For example, it doesn't know where my house is, either, but it knows where my old apartment is (in the same town), and where the houses of several relatives are in other cities.

It's probably issues with OSM's data rather than the routing mechanism itself, however, so yeah, it should be possible to poke at it a bit and fix things up (as I likely will do, being no stranger to OSM editing myself).

Try inputting your address without any sort of "area" or suburb. I.e. just type in street number + street name + city. I had such a tough time wondering why it wouldn't recognize a certain address, then noticed how it auto-corrected the previous one that worked.

Instead of picking up that the address was in suburb "A", it put it inside "Ward 47 of Tshwane", Tshwane being the city/municipality. Perhaps the data for suburbs is not up to scratch in my particular area.

In all my testing, it was with only the number and street name (i.e. "1234 Somesuch Road") - no city, state, zip, etc. I tried again with "1234 Somesuch Road Somecity" ("Somecity" being the city) for my own town, but that didn't seem to work, either.

I used to work on the router used in VZ Navigator and related products (I wrote the part that used real-time traffic data to route around slowdowns, plus several other bits). After leaving, I started writing my own router on top of OSM data (fall 2008). The difference in quality of Navteq and other vendor data vs. OSM was substantial, and I abandoned the project simply because shit data is impossible to optimize for. It looked great on a map, but disconnected road segments, incorrect road categorization, incorrect directions of one-way streets, missing intersections, ... I wasn't at all surprised at Apple falling on its face in 2012 with its OSM-backed maps product - it was a virtual guarantee from my experience.

Likely a missed opportunity for a big exit for me, but life's too short to work against poor-quality crowd-sourced data as a one-man startup in Venice.

Routing belongs on a mobile device. Now all I need is a usable Android app for browsing maps and navigating. OsmAnd seems to be the benchmark, and it's freaking terrible.

I've been tempted to set up Eclipse, and just go in there and gut 90% of the menu options. What would remain would probably be a reasonably usable mapping app.

udig has been around for a while now. http://udig.refractions.net/

I was talking about taking the menu options out of OSMAnd. I mentioned Eclipse because it is necessary for Android development.

Can you elaborate on why you think OsmAnd is terrible?

I think he means end-usability. Feature-wise and once you get used to it, it is VERY amazing :)

IMO, so cluttered and stuffed with... stuff ... that the useful functionality is buried under a baffling pile of UI elements and surprise actions.

It's a classic open source problem: pack in the functionality, but not be entirely sure how best to present it, so provide everything with lots and lots of switches for power users to toggle what they want.

Starting out with less stuff might help; starting out remembering to go to the map would, I suspect, be a great UX experience for a map app.

OsmAnd is great but its target users are OSM contributors and map geeks, not "Joe User looking for a GM alternative".

For your usecase, have a look at mapswithme instead. It's proprietary but very neat. Does only the basics but does them well.

There are plenty of mobile apps using OSM data, some of them high quality and improving regularly. If one app doesn't suit you, look around. Have another look if you last tried many months ago.

Maps.me is a good android OSM app. It has routing now I think.

Seems to only work by street name. If I put in two UK postcodes the results are almost always wrong. This seems to be a problem in normal OSM anyway, if you search for an exact postcode, a list of nearby streets come up and the street you actually want is incorrectly listed. Where should I go to fix this? Seems like it should be a simple enough edit.

The postcode database is not Free (enough).

Re where should I go to fix this:

* https://alpha.openaddressesuk.org/

...which is still only in alpha, so don't expect much. Read their posts about the data sources (https://alpha.openaddressesuk.org/about/docs) to see why this is in such a bad state.

This won't fix the data in OSM; this will contribute to OpenAddresses UK which is a separate (though worthy!) project.

In theory you just need to add the 'addr:postcode' tag to the relevant house or street.

That said, OSM's geocoder has a few issues with postcodes at present: https://trac.openstreetmap.org/ticket/2497 . The second para of lonvia's final comment is the crux - "[postcode updates are] a very expensive operation and so the centroids don't get updated and postcodes go stale with time".

This doesn't appear to be working for me in Chrome. I'm getting a ton of "XMLHttpRequest cannot load" errors related to this in the console:

  No 'Access-Control-Allow-Origin' header is present on the requested resource. Origin 'http://www.openstreetmap.org' is therefore not allowed access.

What server is being used? Is it OSRM?

OSRM is the default, but there are a number of other profiles available (foot, bike and car from Mapquest and foot and bike from GraphHopper).

How very cool.

This is very good, I’ve been wanting this for a long time. But it still has some serious shortcomings:

Car routing only for OSRM. Is this something which will be fixed?

Also egregiously missing is the ability to create a link to a pre-made route.

Linking is all Web 1.0, all you have to do is copy the URL:

http://www.openstreetmap.org/directions?engine=osrm_car&rout...

Oh, nice. Did I miss this, or is this changing of the URL in the address bar a recent addition?

I’m assuming I missed it. Sorry about that.

Does it use pgrouting ?

Nope. The frontend JS is reasonably agnostic and talks to three third-party backends: OSRM, GraphHopper and MapQuest Open. If anyone would like to set up a reliable worldwide instance of pgrouting I'm sure we'd be interested in using it.

No. Nobody serious uses pgrouting.

What makes you say that? Honest question.

Have you read the documentation for pgrouting?

Agreed. I cannot agree more. I similarly build a system using the routing capabilities of pgRouting with OSM. While the outcome has bbe absolutely awesome (managed routing on the entire OSM dataset with pretty fast queries) and was done in quite a short timespan, chugging through the documentation was horrible - especially when I ran into errors.

Do you know of any other alternative routing libraries that can be used with OSM data similar to pgrouting?

There are many OSM routers. http://wiki.openstreetmap.org/wiki/Routing#Developers

Really like what OSM are doing

Reply on news.ycombinator.com