get_aon: 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)

Value

A data.frame containing edges attributes, including flow.

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 : phast or bi. Otherwise : d, bi or nba. 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

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.

Examples

Run this code

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