Routino

From OpenStreetMap Wiki
Jump to: navigation, search
Available languages
Deutsch English français
Routino
Screenshot of Routino
Author: Andrew M. Bishop
Website: http://www.routino.org/
Version: 2.7 (2014-03-22)
License: Affero GPLv3
Platform: linux ; macos

Flexible router with web interface and routing data analyser.

This router uses a routing algorithm that takes OSM format data as its input and calculates either the shortest or quickest route between two points. To optimise the routing a custom file format is used that contains the defined highways broken into segments and joined in groups of segments with the same properties. This allows the routing to be performed quickly after a modest one-off pre-processing stage.

A selection is possible for any of the major OSM transport types and for each of the main OSM highway types a preference can be provided and a speed limit. Restrictions on one-way streets, weight, height, width and length are also options. Further preferences about road properties (e.g. paved or not) can also be selected.

The processing of the input XML, PBF or O5M file is based on rules in a configuration file that transform the highway tags into tags that are understood by Routino. The generation of the output files (HTML and GPX) uses language fragments selected from another configuration file which allows multi-lingual output from the same database.

The router takes into account private/public/permissive restrictions on highways as well as tagged speed limits and barriers (gates, bollards). The simplest and most common turn restriction relations (those composed of a way, node and way) are supported (since version 2.0).

Website

A website dedicated to Routino contains more information about release status, description, documentation and downloads:

http://www.routino.org/

Algorithm

The OSM data is processed and intially split into nodes, segments (portions of ways that connect pairs of nodes), ways (that store the properties for the segments) and relations (for routes and turn restrictions). A pre-processing step is performed to identify interesting nodes (called super-nodes) and add to this segments a set of super-segments that connect a pair of super-nodes such that the optimum route between them is along a set of segments with identical routing properties.

When it comes to routing a route is found by following all segments to the closest super-nodes from the start and end points and then only following super-segments between these sets of super-nodes. Finally the super-segments are decomposed into segments to provide the complete route.

Turn Restrictions

Routino can handle turn restrictions that are composed of a single node for the via point and a highway for each of the from and to components.

The addition of turn restrictions adds quite a few complications to a routing algorithm. As the simplest example it means that a route between two waypoints may need to pass through the same node more than once in different directions to avoid a turn restriction. In Routino before version 2.0 where there were no turn restrictions this was not the case and routes could be calculated just as a set of nodes. With turn restrictions a route must be calculated as a set of nodes and segments (in the Routino data model the segment/node pair are like the body and head of an arrow).

The second complexity of including turn restrictions is that U-turns within a highway must be forbidden. If this was not the case then it would be possible to bypass a "no left turn" restriction by driving past the restriction and performing a U-turn to come back and turn right. In Routino this restriction on U-turns is taken as default so that when calculating a route with three waypoints for example the route will continue from the middle waypoint in the same direction as it arrived (for those forms of transport that obey turn restrictions). The only time that a U-turn is allowed is when starting from a waypoint and facing a dead-end highway (otherwise the route could not be calculated at all).

In terms of the Routino data model of super-nodes and super-segments for calculating routes quickly there are some extra complications such that super-segments cannot end at a turn restriction node and a dead-end road with a loop cannot be optimised away.

Data Pruning

During the pre-processing step a number of simplifications or improvements of the raw data can be made. The intention of these is to reduce the database size (to speed up routing) and to reduce the number of routes that cannot be calculated. These data pruning options are enabled by default although they can be disabled on the command line or their behaviour tuned.

The types of data pruning and their purpose are described below:

  • Remove isolated segments.
    • In the first instance (and the original implementation) this was to detect regions of the map of small size that are not connected to the rest of the highway network. The size limit defaults to a total of 500m and the purpose is to avoid selecting one of these highways as a waypoint (nearest to the selected coordinates) which would fail to route unless all waypoints were within the same small region.
    • In the second instance (and the improved implementation starting in version 2.4) each transport type (e.g. motorcar, foot) is examined in turn and isolated regions for that particular transport type have their tags changed to disallow that transport type. Any regions which are completely isolated will have all transport types removed one by one and be deleted from the database. This removes another set of unroutable waypoint highways from being selected.
  • Remove short segments. This will remove short stub highways (consisting of a single segment) completely and short segments within a highway will be replaced by moving the two endpoints to the midpoint of the segment and extending the adjacent segments. The length limit used by default for this is 5m and when removing short segments from within highways the total highway length is preserved even if it does not match the updated geometry. Care is also taken not to remove short segments if either end is a junction or a barrier.
  • Remove unneeded nodes within almost straight highways. Each node within a highway is examined to see whether its removal would cause the highway to move by more than a small amount (limit set to 3m). If there is no significant change then the node is removed and the length of the replacement segment set to the sum of the lengths of the two original segments that met at that node. This check is performed along the highway and multiple nodes can be removed provided that no point along the final highway deviates significantly from the original path. This leads to a large reduction in the database size while at the same time giving the same calculated routes with the correct geometry to a small margin.

