shortest.paths: Low-Level Functions for Shortest Path Manipulation
In travelr: Functions for Travel Demand Modeling

Description Usage Arguments Details Value Author(s) See Also

These functions construct and manipulate shortest paths based on highway networks. They are intended for use in building higher-level algorithms.

.shortest.paths(network.set, costs,penalties=NULL)
.load.paths(paths, demand)
.build.and.load.paths(network.set, costs,demand,penalties=NULL)
.skim.paths(paths, costs, empty.value = 0)
.intercept.paths(paths, links)
.walk.paths(paths, origins, dests, permute=TRUE)

`network.set`	Network descriptor (generated by `build.network.set`)
`demand`	A matrix of demands between each origin/destination pair
`costs`	A vector of costs for each link in the network
`penalties`	A vector of penalty values for each turn penalty in the network
`paths`	A shortest-path tree for a particular network
`empty.value`	The value to be used for origin/destination pairs that have no path, and also for intrazonal (diagonal) cells
`links`	A vector selecting links of interest in the network; the intercept matrix will contain true for any origin/destination pair whose shortest path crosses one of these links.
`origins`	A vector of origin zones
`dests`	A vector of destination zones
`permute`	If true, returns paths for all combinations of `origins` and `dests`; otherwise, `origins` and `dests` must be vectors of the same length and paths will only be built for each corresponding origin and destination

These functions are thin wrappers to C++ code called via the .Call interface.

The C++ code builds shortest paths using Dijkstra's algorithm with a priority queue and integrated support for turn (junction) penalties and prohibitions. The algorithm respects the usual routing convention of highway networks that treates the origins and destinations of interest as "terminal" nodes. Routes are only allowed to leave one of those nodes (the current origin) at a time, and paths are built only to the other terminal nodes. The resulting path tree contains paths from all origins to all destinations. However, these paths span only the terminal nodes, so there may be intermediate nodes for which a path does not exist for certain origins.

The resulting path tree structure (an R matrix) can be used with the other functions to perform operations on vectors of values corresponding to the links, and on matrices whose dimensions correspond to the number of zones (terminal nodes) in the network, and whose values are associated with the paths from origins to destinations.

Such vectors of values are often referred to in this documentation as link vectors, since they will contain a set of values corresponding to the links in the highway network (and, importantly, in the same order in which the highway network links were originally presented, corresponding to order(network$Links$.LinkID)).

Likewise, the matrices passed to and from these functions are often referred to either as demand matrices or trip tables when they are used for loading the network, and as skim matrices when they are returned.

Conventionally in travel demand modeling, the matrices have origins as their rows (first dimension), and destinations as their columns (second dimension). This convention dates back to the original implementation of these models in FORTRAN, when limited memory in early computers was handled by processing the matrices one origin at a time. R, however, is set up to most efficiently process matrices one column at a time (the C convention for multi-dimensional arrays). None of that will matter to travelr users since the gnarly details (along with the C 0-base versus R 1-base array index problem) are handled automatically by these wrapper functions.

In general, it is usually more useful to perform these operations through even higher-level functions which handle multi-class assignment and “select link” analysis: build.paths, load.paths, build.and.load.paths, intercept.paths.

The higher-level functions require an assignment.set to manage the various parameters.

.shortest.paths returns a shortest path tree (a species of matrix)

.load.paths returns a numeric vector of loaded network link values constructed from the demand matrix

.build.and.load.paths returns a list with elements volumes and paths comparable to what would result by calling .shortest.paths followed by .load.paths

.skim.paths returns a matrix that results from applying FUN to a vector of link values for each path

.intercept.paths returns a matrix of of 0 or 1 indicating whether a path includes a marked link

.walk.paths returns a list (or a matrix, if the permute option is TRUE) of vectors of link indices (integers) showing the links traversed on the requested paths

Jeremy Raw

build.network.set, assignment.set, highway.assign for general operations.

And the higher level interfaces: build.paths, load.paths, build.and.load.paths, and intercept.paths

travelr documentation built on May 2, 2019, 5:17 p.m.