Support Our Open Source Project

Creating and maintaining an open source project takes significant time and effort. If you find value in our work and would like to see it continue to grow and improve, please consider making a donation. Your support helps us cover hosting costs, development tools, and allows us to dedicate more time to enhancing this project. Every contribution, no matter how small, makes a big difference. Thank you for supporting open source!

<img src="https://www.scclive.org/wp-content/uploads/2017/03/PayPal-Donate-Button.png" width="150">

cppRouting v3 : Algorithms for Routing and Solving the Traffic Assignment Problem

Vincent LARMET November 24, 2022

• Package presentation
• Installation
  • Stable version from CRAN
  • or from github
• What are we talking about ?
• Readme Data
  • Set the number of threads used by cppRouting
  • Instantiate the graph
• Main functions
• Routing
  • Algorithms
  • Compute isochrones
  • Compute possible detours within a fixed additional cost
  • Contraction hierarchies
  • Work with dual weighted network
• Network simplification
• Traffic assignment
  • All-or-Nothing (AON)
    • Choosing the best routing algorithm
  • User Equilibrium (UE)
    • Link-based algorithms
    • Bush-based algorithms
    • Performance comparison
• Algorithm compatibility
• Parallel implementation
• Applications
  • Application 1 : Calculate Two Step Floating Catchment Areas (2SFCA) of general practitioners in France
  • Application 2 : Calculate the minimum travel time to the closest maternity ward in France
  • Application 3 : Calculate average commuting time to go to job in France
  • Application 4 : Calculate the flow of people crossing each municipality in the context of commuting in Bourgogne-Franche-Comte region
• Benchmark with other R packages
• Citation

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 :

• its ability to work on large road graphs (country/continent scale)
• its large choice of one-to-one shortest path algorithms
• its implementation of contraction hierarchies and associated routing algorithms
• its large choice of algorithms for solving the traffic assignment problem (TAP)
• its high performance through memory usage and parallel programming

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.

Installation

Stable version from CRAN

install.packages("cppRouting")

or from github

library(remotes)
remotes::install_github("vlarmet/cppRouting")

What are we talking about ?

cppRouting implements algorithms belonging to graph theory, so let’s define what a graph is.
A graph is commonly used to represent a network, which is composed of vertices connected by edges.

<!-- -->

In cppRouting, an edge has at least three attributes : vertice’s ID from which it start, vertice’s ID from which it end and a weight (length, flow, travel time …).

Readme Data

**This README file and all time measurements were made on a Windows 10 computer, with 11th generation i5 (6 cores) processor and 32GB of memory. **
The data presented here is the official french road network describing over 500000 km of roads.
All data used in this README are free and can be downloaded here :

• roads : http://professionnels.ign.fr/route500
• general practitioners location : https://www.insee.fr/fr/statistiques/3568614?sommaire=3568656#consulter
• maternity wards location : https://www.insee.fr/fr/statistiques/3568611?sommaire=3568656#dictionnaire
• shapefile of the ~36000 communes in France : http://professionnels.ign.fr/adminexpress
• commuting to work from the French national census : https://www.insee.fr/fr/statistiques/3566477#consulter

Graph data have been preprocessed for more readability (see data_preparation.R).

The final graph is composed of 234615 nodes and 685118 edges.
Data has to be a 3 columns data.frame or matrix containing from, to and a cost/distance column. Here the cost is the time needed to travel in each edges (in minutes). From and to are vertices IDs (character or numeric).

library(cppRouting)
library(dplyr)
library(sf)
library(ggplot2)
library(concaveman)
library(ggmap)
library(tmap)
library(microbenchmark)
library(reshape2)
library(kableExtra)

#Reading french road data
roads  <-  read.csv("roads.csv",colClasses = c("character","character","numeric"))
#Shapefile data of communes (polygons)
com  <-  read_sf("com_simplified_geom.shp")
#Correspondance file between communes and nodes in the graph (nearest node to each commune centroid)
ndcom  <-  read.csv("node_commune.csv",colClasses = c("character","character","numeric"))
#General practitioners locations
med  <-  read.csv("doctor.csv",colClasses = c("character","numeric","character","numeric"))
#Import materinty ward locations
maternity  <-  read.csv("maternity.csv",colClasses = c("character","numeric"))
#Commuting data from national census
load("commuting.Rds")
#Import nodes coordinates (projected in EPSG : 2154)
coord  <-  read.csv("coordinates.csv",colClasses = c("character","numeric","numeric"))

Head of road network data

head(roads)

##   from     to    weight
## 1    0 224073 0.4028571
## 2    1  65036 3.5280000
## 3    2 173723 1.8480000
## 4    3      2 2.5440000
## 5    4 113129 4.9680000
## 6    5      4 1.6680000

Head of coordinates data

head(coord)

##   ID        X       Y
## 1  0 805442.8 6458384
## 2  1 552065.9 6790520
## 3  2 556840.2 6790475
## 4  3 554883.7 6790020
## 5  4 548345.2 6791000
## 6  5 547141.3 6790434

Set the number of threads used by cppRouting

RcppParallel::setThreadOptions(numThreads = 1)

Instantiate the graph

#Instantiate a graph with coordinates
graph  <-  makegraph(roads, directed = T, coords = coord)

Graph object have some useful attributes for the user :

• graph$nbnode : total number of vertices,
• graph$dict$ref : vertices ids.

Other attributes are internals data and have no interest for the user. All graph attributes should never be modified by the user.

Main functions

cppRouting package provide these functions :

• get_distance_matrix : compute distance matrix (between all combinations origin-destination nodes - one-to-many),
• get_distance_pair : compute distances between origin and destination by pair (one-to-one),
• get_path_pair : compute shortest paths between origin and destination by pair (one-to-one),
• get_multi_paths : compute shortest paths between all origin nodes and all destination nodes (one-to-many),
• get_isochrone : compute isochrones/isodistances with one or multiple breaks.
• get_detour : return nodes that are reachable within a fixed additional cost around shortest paths. This function can be useful in producing accessibility indicators.
• cpp_simplify : remove non-intersection nodes, duplicated edges and isolated loops in the graph. Graph topology is preserved so distance calculation is faster and remains true. This function can be applied to very large graphs (several millions of nodes).
• cpp_contract : contract the graph by applying contraction hierarchies algorithm.
• get_aon : given an origin-destination matrix, compute All-or-Nothing assignment.
• assign_traffic : given an origin-destination matrix, estimate the traffic flows on the network.

Routing

As the package name suggest, cppRouting is initially aimed to provide efficient algorithms for finding shortest paths.

Algorithms

Path algorithms proposed by the package are :

• 1 uni-directional Dijkstra algorithm,
• 2 bi-directi