Routing

From OpenStreetMap Wiki
(Redirected from Routing engine)
Jump to navigation Jump to search
Routing - Other languages
Skobbler Navigation (online turn-by-turn navigation app for iOS).

Routing services (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


Name, link Genre Covered region Language Description Free materials Image
A Better Routeplanner Routing, car English A route planner for planning trips and charging with a Electric Vehicle. No
Agilogik GmbH Routing, maps, tile server, geocoding, geo reverse coding Worldwide English, German Worldwide tile server and services for commercial use No
BBBike [1] Routing English, Chinese, Danish, Spanish, French, German, Croatian, Dutch, Polish, Portuguese, Russian Routing focused on bikes (no. of traffic lights, height profile, lit, road surface, …)
?
 Bbbike.org screenshot.png
Bike Citizens [2] Routing English, Spanish, French, German Bike Citizens is a navigation app designed for and by cyclists, offers offline routing, predefined tours and various routing profiles
?
 Finnder screenshot.jpeg
BRouter [3] Routing English, Hungarian BRouter: Let's get serious about bike routing. BRouter offers routing for trekking and cycling with predefined profiles and the ability to modify and upload custom profiles
?
Curvature Routing English Curvature generates a map highlighting the most twisty roads, all across the world. Yes
CycleStreets [4] Routing English Bicycle routing and planning and photo map based on OpenStreetMap data and the OpenCycleMap for the British Isles. API available. Yes CycleStreets screenshot.jpg
FacilMap [5] General, routing, share, social, interaction English Different OSM renderings, search and draggable routes, create custom maps with live collaboration where markers, lines, routes and GPX/KML/GeoJSON/OSM files can be added. Yes
GraphHopper [6] Routing, car, bike, walking, public transport, wheelchair Worldwide multiple languages Fast routing for bikes, pedestrians and cars with worldwide coverage. Using the open source routing engine GraphHopper. Yes Routing graphhoppercom.png
GraphHopper Direction Api Road Routing, car, bike, walking Worldwide multiple languages Fast routing service including a powerful Matrix and Route Optimization API based on the open source routing engine GraphHopper No commercial Routing graphhoppercom.png
KOMOOT Routing Routing, hiking, bike German, English Calculate routes for mountain bikes, touring bikes and hiking taking your fitness level and elevation into account Yes, see GraphHopper Komoot screenshot.png
Kurviger Routing, motorcycle English, French, Greek, Spanish, German Routing and navigation specialised for motorcycles. Kurviger calculates curvy routes that are fun to ride on bike. Curves and slopes are preferred, while cities and highways are avoided. Generate loop trips with one click. Personalise the routing to your own riding style. Yes, see GraphHopper Kurviger.jpg
Mapzen Turn-by-Turn (Valhalla) Routing Worldwide English Worldwide routing by automobile, bus, foot, and bicycle. Yes Valhalla bike.png
Naviki Routing multiple languages Planning bicycle trips and routing and collecting GPS traces
?
 Naviki screenshot.png
Nop's Reit- und Wanderkarte [7] Routing German, English, Italian Dedicated routing for hiking and horseback riding with multiple targets. Dynamic route options e.g. for following marked hiking routes or weather conditions. Options to modify caculated route manually, download or print it. No Osmc riding map screen1.png
OpenRouteService [8] Routing, wheelchair routing Czech, Danish, German, English, Spanish, French, Croatian, Hungarian, Italian, Dutch, Polish, Portuguese, Russian, Ukrainian, Chinese Route navigation based on osm data and TMC for car, bike and pedestrian Yes OpenRouteService screenshot.png
routing.osm.ch Routing German, English, French, Italian Routing with Leaflet slippy map for pedestrians (two types), cyclists (two types) and cars in Switzerland only (based on OSRM) Yes, see OSRM (and links on page)
OpenTripPlanner Routing English A multimodal router combining OSM and Public transport tables Yes OpenTripPlanner screenshot.png
Ride the City Routing English, French, Spanish, Icelandic Bicycle routing based on OSM data. Coverage: Selected big cities (currently 42) in U.S., Canada, Australia, France, Spain, few cities in other countries. No RidetheCity.png
TargomoAPI Routing, car, walk, bike, public transport, network analysis, isochrone English, German Targomo offers routing-based analysis tools - isochrone polygons, points-of-interest, routing, reachability, fleet management, statistics reachability. No R360.png
Open Source Routing Machine (OSRM) Routing Worldwide Bulgarian, Czech, German, Danish, Greek, English, Spanish, Finnish, French, Italian, Irish, Georgian, Latvian, Norwegian Bokmål, Polish, Portuguese, Romanian, Russian, Swedish, Turkish A new fast routing service for car
covering the world 		Yes. OSRM Paris - Vladivostok.jpg
Sputnik General, render, routing Russian Russian website that provides search of state services, POIs and routing to them Partial Sputnik.ru Moskow.png
uNav General, routing multiple languages Map viewer and GPS navigator for Ubuntu Phone Yes UNav.png
VROOM [9] Routing English Vehicle Routing Open-source Optimization Machine
It's aim at providing good solutions to various real-life vehicle routing problems (VRP) within a small computing time. 		Yes
YOURS [10] Routing English Yet another OpenStreetMap Route Service. Goal is to use OpenStreetMap data to make a routing website utilizing as much other (opensource) applications as possible. Routes can be exported as gpx, waypoints and other formats. Yes YourNavigation screenshot.png
brouter.grade.de [11] Waterway routing English Inland waterway routing (Europe) taking size of vessel into account. Based on Brouter router-software Yes European Navigable Waterways map.png


Gallery

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 notes

Showing how to determine connected and unconnected nodes in Potlatch

Some issues reported in Notes are specifically about one-way roads or turn restrictions, and are marked as such.

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: There are some 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.

Other useful data

Developers

This Roads to Rome image was produced using GraphHopper

Open source desktop and server software

Java:

  • OpenRouteService - free, open source library and API with many options and an ecosystem of further tools and libs for Javascript, R, Python, QGIS etc. Has website at openrouteservice.org.
  • GraphHopper is an open source routing engine for road networks written in Java. Fast and memory efficient (for Android, iOS, desktop and server)
  • OpenTripPlanner site is a multi-modal trip planner supporting OSM data. OTP Deployer makes it easy to deploy your own routing instance.
  • BRouter focuses on bike routing and features elevation awareness, alternatives, fully configurable routing profiles and offline routing initially written for Android, but has also a web api. BRouter can also run in QMapShack.
  • OptaPlanner is a lightweight, embeddable planning engine which optimizes the Vehicle Routing Problem, the Travelling Salesman Problem and variants. It is based on GraphHopper and Google Maps APIs.
  • JGraphT (jgrapht.org) - "class library that provides mathematical graph-theory objects and algorithms." Used by JOSM/Plugins/Routing
  • pgrServer is a routing service that uses pgRouting topologies in PostGIS and is loaded to a JGraphT graph for fast searches even with very dense networks.

C/C++:

C#:

  • Itinero – (.Net) libraries for routing and transportation optimization problems; formerly part of OsmSharp library

R:

Ruby:

  • Mormon ruby version of pyroutelib

Python:

Mobile device software

C/Java:

  • Guru Maps online & offline routing for iOS & Android
  • OsmAnd OSM Map, POI and Routing (car/bike/foot, online&offline) for Android and iOS
  • Navit Linux, Windows and portable devices
  • GraphHopper Open Source routing library for Desktop, Android and iOS
  • 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
  • MapFactor Navigator Free for Android and iOS
  • MAPS.ME for Android and iOS

Libraries/development tools

Main article: Frameworks#Navigation

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

  • openrouteservice, free, open source library and API with many options and an ecosystem of further tools and libs for Javascript, R, Python, QGIS etc.
  • 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
  • osm4routing is a command-line tool for parsing OSM data into a routing graph.
  • 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:

  • The default-protocol is the API v0.6 spoken by the main servers. If can contain all data there is in OSM. Get Planet.osm dump.

Routing considerations

Highway-type

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

Type Description (mainly valid in Western Europe)
motorway Usually the maxspeed can be kept for long distances, but these roads can be sensitive to long traffic jams. Usually forbidden for slow traffic (pedestrians, cyclists, agricultural, ...)
trunk Similar to motorways, but these roads can have level crossings, so the stretches where the maximum speed can be reached are shorter. Best avoided when using slow vehicles (sometimes forbidden, depending on the local legislation).
primary Connecting roads between cities, towns and villages. The classification depends mostly on the importance of the areas they connect. This is often also reflected in the number of lanes and the general traffic throughput, but the speed for these classifications is mostly comparable. Usually around 90-100 km/h in the countryside, and 50 (or even 30) km/h when crossing a residential center.
secondary
tertiary
motorway_link Used for on- and off-ramps or complete motorway junctions. Reachable speed depends a lot on curvature, usually around 60-90 km/h
trunk_link In contrast to motorway junctions, these link roads are often very short pieces (e.g., allowing one to turn right without stopping at a traffic light). The speed on these road pieces is very slow, as these often need to give way to the other traffic.
primary_link
secondary_link
tertiary_link
unclassified These roads usually connect farms, isolated houses and small hamlets through the countryside to bigger residential areas. Due to lack of traffic signs, they often have a speed limit way faster than can be driven safely. Speed on a well-maintained but unfamiliar unclassified road will rarely exceed 50 km/h.
residential Residential roads are found in a residential area, so usually have a speed limit of 50 km/h to 30 km/h, with a lot of traffic calming features.
living_street Living streets are streets where slow traffic has absolute right-of-way. The speed limit is normally around 20 km/h. Through-going traffic is absolutely discouraged (and often impossible).
service Service roads are usually found on private property or parking lots. The driver has to pay attention to manoeuvring vehicles, and must wait often.
track Tracks are roads of agricultural purpose. They usually connect fields to farms. The surface sometimes makes them inaccessible for regular cars, or at least limits the speeds to a very slow pace. Tracks should always be avoided for through-going traffic.
pedestrian Pedestrian roads are normally forbidden for motorised vehicles, but can be allowed on certain hours (f.e. early in the morning), or for certain purposes (like delivering goods to shops). Even when allowed, only pedestrian speed is advisable. Cycling can also be forbidden on pedestrian highways.

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 [13] 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
  • traffic-signals, see also traffic_signals:direction=*

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.
  • Speedcollector is a currently defunct service to collect real-world measurements, while it might be possible to derive average speed per way from stored tracks.
  • 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.
  • For an upper limit, see maxspeed=*

List of other tags giving routing hints

Bicycle
Hiking

Routing obstacles and other conditions requiring special consideration

  • crossing=* - pedestrian or other crossing, slowdown

Discontinued routing engines

Main article: Discontinued Routing Engines

Mailing lists

The following mailing lists are relevant to routing

  • osm-routing 'Discussion about Routing with vector Data. Especially concerning OSM Data' Note that it is nearly inactive, it is likely that osm-talk or osm-dev will be preferable for most topics.
  • 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

Videos

Retrieved from "https://wiki.openstreetmap.org/w/index.php?title=Routing&oldid=2767343"