Routino

Routino
Author:	Andrew M. Bishop
License:	Affero GPLv3
Platforms:	Linux, macOS, Windows, and Web
Version:	3.4.1 (2023-07-01)
Languages:	English, Czech, Dutch, German, Finnish, French, Hungarian, Italian, Polish, Russian, Slovak, and Spanish
Website:	http://www.routino.org/
Programming language:	C
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 3.0 the routing function is available as a shared library (for Windows or UNIX-like systems) so that routes can be calculated from other programs. A routing database generated using the command line tools is still required (the library does not include creating the database).

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.

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.

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) 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 as an online router using OSM data. Later discussion clarified that the software running the online webpage would be released as free software.

Version 1.0

Released on 8th April 2009.

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 3.0

Released on 12 September 2015

Windows compilation and library providing routing API.

Versions 3.1 & 3.1.1

Released on 5th March 2016 and 6th March 2016

Various bug fixes and improvements, default to 64-bit node IDs.

Version 3.2

Released on 12th March 2017

Various minor bug fixes, more translated phrases and some web page improvements.

Versions 3.3, 3.3.1 & 3.3.2 & 3.3.3

Released on 7th September 2019, 8th September 2019, 18th September 2019 and 30th December 2020

Various bug fixes, some important ones that affect large data sets. Updated to latest version of OpenLayers. Includes Python bindings for routing and access to database.

Version 3.4

Released on 11th June 2023

Various bug fixes, some important ones that affect large data sets. Updated to latest version of OpenLayers and Leaflet. Updated translations.