Routing

From OpenStreetMap Wiki
Jump to: navigation, search
Available languages — Routing
Deutsch English italiano русский 한국어 日本語
Skobbler Navigation (online turn-by-turn navigation app for iOS).

Routing (in some countries called navigation) services help people get from one place to another. OpenStreetMap data includes information for routing by many modes including car, foot, bicycle and horse. There are many offline, embedded and web-based routing services using OpenStreetMap data.

For developers this page provides advice on software available for creating new routing applications/deployments and details key OpenStreetMap data that can be used to create better routing engines. A number of mailing lists are also available.

End users: Routing software

See also: List of OSM based Services#Routing

Mappers: Improving the map data

For routing software to work well, the underlying map data must be of good quality. Essentially this means that ways that should be connected are in fact connected, one-way roads are tagged, turn restrictions are mapped, and so on. You should be familiar with the Map Features used, in particular see OSM tags for routing to understand the tags specific to routing.

Fixing bugs with MapDust

Showing how to determine connected and unconnected nodes in Potlatch

Many of the bugs on MapDust have been added directly from within iOS or Android navigation apps. This makes it a good place to look for improvements to the map data. Some bugs are specifically about one-way roads or turn restrictions, and are marked as such.

Look out for many "poor routing" or "other" bugs in a small area as this may indicate that thre is a missing connection between ways. In Potlatch when you select a way you will see all the nodes highlighted. If a node is big and square then it is connected to another way. To improve the quality of OSM data you can use also the reports generated by WayCheck.

Note: Try unchecking the "Hide bugs with default text" on mapdust as many users do not change the default text whilst using the navigation app.

Speed data

In order to better calculate the fastest route, please consider helping by adding speed data using the maxspeed=* tag. This is especially important where the speed limit differs from the assumed maximum permitted speed for the road type per country and vehicle-type.

Note: ITO World provide a number of services to help identify missing speed limits.

Often maxspeed is meaningless - see #Average speed.

Checking your fix

After you have fixed an error on the map you will need to wait until the revised version of the map propagates into the routing engine you are using. This delay will depend for each engine on:

  • how often it get updates from the database
  • how long it needs to update its internal database.

In the case of OSRM used on the map front page it usually gets updates twice a day and then spends 10-12 hours processing the updates. This gives a total delay of anything from 10 to 24 hours from your fix being saved to the map, to working in OSRM.

Developers

Desktop and server software

Java

  • The Traveling salesman routing-application contains the osmNavigation -library for doing all the basics except a user-interface. All important parts can be exchanged via plugins.
  • OpenTripPlanner site is a multi-modal trip planner supporting OSM data. OTP Deployer makes it easy to deploy your own routing instance.
  • GraphHopper is a Java routing engine for (road) networks. Fast and memory efficient (for Android, iOS, desktop and server).
  • BRouter focuses on bike routing and features elevation awareness, alternatives, fully configurable routing profiles and offline routing initially written for Android, but has now also a web api
  • Atlas is a Java map and navigation application using offline vector maps.

C/C++

C#

Scala

Ruby

  • Mormon ruby version of pyroutelib

Python

Mobile device software

C/Java

  • OsmAnd OSM Map, POI and Routing (car/bike/foot, online&offline) for Android
  • ZANavi Android
  • Navit Linux, Windows and portable devices
  • GraphHopper Android and iOS. Routing engine library.
  • BRouter focuses on bike routing and features elevation awareness, alternatives, fully configurable routing profiles and offline routing for Android
  • OpenTripPlanner_(Android) is an Android app for multi-modal trip planning using any OpenTripPlanner server
  • Cruiser is an Android map and navigation application using offline vector maps.

Libraries/development tools

Libraries focused on OSM Routing can be found at Develop/Frameworks. Here some general libs:

  • DGLib Directed Graph Library used by Grass's vector network tools (shortest path, traveling salesman, isodistances, Steiner trees; also Addons)
  • Graphserver is a webservice providing shortest-path itineraries on TIGER/line road maps, and public transport data in the General Transit Feed Specification format
  • pgRouting - PostGIS-based routing engine. Special tool osm2pgrouting for importing OSM data to internal graph structure. Works directly on top of SQL database tables.
  • Libosmscout offers simple, high-level interfaces to offline rendering and routing functionalities based on OpenStreetMap data
  • Spatialite Spatialite has its own routing engine VirtualNetwork and a spatialite_osm_net tool for building a routable network directly from OSM data. Routing can use either Dijkstra or A* algorithm.
  • GraphHopper routing engine with Java API.
  • ffwdme.js is a JavaScript toolkit that aims to bring interactive GPS driving directions to the mobile browser.
  • Valhalla is a free, open-source routing service that lets you integrate routing and navigation into a web or mobile application.