Routing Preferences

Many routing preferences are available, as of version 2.3 the following can be selected when calculating a route:

  • The mode of transport: foot, horse, wheelchair, bicycle, moped, motorbike, motorcar, goods, hgv, psv.
  • A preference for each type of highway (percentage): motorway, trunk, primary, secondary, tertiary, unclassified, residential, service, track, cycleway, path, steps, ferry.
  • A speed limit for each type of highway (in addition to not exceeding the speed limit).
  • A preference for a highway property (percentage): paved, multilane, bridge, tunnel, footroute, bicycleroute.
  • The option to obey or not: one-way streets, turn restrictions.
  • Limits on the vehicle: height, weight, width, length.

In addition the route selected can be the fastest or shortest (taking into account the specified preferences of the other highway properties).

A route can be made up of up to 99 waypoints (a smaller limit can be applied to the online router) with an optional starting direction specified.

Web Interface

Router

The Routino software as supplied contains an implementation of a router web page using a Slippy Map that allows markers to be placed or locations to be searched (calling Nominatim from a server CGI) before calculating a route.

The routing preferences default to the a pre-determined set depending on the transport type selected. These can then be edited before the route is calculated. Selecting one of the "Shortest" or "Quickest" buttons will calculate the route and display the results. The route is displayed on the map and by moving the mouse over the route description each important junction can be highlighted on the map with a description of it.

Routino Route.png

Data Visualiser

The web interface that allows routes to be calculated also provides a way of visualising the data that is used for calculating the route. A second web page is available (linked to the router page by the "Data" tab) that can be used to display various information about the contents of the Routino routing database.

Routino Visualiser.png

This information is:

  • Junctions and the number of segments meeting at each junction.
  • Super-nodes and super-segments (as described in the algorithm section).
  • Oneway highway segments.
  • Highway segments of a particular type (e.g. motorway, trunk, primary etc).
  • Highway segments accessible to a particular transport type (e.g. motorcar, bicycle, foot etc).
  • Barrier nodes that block a particular transport type.
  • Turn restrictions.
  • Limits (maximum speed, maximum weight, maximum height, width or length).
  • Properties (paved, multiple Lanes, bridge, tunnel, walking route, bicycle route, cycle both ways).
  • Parsing Errors (warnings from the database generation step).

When Routino fails to find a route this information can be used to check whether the expected route is available for the selected routing preferences.

Error Log

When creating the routing database Routino can create a log file of errors that it has found in the data (using the --errorlog option). The majority of the problems that are reported are restricted to tags that a router should be expected to understand, to highways or to relations.

The types of errors detected are:

  • Unrecognised tags (since Routino can only use the small set of tags that it understands any unrecognised tags could lead to routing errors and could be tagging errors in the data).
  • Highways with zero or one node.
  • Highways with repeated adjacent nodes (segments of zero length).
  • Highways with overlapping segments.
  • Overlapping highways.
  • Highway areas overlapping other highways.
  • Turn restrictions with missing data (e.g. no from way, via node or to way).
  • Turn restrictions with inconsistent data (e.g. via node not at the end of the from way or the to way).
  • Route relations for foot or bicycle that use highways that do not allow the particular transport type.
  • Relations that have no nodes, ways or sub-relations.
  • Relations that include themselves as sub-relations.

Since the purpose of the Routino error log is to find data that causes problems for Routino it does not mean that all reported items are data errors. Some of them however will be data errors that will affect multiple data users.

Demonstration

An online demonstration of the router for the UK (actually Great Britain, Ireland and Isle of Man as defined by the OpenStreetMap data dumps at GeoFabrik[1]) is available:

