• Routing Algorithms

Routing Algorithms

Routing Algorithms#

Applications that perform routing (sumo, sumo-gui, duarouter, marouter) support the option --routing-algorithm for selecting among the following values:

Dijkstra (dijkstra)#

Dijkstra's algorithm is the simplest and slowest routing algorithm. It is well suited to routing in time-dependent networks (i.e. when the travel time on an edge depends on the time of day).

A* (astar)#

The A* routing algorithm uses a metric for bounding travel time to direct the search and is often faster than dijkstra. Here, the metric euclidean distance / maximumVehicleSpeed) is used.

ALT#

By using astar together with the option --astar.landmark-distances <FILE> the ALT-Algorithm is activated. The name ALT stands for: A*, Landmarks, triangle inequality. It uses a precomputed distance table to selected network edges (so-called landmarks) to speed up the search, often by a significant factor.

• A lookup table can be generated by creating a file with one landmark edge id per line (e.g. landmarks.txt) and then setting the options --astar.landmark-distances landmarks.txt --astar.save-landmark-distances lookuptable.txt.
  • an alternative input for generating a distance table is one geo-coordinate in the form LON LAT per line
  • the tool generateLandmarks.py can be used to generate a landmark input file by distributing edges around the rim of the network in all directions
• As a rule of thumb using 8-16 edges distributed around the main roads that border the network achieve good ALT-performance. Using more edges is not recommended because each landmark adds a fixed overhead.
• by using astar together with the option --astar.all-distances <FILE> the A* algorithm is used together with a complete (and often huge) distance table to allow for blazing fast search. This is only recommended for medium sized networks with a high number of routing queries

CH (Contraction Hierarchies)#

Contraction Hierarchies is a preprocessing-based routing algorithm. This is very efficient when a large number of queries is expected. The algorithm does not consider time-dependent weights. Instead, new preprocessing can be performed for time-slices of fixed size by setting the option --weight-period <TIME>.

When loading a network with edge permissions, a separate preprocessing is triggered for every vehicle class encountered in a routing task (by automatically switching to CHWrapper).

CHWrapper#

This works like CH but performs separate preprocessing for every vehicle class that is encountered, thereby enabling routing in multi modal scenarios.

CCH (Customizable Contraction Hierarchies)#

Customizable Contraction Hierarchies (CCH) is a preprocessing-based routing algorithm, available in sumo, duarouter and marouter. It splits Contraction Hierarchies into a one-time, weight-independent topology build (the nested dissection order) and a much cheaper "customization" step that recomputes edge weights over that fixed topology. This makes it attractive when edge weights change repeatedly over a simulation run or an assignment (unlike plain CH, which must rebuild the whole hierarchy for every --weight-period).

In all three applications one metric is customized per vehicle type (not per vehicle class). Everything the travel time function reads from the type is therefore exact per metric: the type's maximum speed, vClass-specific edge speed limits, routing preferences and --weights.priority-factor. Only the individual speed factor of the vehicles within a type is approximated by the type's reference vehicle, and --weights.random-factor freezes one random realization into each metric (the same approximation CHWrapper makes when building its hierarchies, instead of a fresh draw per query as with dijkstra and astar).

• In sumo, CCH replaces the periodic hierarchy rebuild of CH/CHWrapper with a metric re-customization that runs whenever the rerouting device adapts edge weights (--device.rerouting.adaptation-interval), so the metrics always reflect the device's current edge weights (--device.rerouting.bike-speeds included, through the metrics of the bicycle types). The re-customization is partial: an edge is only propagated into the metric once its weight has moved by more than --device.rerouting.cch-update-threshold.factor (relative) and --device.rerouting.cch-update-threshold.constant (absolute, in seconds) since it was last applied; the defaults (1 and 0) propagate every change. --device.rerouting.cch-ensemble <INT> keeps that many metrics per type, each with its own frozen --weights.random-factor realization, and assigns every vehicle to one of them by a stable hash of its id, which restores the route diversity of the random factor at the cost of more customization work. A query for a type without a metric yet, or a query carrying a per-request prohibition (e.g. a rerouter closure) that is not already a live permission change, transparently falls back to an embedded A* search.
• In duarouter, CCH supports --weight-files / --weight-period (one metric per vehicle type and weight period, built lazily on first use) and --restriction-params (the restricted edges are masked to infinite weight per affected vehicle type).
• In marouter, one metric is customized for the default vehicle type and re-customized whenever an assignment iteration has updated the travel times, so every iteration routes on the same travel times a dijkstra run would use (CH rebuilds its whole hierarchy at that point instead). As with CH, the metric does not see the k shortest path penalties of --paths, so a warning is issued for --paths greater than 1.

Routing feature support by algorithm#

The table below summarizes which routing features are supported by each --routing-algorithm value. "partial" means the feature is only supported by some of the applications that implement CCH (sumo, duarouter, marouter); see the CCH section above for the exact split.