Vincent Larmet


Package presentation

cppRouting is an R package which provide routing algorithms (shortest paths/distances, isochrones) and traffic assignment solvers on non-negative weighted graphs.
cppRouting is characterized by :

cppRouting is therefore particularly adapted for geographer, or whoever who need to calculate accessibility indicators at large scale.
All algorithms are written in C++ and mainly use containers from the Standard Template Library (STL).
This package have been made with Rcpp and RcppParallel packages.

Main functions

cppRouting package provide these functions :

Routing algorithms

Path algorithms proposed by the package are :

1, 2, 3 and 4 are available for one-to-one calculation in get_distance_pair and get_path_pair functions on a non-contracted graph. In these functions, uni-directional Dijkstra algorithm is stopped when the destination node is reached.
A* and NBA* are relevant if geographic coordinates of all nodes are provided. Note that coordinates should be expressed in a projection system.
To be accurate and efficient, A* and NBA* algorithms should use an admissible heuristic function (here the Euclidean distance), i.e cost and heuristic function must be expressed in the same unit.
In cppRouting, heuristic function h for a node (n) is defined such that :
h(n,d) = ED(n,d) / k with h the heuristic, ED the Euclidean distance, d the destination node and a constant k.
So in the case where coordinates are expressed in meters and cost is expressed in time, k is the maximum speed allowed on the road. By default, constant is 1 and is designed for graphs with cost expressed in the same unit than coordinates (for example in meters).
If coordinates cannot be provided, bi-directional Dijkstra algorithm is the best option in terms of performance.

5 is used for one-to-one calculation in get_distance_pair and get_path_pair functions on a contracted graph.

1 is used for one-to-many calculation in get_distance_matrix function on a non-contracted graph.

6 and 7 are available for one-to-many calculation in get_distance_matrix function on a contracted graph.

Traffic assignment algorithms

Traffic assignment models are used to estimate the traffic flows on a network. It take as input origin-destinations matrix describing volume between each OD pair.

All-or-Nothing (AON)

All-or-Nothing assignment (AON) is the most simplistic (and fastest) method to load flow on a network, since it assume there is no congestion effects. The assignment algorithm itself is the procedure that loads the origin-destination matrix to the shortest path trees and produces the flows.
In cppRouting, OD matrix is represented as 3 vectors of equal length :
- from : origin node,
- to : destination node,
- demand : volume.

User Equilibrium (UE)

The term “User Equilibrium” is used to describe a route choice assumption formally proposed by Wardrop :
“The journey times on all the routes actually used are equal and less than those which would be experienced by a single vehicle on any unused routes”.
Note that this principle follows directly from the assumptions that drivers choose minimum time paths, and are well-informed about network conditions.

Unlike AON assignment, this more realistic way to assign flows on a network take into account congestion effect. In this paradigm, the cost of a given link is dependent of the flow on it.

Algorithms proposed by cppRouting for solving UE are :
- link-based : Method of Successive Average (MSA), Frank-Wolfe algorithms (including Conjugate and Bi conjugate variants),
- bush-based : Algorithm B

Examples and applications using cppRouting

see : https://github.com/vlarmet/cppRouting/blob/master/README.md