OpenLayers version (http://www.routino.org/uk-openlayers/) Leaflet version (http://www.routino.org/uk-leaflet/)

Online demonstration of the router for Belarus is available:

http://mgorka.info/by/

For Germany:

https://routino.arch.tu-dresden.de/routino/router.html

(No information on update frequency given; age of data files is visible under "Data" -> "Display data statistics" on all routino websites)

Software

The software is released under the Affero GPLv3 license and source code can be downloaded from here:

http://www.routino.org/download/

History

This router was originally announced on the talk-gb list[2] as an online router using OSM data. Later discussion[3] clarified that the software running the online webpage would be released as free software.

Version 1.0

Released on 8th April 2009.

Version 1.1

Released on 13th June 2009.

The main changes in version 1.1 were the addition of a set of web-pages (including Javascript map using OpenLayers) to allow a Routino web-server to be configured easily.

Version 1.2

Released on 21st October 2009.

The primary focus of the version 1.2 release was optimisation of routing speed and reduction in database size, there were also a small number of new features.

Version 1.3

Released on 21st January 2010.

The main focus of the version 1.3 release is adding new features like highway properties, some new transport types, start/via/end points within segments and turn instructions.

Version 1.4

Released on 31st May 2010

The primary new features in version 1.4 are the addition of configuration files containing tagging rules, routing profiles and translations for the output files.

Version 1.4.1

Released on 10th July 2010

This version fixes a few serious bugs, reduces memory usage and therefore increases routing speed.

Version 1.5

Released on 30th October 2010

The main new features in this version are the addition of routing on ferrys, recognition of barriers (node properties) and new highway properties for walking and cycling routes.

Version 1.5.1

Released on 13th November 2010

This version fixes a few bugs that caused planetsplitter to crash for some users.

Version 2.0

Released on 30th May 2011

Adds turn restriction processing and stops U-turns at waypoints unless required to get out of a dead-end.

Version 2.0.1

Released on 7th June 2011

A bug fix release to stop crashes on some invalid turn restrictions. Also fix the online demonstration which stopped working at the time of the version 2.0 update.

Version 2.0.2

Released on 26th June 2011

A bug fix release to stop crashes on 64-bit machines in certain cases.

Version 2.0.3

Released on 4th August 2011

A bug fix release to stop crashes on 64-bit machines in certain cases. Also fixes some pathological routing cases.

Version 2.1

Released on 3rd October 2011

Improve the OSM parsing, include transport specific tag processing files and optionally create an error log file listing problems found during parsing.

Version 2.1.1

Released on 23rd October 2011

Much faster routing, handle the 'except' tag of turn restrictions.

Version 2.1.2

Released on 12th November 2011

Much faster routing (again), improve some translated outputs, add Russian translations, other small bug fixes.

Version 2.2

Released on 3rd March 2012

Much smaller database by removing unneeded nodes and segments. Better description of routing around roundabouts (e.g. "leave roundabout by third exit").

Version 2.3

Released on 21st July 2012

Mostly improvements to the web pages but also a slight decrease in database generation time and some bug fixes.

Version 2.3.1

Released on 11th August 2012

Many bug fixes for web pages mainly related to waypoint editing.

Version 2.3.2

Released on 6th October 2012

Some routing bug fixes (routes that start or end at a barrier, oneway loops at waypoint) and fix missing route instructions (final section) in some cases.

Version 2.4

Released on 8th December 2012

The database generation step will now accept an OSM changes file although optimisation of the raw data to create the final database still needs to be performed in full again.

Version 2.4.1

Released on 17th December 2012

A fairly serious bug with the router that has been present since version 1.1 has been fixed. This stopped routes being calculated when they require using highways with very low preference or that have very low property preferences.

Version 2.5

Released on 9th February 2013

A new XML parser and options for PBF and O5M/O5C parsing as well as reading of bzip2 or gzip compressed files. More complex tag parsing configuration file options and more tags processed. Replace motorbike with motorcycle and change the handling of the lanes tag.

Version 2.5.1

Released on 20th April 2013

Bug fixes for XML parsing (4-byte UTF-8), XML quoting (7-bit ASCII special chars), installation documentation and routing for some special case short routes.

Version 2.6

Released on 6th July 2013

Much faster database generation and faster routing (especially for slim mode). Simpler compile-time configuration (Makefile.conf). Improved data visualiser with access to data parsing errors and the ability to see the details of any item displayed.

Version 2.7

Released on 22nd March 2014

Improved web pages for touch screen devices in particular and easier to create translated versions. Both OpenLayers and Leaflet Javascript map libraries are now supported. Allow cycling both ways on highways with appropriate tags (e.g. "cycleway=opposite_lane").


References

  1. http://download.geofabrik.de/osm/europe/
  2. http://lists.openstreetmap.org/pipermail/talk-gb/2009-March/007122.html
  3. http://lists.openstreetmap.org/pipermail/talk-gb/2009-March/003665.html