Tag: Routing

The State of the Map. United States. Street Network. 2013

Last year we wrote a journal paper in which we analyzed the OpenStreetMap (OSM) dataset of the United States which was published on May 28th, 2013 in the Transactions in GIS Journal. You can download a free pre-print version here. This paper has been published just on time to add to the discussion at the upcoming State of the Map United States conference which will take place in San Francisco and includes some presentations about data imports to OSM. Unfortunately, Dennis and I cannot attend the conference this year, so we decided to write a blog post with some additional and up-to-date numbers.

OSM Routing View Worldwide 2011-11

Really great news for all our non-European OpenStreetMap.org Mappers: Since last month, the OSM Routing View is available for the whole world. You can read more in Frederik’s blog post. Yesterday he sent me the latest results of the view and I did some analysis with it. To all new readers: you can find more information about the OSM Inspector (OSMI) here. The Routing View within the OSMI “shows problems in the data, related to routing and navigation” (direct link).

However, here are the new *worldwide* stats for November 2011: we have a total of about 1,3 Mio errors. We can divide them into the following groups:

  • Unconnected 1 meter: 248000
  • Unconnected 2 meter: 62000
  • Unconnected 5 meter: 170000
  • Duplicate (number of duplicate segments): 833000

The following diagram shows the amount of errors per continent:

Comparison of (OSM) routing-engines – Reloaded

Maybe some of you remember that I conducted a comparison analysis between three OpenStreetMap (OSM) routing engine APIs (CloudMade, MapQuest Open and OSRM) and G**gle Maps API last week. You can find the results in my blog post here. As I mentioned in the article, I wanted to try to do a second analysis with more routing engines.

Thus, I added Bing Maps and two OSM engines (YourNavigation/YOURS and Routino/Roadeeno) to the comparison. All services have a continental coverage with the exception of OSRM. The following table shows an overview of (1) the request-response time of the service, (2) the calculated distance for the test-route and (3) the file size of the service response:

As you can see in the following diagram does the OSM routing engine (OSRM) give the fastest results. A little bit strange is that the Routino/Roadeeno service returns no valid route responses for requests which are longer than 600 km.

A comparison of several routing-engines – Which one is the fastest?

In the past blog post I wrote about the newest changes and encoding techniques that have been implemented in the Open Source Routing Project (OSRM). So I think it is time do a little comparison analysis about the request/response time of several routing APIs. The main question I wanted to answer was: “Is an OpenStreetMap direction service faster than G**gle?” I tested the following direction APIs for cars (fastest): MapQuest, CloudMade, G**gle and finally OSRM. For the analyses I wrote a small Java tool, which measured the time to get a result of a routing-service. I did all tests at home with a “regular” 12kbit/s internet connection. I tested several distance levels and the results can be seen in the following table. It shows the average times of five requests for each route with a delay of 3 seconds between each request/response. Overall I did this analysis three times.

Fast routes of OSRM just got faster…

One of the many bottle necks of today’s web services are network latency and bandwidth. While I was working on a research paper, I recognized that G**gle encodes some information when you calculate a route on G**gle Maps. This process reduces, besides the gzip compression, the response from the server. This means that this is a speed improvement for the server client communication besides the zoom-level-generalization. You can read more about the “Encoded Polyline Algorithm Format” and how it works here.

We integrated this nice feature into the code of the Open Source Routing Machine (OSRM) project. The following table shows a few results for some sample routes comparing the old and the new file sizes (@ zoomlevel 18):

Web-GUI for OS Routing Machine

During my Easter holidays I created a web-fronted for Dennis Luxen’s Open Source Routing Machine (OSRM Project). The OSRM project (http://project-osrm.org/) is in my opinion probably the fastest Open Source software which is using data from the OpenStreetMap project. “In contrast to most routing servers OSRM does not use an A* variant to compute shortest path, but Contraction Hierarchies.” You can read a little bit more about Contraction Hierarchies in Wikipedia.

The website that I created contains in its first version an address-search (geocoding) and of course routeplanning. For the geocoding I integrated the Nominatim search from OpenStreetMap. You can find a How-To on the MapQuest-site. Unfortunately the OSRM routing service covers only most parts of Europe for now. The current version of my web-fronted can be found here: http://map.project-osrm.org

Routing View Europe 2011-05

First of all, sorry that I did not create a new stat regarding the Routing View past month. To all the new readers: Usually I create an analysis about the Routing View of the OpenStreetMap Inspector for each month for Europe. You can find more information about the OSM Inspector (OSMI) here. The Routing View within the OSMI “shows problems in the data related to routing and navigation”. You can read more about it here … A direkt link to the OSMI Routing View is here!

However, here are the new stats for May, 2011: we have a total of about 124000 “Unconnected Roads” and about 108000 “Duplicate Ways” (number of duplicate segments). Overall this means that we have about 17000 *new* „Unconnected Roads” errors and only ca. 1300 “Duplicate Ways” have been fixed in Europe. For the past three months we have an increment of about 2850000 new OSM way segments for routing. (May 7th: 34500000, February 20th: 31700000, January 20th: 30600000)

Updated Error Summary for Europe

This month I tried something new. But first we will start with the usual monthly stats of the OSM Inspector Routing for Europe, this time for the middle of February 2011. Overall the following amount of errors appears for “Europe”: Unconnected Roads: ca. 107000 and Duplicate Ways (number of duplicate segments): ca. 109000 (in the OSM Wiki you can find more information about the error-types). This means that altogether there are 2600 unconnected streets and 16900 duplicate way segment errors have been fixed. In total we have an increment of 1111000 new OSM way segments for routing during the past 4 weeks in Europe (01/20/2011: 30600000, 02/20/2011: 31710000).

The following image shows the amount of errors divided by country for today’s Europe OpenStreetMap dataset:

In the past month several other countries were able to reduce the amount of errors, such as in: France (-1600), Italy (-1600), Poland (-1900), Sweden (-2300) and United Kingdom (-8000!!!). So congratulation to the UK, this is your month :)

Routing View EU 2011-01

Overall the following amount of errors appears for “Europe” at the middle of January 2011:

  • Unconnected Roads: ca. 109600
  • Duplicate Ways (number of duplicate segments): ca. 125900
  • (read more about the error-types here)

This means that altogether there are 3000 unconnected streets and 13400 duplicate way segment errors have been fixed (last month we had 112600 unconnected roads and 139000 duplicate ways errors). In total we have an increment of 1139000 (+3.8%) new OSM way segments for routing during the past 4 weeks in Europe!

  • 12/23/2010: 29400000
  • 01/20/2011: 30600000

The following image shows the amount of errors divided by country for today’s Europe OpenStreetMap dataset:

Routing View EU 2010-12

Short update with new statistics for the “Routing View EU“. Overall the following amount of errors appears for “Europe” at the middle of December 2010:

  • Unconnected Roads: ca. 112600
  • Duplicate Ways (number of duplicate segments): ca. 139000
  • read more about the error-types here

This means that altogether there are 5100 new unconnected streets and 20000 duplicate way segment errors have been fixed (last month we had 107500 unconnected roads and 160000 duplicate way errors). In total we have an increment of 1300000 (+4.6%) new OSM way segments for routing in the past 5 weeks in “Europe” (this is nearly twice the number in comparison to one month ago)!

The following image shows the amount of errors divided by country for today’s Europe dataset: