Movatterモバイル変換

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

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 (seeget_aon), edge congestion is modeled through theVolume 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) andFrank-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.IncppRouting, 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 andcbi. Optimal for high sparsity. One-to-one algorithm is called N times, with N being the length of from.

• recursive one-to-many :d andcphast. 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 differentaon_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 usingtempdir()

• 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.mdAll algorithms are partly multithreaded (AON assignment).

Value

Alist 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 anddemand must be the same length.alpha,beta andcapacity must be filled in during network construction. Seemakegraph.

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 cppRoutingRcppParallel::setThreadOptions(numThreads = 1)#Data describing edges of the graphedges<-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 tripstrips <- 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 graphgraph <- makegraph(edges,directed=TRUE, alpha = 0.15, beta = 4, capacity = 5)# Solve traffic assignment problem## using Bi-conjugate Frank-Wolfe algorithmtraffic <- assign_traffic(Graph=graph,                          from=trips$from, to=trips$to, demand = trips$flow,                          algorithm = "bfw")print(traffic$data)## using algorithm-Btraffic2 <- assign_traffic(Graph=graph,                           from=trips$from, to=trips$to, demand = trips$flow,                           algorithm = "dial")print(traffic2$data)

Contraction hierarchies algorithm

Description

Contract a graph by using contraction hierarchies algorithm

Usage

cpp_contract(Graph, silent = FALSE)

Arguments

Details

Contraction hierarchies is a speed-up technique for finding shortest path in a graph.It consist of two steps : preprocessing phase and query.cpp_contract() preprocess the input graph to later use special query algorithm implemented inget_distance_pair,get_distance_matrix,get_aon andget_path_pair functions.To see the benefits of using contraction hierarchies, see the package description :https://github.com/vlarmet/cppRouting/blob/master/README.md.

Value

A contracted graph.

See Also

cpp_simplify

Examples

#Data describing edges of the graphedges<-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))#Construct cppRouting graphgraph<-makegraph(edges,directed=TRUE)#Contract graphcontracted_graph<-cpp_contract(graph,silent=TRUE)

Reduce the number of edges by removing non-intersection nodes, duplicated edges and isolated loops in the graph.

Description

Reduce the number of edges by removing non-intersection nodes, duplicated edges and isolated loops in the graph.

Usage

cpp_simplify(  Graph,  keep = NULL,  rm_loop = TRUE,  iterate = FALSE,  silent = TRUE)

Arguments

Details

To understand why process can be iterated, see the package description :https://github.com/vlarmet/cppRouting/blob/master/README.md

Value

The simplified cppRouting graph

Note

Additional edge attributes likeaux,alpha,beta andcapacity will be removed.The first iteration usually eliminates the majority of non-intersection nodes and is therefore faster.

Examples

#Simple directed graphedges<-data.frame(from=c(1,2,3,4,5,6,7,8),                  to=c(0,1,2,3,6,7,8,5),                  dist=c(1,1,1,1,1,1,1,1))#Plotif(requireNamespace("igraph",quietly = TRUE)){igr<-igraph::graph_from_data_frame(edges)plot(igr)}#Construct cppRouting graphgraph<-makegraph(edges,directed=TRUE)#Simplify the graph, removing loopsimp<-cpp_simplify(graph, rm_loop=TRUE)#Convert cppRouting graph to data framesimp<-to_df(simp)#Plotif(requireNamespace("igraph",quietly = TRUE)){igr<-igraph::graph_from_data_frame(simp)plot(igr)}#Simplify the graph, keeping node 2 and keeping loopsimp<-cpp_simplify(graph,keep=2 ,rm_loop=FALSE)#Convert cppRouting graph to data framesimp<-to_df(simp)#Plotif(requireNamespace("igraph",quietly = TRUE)){igr<-igraph::graph_from_data_frame(simp)plot(igr)}

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

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

There is two variants of algorithms, depending thesparsity 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 aremultithreaded. Please useRcppParallel::setThreadOptions() to set the number of threads.

Value

Adata.frame containing edges attributes, including flow.

Note

'from', 'to' and 'demand' must be the same length.

See Also

cpp_contract,assign_traffic

Examples

#Choose number of cores used by cppRoutingRcppParallel::setThreadOptions(numThreads = 1)#Data describing edges of the graphedges<-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 tripstrips <- 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 graphgraph<-makegraph(edges,directed=TRUE)# Compute All-or-Nothing assignmentaon <- get_aon(Graph=graph, from=trips$from, to=trips$to, demand = trips$flow, algorithm = "d")print(aon)

Return the nodes that can be reached in a detour time set around the shortest path

Description

Return the nodes that can be reached in a detour time set around the shortest path

Usage

get_detour(Graph, from, to, extra = NULL, keep = NULL, long = FALSE)

Arguments

Details

Each returned nodesn meet the following condition :

SP(o,n) + SP(n,d) < SP(o,d) + t

withSP shortest distance/time,o the origin node,d the destination node andt the extra cost.

Modified bidirectional Dijkstra algorithm is ran for each path.

This algorithm ismultithreaded. Please useRcppParallel::setThreadOptions() to set the number of threads.

Value

list or adata.frame of nodes that can be reached

Note

from andto must be the same length.

Examples

#Choose number of cores used by cppRoutingRcppParallel::setThreadOptions(numThreads = 1)if(requireNamespace("igraph",quietly = TRUE)){#Generate fully connected graphgf<- igraph::make_full_graph(400)igraph::V(gf)$names<-1:400#Convert to data frame and add random weightsdf<-igraph::as_long_data_frame(gf)df$dist<-sample(1:100,nrow(df),replace = TRUE)#Construct cppRouting graphgraph<-makegraph(df[,c(1,2,5)],directed = FALSE)#Pick up random origin and destination nodeorigin<-sample(1:400,1)destination<-sample(1:400,1)#Compute distance from origin to all nodesor_to_all<-get_distance_matrix(graph,from=origin,to=1:400)#Compute distance from all nodes to destinationall_to_dest<-get_distance_matrix(graph,from=1:400,to=destination,)#Get all shortest paths from origin to destination, passing by each node of the graphtotal_paths<-rowSums(cbind(t(or_to_all),all_to_dest))#Compute shortest path between origin and destinationdistance<-get_distance_pair(graph,from=origin,to=destination)#Compute detour with an additional cost of 3det<-get_detour(graph,from=origin,to=destination,extra=3)#Check result validitylength(unlist(det))length(total_paths[total_paths < distance + 3])}

Compute all shortest distance between origin and destination nodes.

Description

Compute all shortest distance between origin and destination nodes.

Usage

get_distance_matrix(  Graph,  from,  to,  algorithm = "phast",  aggregate_aux = FALSE,  allcores = FALSE)

Arguments

Details

If graph is not contracted,get_distance_matrix() recursively perform Dijkstra algorithm for eachfrom nodes.If graph is contracted, the user has the choice between :

• many to many contraction hierarchies (mch) : optimal for square matrix.

• PHAST (phast) : outperform mch on rectangular matrix

Shortest path is always computed according to the main edge weights, corresponding to the 3rd column ofdf argument inmakegraph() function.Ifaggregate_aux argument isTRUE, the values returned are the sum of auxiliary weights along shortest paths.

All algorithms aremultithreaded.allcores argument is deprecated, please useRcppParallel::setThreadOptions() to set the number of threads.

See details in package website :https://github.com/vlarmet/cppRouting/blob/master/README.md

Value

Matrix of shortest distances.

Note

It is not possible to aggregate auxiliary weights on a Graph object coming fromcpp_simplify function.

See Also

get_distance_pair,get_multi_paths

Examples

#Choose number of cores used by cppRoutingRcppParallel::setThreadOptions(numThreads = 1)#Data describing edges of the graphedges <- 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),                    time = c(9,2,11,3,5,12,4,1,6),                    dist = c(5,3,4,7,5,5,5,8,7))#Construct directed  graph with travel time as principal weight, and distance as secondary weightgraph <- makegraph(edges[,1:3], directed=TRUE, aux = edges$dist)#Get all nodes IDsnodes <- graph$dict$ref# Get matrix of shortest times between all nodes : the result are in time unittime_mat <- get_distance_matrix(graph, from = nodes, to = nodes)# Get matrix of distance according shortest times : the result are in distance unitdist_mat <- get_distance_matrix(graph, from = nodes, to = nodes, aggregate_aux = TRUE)print(time_mat)print(dist_mat)

Compute shortest distance between origin and destination nodes.

Description

Compute shortest distance between origin and destination nodes.

Usage

get_distance_pair(  Graph,  from,  to,  aggregate_aux = FALSE,  algorithm = "bi",  constant = 1,  allcores = FALSE)

Arguments

Details

If graph is not contracted, the user has the choice between :

• unidirectional Dijkstra (Dijkstra)

• A star (A*) : projected coordinates should be provided

• bidirectional Dijkstra (bi)

• New bi-directional A star (NBA) : projected coordinates should be provided

If the input graph has been contracted bycpp_contract function, the algorithm is a modified bidirectional search.

Shortest path is always computed according to the main edge weights, corresponding to the 3rd column ofdf argument inmakegraph function.Ifaggregate_aux argument isTRUE, the values returned are the sum of auxiliary weights along shortest paths.

In A* and New Bidirectional A star algorithms, euclidean distance is used as heuristic function.

All algorithms aremultithreaded.allcores argument is deprecated, please useRcppParallel::setThreadOptions() to set the number of threads.

To understand how A star algorithm work, seehttps://en.wikipedia.org/wiki/A*_search_algorithm.To understand the importance of constant parameter, see the package description :https://github.com/vlarmet/cppRouting/blob/master/README.md

Value

Vector of shortest distances.

Note

from andto must be the same length.It is not possible to aggregate auxiliary weights on a Graph object coming fromcpp_simplify function.

See Also

get_distance_matrix,get_path_pair,cpp_contract

Examples

#Choose number of cores used by cppRoutingRcppParallel::setThreadOptions(numThreads = 1)#Data describing edges of the graphedges<-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),                  dist = c(5,3,4,7,5,5,5,8,7))#Construct directed  graph with travel time as principal weight, and distance as secondary weightgraph <- makegraph(edges[,1:3], directed=TRUE, aux = edges$dist)#Get all nodes IDsnodes <- graph$dict$ref# Get shortest times between all nodes : the result are in time unittime_mat <- get_distance_pair(graph, from = nodes, to = nodes)# Get distance according shortest times : the result are in distance unitdist_mat <- get_distance_pair(graph, from = nodes, to = nodes, aggregate_aux = TRUE)print(time_mat)print(dist_mat)

Compute isochrones/isodistances from nodes.

Description

Compute isochrones/isodistances from nodes.

Usage

get_isochrone(Graph, from, lim, setdif = FALSE, keep = NULL, long = FALSE)

Arguments

Details

Iflength(lim) > 1, value is alist oflength(from), containinglists oflength(lim).

All algorithms aremultithreaded. Please useRcppParallel::setThreadOptions() to set the number of threads.

For large graph,keep argument can be used for saving memory.

Value

list or adata.frame containing reachable nodes below cost limit(s).

Note

get_isochrone() recursively perform Dijkstra algorithm for eachfrom nodes and stop when cost limit is reached.

Examples

#Choose number of cores used by cppRoutingRcppParallel::setThreadOptions(numThreads = 1)#Data describing edges of the graphedges<-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))#Construct directed graphdirected_graph<-makegraph(edges,directed=TRUE)#Get nodes reachable around node 4 with maximum distances of 1 and 2iso<-get_isochrone(Graph=directed_graph,from = "4",lim=c(1,2))#With setdif set to TRUEiso2<-get_isochrone(Graph=directed_graph,from = "4",lim=c(1,2),setdif=TRUE)print(iso)print(iso2)

Compute all shortest paths between origin and destination nodes.

Description

Compute all shortest paths between origin and destination nodes.

Usage

get_multi_paths(Graph, from, to, keep = NULL, long = FALSE)

Arguments

Details

get_multi_paths() recursively perform Dijkstra algorithm for each 'from' nodes. It is the equivalent ofget_distance_matrix, but it return the shortest path node sequence instead of the distance.

This algorithm ismultithreaded. Please useRcppParallel::setThreadOptions() to set the number of threads.

Value

List or a data.frame containing shortest paths.

Note

Be aware that if 'from' and 'to' have consequent size, output will require much memory space.

See Also

get_path_pair,get_isochrone,get_detour

Examples

#Choose number of cores used by cppRoutingRcppParallel::setThreadOptions(numThreads = 1)#Data describing edges of the graphedges<-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))#Get all nodesnodes<-unique(c(edges$from_vertex,edges$to_vertex))#Construct directed graphdirected_graph<-makegraph(edges,directed=TRUE)#Get all shortest paths (node sequences) between all nodesdir_paths<-get_multi_paths(Graph=directed_graph, from=nodes, to=nodes)print(dir_paths)#Get the same result in data.frame formatdir_paths_df<-get_multi_paths(Graph=directed_graph, from=nodes, to=nodes, long = TRUE)print(dir_paths_df)

