get_aon {cppRouting} | R Documentation |
Given an origin-destination matrix, compute All-or-Nothing assignment.
Description
Given an origin-destination matrix, compute All-or-Nothing assignment.
Usage
get_aon(Graph, from, to, demand, algorithm = "bi", constant = 1)
Arguments
Graph |
An object generated by makegraph, or cpp_contract function. |
from |
A vector of origins |
to |
A vector of destinations. |
demand |
A vector describing the flow between each origin-destination pair. |
algorithm |
character. For contracted network : |
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 |
Details
All-or-Nothing assignment (AON) is the simplest 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.
Origin-destination matrix is represented via 3 vectors : from
, to
and demand
.
There is two variants of algorithms, depending the sparsity of origin-destination matrix :
recursive one-to-one : Bidirectional search (
bi
) and Bidirectional A* (nba
). Optimal for high sparsity.recursive one-to-many : Dijkstra (
d
) and PHAST (phast
). Optimal for dense matrix.
For large network and/or large OD matrix, this function is a lot faster on a contracted network. 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 multithreaded. Please use RcppParallel::setThreadOptions()
to set the number of threads.
Value
A data.frame
containing edges attributes, including flow.
Note
'from', 'to' and 'demand' must be the same length.
See Also
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)
# Compute All-or-Nothing assignment
aon <- get_aon(Graph=graph, from=trips$from, to=trips$to, demand = trips$flow, algorithm = "d")
print(aon)