Protocols:

Routing considerations

Highway-type

The order of values for the highway-tag ordered by assumed speed is:

  1. motorway
  2. motorway_link
  3. trunk
  4. trunk_link
  5. primary
  6. primary_link
  7. secondary
  8. secondary_link
  9. tertiary
  10. tertiary_link
  11. unclassified
  12. residential
  13. living_street / service
  14. track

This is highly country specific and rather useless without country specific values. For example in Germany primary roads allow 100km/h both legally and as a realistic speed while minor motorway_link(s) are built to allow a recommended speed of 60 km/h, only major motorway_links allow a realistic speed of 80 or 100. For more information see OSM_tags_for_routing/Maxspeed#Additional_information_for_selected_countries

Lanes

The number of lanes of a highway is directly tagged in OSM and has a major influence on the average speed (fastest route) and fuel-consumption (most efficient route). There is no simple mapping to speed unfortunately, in many cases more lanes only indicate more congestion.

Highway condition

Other factors, in our case more difficult to measure, which determine the average speed are the width of pavement, condition of the network (roadworks, surface type and surface smoothness - especially in ex-USSR), Levels of Service (LOS), minimal radius curve, banked turns, visibility based on curves and gradients, etc.

In OpenStreetMap this model can be interesting for those routes where there are no data on speeds (for example: highway=road).

Inclines

Same as curves, inclines may decrease the speed of traffic. In winter of when lots of hgv is present the hindrance is also on the descending way. While some inclines are explicitly tagged, in some cases utilization of additional informations such as ele=* and height elevation profile from DEM data could prove useful.

Sinuosity

See also turning radius=*

In some studies about the accessibility [1] develop models that assume a certain speed of travel depending on the degree of sinuosity of the track and certain characteristics of this one. By means of the sinuosity index (observed line distance/expected line distance ) for every section it is possible to obtain a speed estimated according to the degree of winding of the road and type of route. This needs to take into account the visibility around corners (determined by vegetation, embankments, cuttings, cliffs,...) and road width. The model is more precise if the excessively large arcs are avoided provided that a long curve can be equal to many small curves along a way, giving similar values of sinuosity for both routes. Some countries use these values to divide sections of roads and put speed limits (but this is not usual).

On the other hand, geographical approaches like that of the space syntax presuppose that, in urban environments, pedestrians and drivers are influenced at the moment of choosing theirs paths for the visibility of the route. In this respect a pedestrian who moves, for example, from the point A to the point B will select principally wide and rectilinear streets, squares or avenues with a wide visual field, avoiding crossed by winding and narrow streets, even when the latter route is somewhat shorter.

Crossings, junctions and lane changes

Certain cost should be assumed for:

  • crossing higher-class roads
  • changing to and from lower-class roads
  • u-turns
  • lane changes

Average speed

OpenStreetMap data will need average/realistic speed values for routing.

  • maxspeed:practical=* is a rejected but nevertheless used proposal to tag estimated average speed values (with the possibility to specify day/night/rush hour values) in areas where official speed limits are largely meaningless and road/track type information insufficient to derive meaningful travel speed estimates.
  • Global Statistical Speed Matrix is a proposed concept (no current signs of life?) to extract speed information from NMEA/GPX tracks and store them efficiently in a database to make collected data useful for routing purposes.

List of other tags giving routing hints

Bicycle

- see also hiking

Hiking

Routing obstacles and other conditions requiring special consideration

See also wheelchair routing.

Entrance(s)

Finding the entrance can make a huge difference..

Mailing lists

The following mailing lists are relevant to routing

  • osm-routing 'Discussion about Routing with vector Data. Especially concerning OSM Data'
  • osm-accessibility For all kinds of disabilities this concerns the proposal and use of tags that are of special interest for disabled persons. Special maps shall be created with this data.

See also