---
title: "cppRouting"
author: "Vincent Larmet"
date: "`r Sys.Date()`"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{cppRouting}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include=FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
```

# 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.  


# 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 algorithms                    
Path algorithms proposed by the package are :  

  - **1** uni-directional Dijkstra algorithm,
  - **2** bi-directional Dijkstra algorithm,
  - **3** uni-directional A* algorithm  
  - **4** New bi-directional A* algorithm (Piljs & Post, 2009 : see https://repub.eur.nl/pub/16100/ei2009-10.pdf)
  - **5** *one-to-one* bi-directional Dijkstra adapted to contraction hierarchies (Geisberger & al., 2008) 
  - **6** *many-to-many* bi-directional Dijkstra adapted to contraction hierarchies (Geisberger & al., 2008) 
  - **7** PHAST algorithm (Hardware-accelerated shortest path trees), *one-to-all* algorithm adapted to contraction hierarchies (Delling & al., 2011)


*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](doi:10.1680/ipeds.1952.11362) :  
**“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