Compute shortest path between origin and destination nodes.

Description

Compute shortest path between origin and destination nodes.

Usage

get_path_pair(  Graph,  from,  to,  algorithm = "bi",  constant = 1,  keep = NULL,  long = FALSE)

Arguments

Details

If graph is not contracted, the user has the choice between :

• unidirectional Dijkstra (Dijkstra)

• A star (A*) : projected coordinates should be provided

• bidirectional Dijkstra (bi)

• New bi-directional A star (NBA) : projected coordinates should be provided

If the input graph has been contracted bycpp_contract function, the algorithm is a modified bidirectional search.

InA* andNBA algorithms, euclidean distance is used as heuristic function.

All algorithms aremultithreaded. Please useRcppParallel::setThreadOptions() to set the number of threads.

To understand the importance of constant parameter, see the package description :https://github.com/vlarmet/cppRouting/blob/master/README.md

Value

list or adata.frame containing shortest path nodes between from and to.

Note

from andfrom must be the same length.

See Also

get_multi_paths,get_isochrone,get_detour

Examples

#Choose number of cores used by cppRoutingRcppParallel::setThreadOptions(numThreads = 1)#Data describing edges of the graphedges<-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))#Get all nodesnodes<-unique(c(edges$from_vertex,edges$to_vertex))#Construct directed and undirected graphdirected_graph<-makegraph(edges,directed=TRUE)non_directed<-makegraph(edges,directed=FALSE)#Sampling origin and destination nodesorigin<-sample(nodes,10,replace=TRUE)destination<-sample(nodes,10,replace=TRUE)#Get distance between origin and destination in the two graphsdir_paths<-get_path_pair(Graph=directed_graph, from=origin, to=destination)non_dir_paths<-get_path_pair(Graph=non_directed, from=origin, to=destination)print(dir_paths)print(non_dir_paths)

Construct graph

Description

Construct graph

Usage

makegraph(  df,  directed = TRUE,  coords = NULL,  aux = NULL,  capacity = NULL,  alpha = NULL,  beta = NULL)

Arguments

Details

'from' and 'to' are character or numeric vector containing nodes IDs.'cost' is a non-negative numeric vector describing the cost (e.g time, distance) between each 'from' and 'to' nodes.coords should not be angles (e.g latitude and longitude), but expressed in a projection system.aux is an additional weight describing each edge. Shortest paths are always computed using 'cost' butaux can be summed over shortest paths.capacity,alpha andbeta are parameters used in the Volume Delay Function (VDF) to equilibrate traffic in the network. Seeassign_traffic.capacity,alpha,beta andaux must have a length equal tonrow(df). If a single value is provided, this value is replicated for each edge.alpha must be different from 0 andalpha must be greater or equal to 1.For more details and examples about traffic assignment, please see the package website :https://github.com/vlarmet/cppRouting/blob/master/README.md

Value

Named list with two useful attributes for the user :

nbnode : total number of vertices
dict$ref : vertices IDs

Examples

#Data describing edges of the graphedges<-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))#Construct directed and undirected graphdirected_graph<-makegraph(edges,directed=TRUE)non_directed<-makegraph(edges,directed=FALSE)#Visualizing directed and undirected graphsif(requireNamespace("igraph",quietly = TRUE)){  plot(igraph::graph_from_data_frame(edges))  plot(igraph::graph_from_data_frame(edges,directed=FALSE))}#Coordinates of each nodescoord<-data.frame(node=c(0,1,2,3,4,5),X=c(2,2,2,0,0,0),Y=c(0,2,2,0,2,4))#Construct graph with coordinatesdirected_graph2<-makegraph(edges, directed=TRUE, coords=coord)

Convert cppRouting graph to data.frame

Description

Convert cppRouting graph to data.frame

Usage

to_df(Graph)

Arguments

Value

Data.frame with from, to and dist column

Examples

#Simple directed graphedges<-data.frame(from=c(1,2,3,4,5,6,7,8),to=c(0,1,2,3,6,7,8,5),dist=c(1,1,1,1,1,1,1,1))#Construct cppRouting graphgraph<-makegraph(edges,directed=TRUE)#Convert cppRouting graph to data.framedf<-to_df(graph)