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.
1 2 3 4 5 6 | .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 |
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 |
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
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.