assign_traffic: Algorithms for solving the Traffic Assignment Problem (TAP).

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

Algorithms for solving the Traffic Assignment Problem (TAP).

Description

Estimation of the User Equilibrium (UE)

Usage

assign_traffic(
  Graph,
  from,
  to,
  demand,
  algorithm = "bfw",
  max_gap = 0.001,
  max_it = .Machine$integer.max,
  aon_method = "bi",
  constant = 1,
  dial_params = NULL,
  verbose = TRUE
)

Arguments

Graph	An object generated by makegraph function.
from	A vector of origins
to	A vector of destinations.
demand	A vector describing the flow between each origin-destination pair.
algorithm	character. msa, fw, cfw, bfw or dial. Default to bfw. See details.
max_gap	Numeric. Relative gap to achieve. Default to 0.001.
max_it	Numeric. Maximum number of iterations. Default to .Machine$integer.max
aon_method	Character.d, bi, nba, cphast or cbi. Default to bi. See details.
constant	numeric. Constant to maintain the heuristic function admissible in NBA* algorithm. Default to 1, when cost is expressed in the same unit than coordinates. See details
dial_params	List. Named list of hyperparameters for dial algorithm. See details.
verbose	Logical. If TRUE (default), progression is displayed.

Details

The most well-known assumptions in traffic assignment models are the ones following Wardrop's first principle. Traffic assignment models are used to estimate the traffic flows on a network. These models take as input a matrix of flows that indicate the volume of traffic between origin and destination (O-D) pairs. Unlike All-or-Nothing assignment (see get_aon), edge congestion is modeled through the Volume Decay Function (VDF). The Volume Decay Function used is the most popular in literature, from the Bureau of Public Roads :

t = t0 * (1 + a * (V/C)^b) with t = actual travel time (minutes), t0 = free-flow travel time (minutes), a = alpha parameter (unitless), b = beta parameter (unitless), V = volume or flow (veh/hour) C = edge capacity (veh/hour)

Traffic Assignment Problem is a convex problem and solving algorithms can be divided into two categories :

• link-based : Method of Successive Average (msa) and Frank-Wolfe variants (normal : fw, conjugate : cfw and bi-conjugate : bfw). These algorithms uses the descent direction given by AON assignment at each iteration, all links are updated at the same time.

• bush-based : Algorithm-B (dial) The problem is decomposed into sub-problems, corresponding to each origin of the OD matrix, that operate on acyclic sub-networks of the original transportation network, called bushes. Link flows are shifted from the longest path to the shortest path recursively within each bush using Newton method.

Link-based algorithms are historically the first algorithms developed for solving the traffic assignment problem. It require low memory and are known to tail in the vicinity of the optimum and usually cannot be used to achieve highly precise solutions. Algorithm B is more recent, and is better suited for achieve the highest precise solution. However, it require more memory and can be time-consuming according the network size and OD matrix size. In cppRouting, the implementation of algorithm-B allow "batching", i.e. bushes are temporarily stored on disk if memory limit, defined by the user, is exceeded. Please see the package website for practical example and deeper explanations about algorithms. (https://github.com/vlarmet/cppRouting/blob/master/README.md)

Convergence criterion can be set by the user using max_gap argument, it is the relative gap which can be written as : abs(TSTT/SPTT - 1) with TSTT (Total System Travel Time) = sum(flow * cost), SPTT (Shortest Path Travel Time) = sum(aon * cost)

Especially for link-based algorithms (msa, *fw), the larger part of computation time rely on AON assignment. So, choosing the right AON algorithm is crucial for fast execution time. Contracting the network on-the-fly before AON computing can be faster for large network and/or large OD matrix.

AON algorithms are :

• bi : bidirectional Dijkstra algorithm

• nba : bidirectional A* algorithm, nodes coordinates and constant parameter are needed

• d : Dijkstra algorithm

• cbi : contraction hierarchies + bidirectional search

• cphast : contraction hierarchies + phast algorithm

These AON algorithm can be decomposed into two families, depending the sparsity of origin-destination matrix :

• recursive pairwise : bi, nba and cbi. Optimal for high sparsity. One-to-one algorithm is called N times, with N being the length of from.

• recursive one-to-many : d and cphast. Optimal for dense matrix. One-to-many algorithm is called N times, with N being the number of unique from (or to) nodes

For large instance, it may be appropriate to test different aon_method for few iterations and choose the fastest one for the final estimation.

Hyperparameters for algorithm-b are :

• inneriter : number of time bushes are equilibrated within each iteration. Default to 20

• max_tol : numerical tolerance. Flow is set to 0 if less than max_tol. Since flow shifting consist of iteratively adding or substracting double types, numerical error can occur and stop convergence. Default to 1e-11.

• tmp_path : Path for storing bushes during algorithm-B execution. Default using tempdir()

• max_mem : Maximum amount of RAM used by algorithm-B in gigabytes. Default to 8.

In New Bidirectional A star algorithm, euclidean distance is used as heuristic function. To understand the importance of constant parameter, see the package description : https://github.com/vlarmet/cppRouting/blob/master/README.md All algorithms are partly multithreaded (AON assignment).

Value

A list containing :

• The relative gap achieved

• Number of iteration

• A data.frame containing edges attributes, including equilibrated flows, new costs and free-flow travel times.

Note

from, to and demand must be the same length. alpha, beta and capacity must be filled in during network construction. See makegraph.

References

Wardrop, J. G. (1952). "Some Theoretical Aspects of Road Traffic Research".

M. Fukushima (1984). "A modified Frank-Wolfe algorithm for solving the traffic assignment problem".

R. B. Dial (2006). "A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration".

M. Mitradjieva, P. O. Lindberg (2012). "The Stiff Is Moving — Conjugate Direction Frank-Wolfe Methods with Applications to Traffic Assignment".

Examples

#Choose number of cores used by cppRouting
RcppParallel::setThreadOptions(numThreads = 1)

#Data describing edges of the graph
edges<-data.frame(from_vertex=c(0,0,1,1,2,2,3,4,4),
                  to_vertex=c(1,3,2,4,4,5,1,3,5),
                  cost=c(9,2,11,3,5,12,4,1,6))

# Origin-destination trips
trips <- data.frame(from = c(0,0,0,0,1,1,1,1,2,2,2,3,3,4,5,5,5,5,5),
                    to = c(1,2,5,3,2,5,2,4,2,5,2,3,5,2,0,0,3,5,1),
                    flow = c(10,30,15,5,5,2,3,6,4,15,20,2,3,6,2,1,4,5,3))

#Construct graph
graph <- makegraph(edges,directed=TRUE, alpha = 0.15, beta = 4, capacity = 5)


# Solve traffic assignment problem
## using Bi-conjugate Frank-Wolfe algorithm
traffic <- assign_traffic(Graph=graph,
                          from=trips$from, to=trips$to, demand = trips$flow,
                          algorithm = "bfw")
print(traffic$data)

## using algorithm-B
traffic2 <- assign_traffic(Graph=graph,
                           from=trips$from, to=trips$to, demand = trips$flow,
                           algorithm = "dial")
print(traffic2$data)

cppRouting documentation built on Dec. 1, 2022, 5:08 p.m.