highway.assign: Perform highway assignment using a variety of methods
In travelr: Functions for Travel Demand Modeling

Description Usage Arguments Details Value Author(s) References See Also

Perform highway assignment using a variety of methods such as All-or-Nothing (AON), Multiple Successive Averages (MSA), or equilibrium approaches such as the Frank-Wolfe linearized convex solution strategy, and the ParTan variation. Can be extended with user-supplied algorithms.

1	highway.assign(aset, method = c("AON", "MSA", "Frank.Wolfe", "ParTan" ), control=vector("list",0))

`aset`	An `assignment set` whose classes will be assigned.
`method`	A character string specifying the assignment method, which may be one of “AON”, “MSA”, “Frank.Wolfe” or “ParTan”; if no method is specified, then “AON” will be selected. Alternatively, the method may select a user-defined assignment algorithm; see details.
`control`	List of parameters for the assignment; varies by method, see details

The highway.assign function performs a traffic assignment using the network and demand data specified in its first argument, which is an assignment.set. The assignment method is chosen using the method argument, which may refer to user-defined methods as described below. The control argument is a list of values that set values for convergence criteria and adjust the behavior of the algorithm in various ways. Valid control elements for the built-in algorithms are described below.

Most of the highway assignment algorithms reflect descriptions provided in Sheffi (1985). ParTan is described in Lee and Nie, 2001.

Overview of Built-In Algorithms

The method specifies the algorithm to be used for the traffic assignment. Four common assignment algorithms are built in:

AON

“All-or-Nothing” assignment. The algorithm builds shortest paths fromthe free-flow speeds defined for the assignment set, and loads all the demand onto those paths without considering capacity limits. The steps are these:

Build paths
Load Traffic
Stop

MSA

“Multiple Successive Averages” does a simple form of capacity restraint by averaging the volumes from successive AON assignments where the next assignment uses the costs from the average volumes from all the previous assignment volumes. The steps are these:

Build paths using costs from average link volumes (initially free-flow)

Load Traffic

Compute the new average volume and the associated link costs

If maximum number of iterations is reached, stop, otherwise return to step 1.

Frank.Wolfe

Computes an equilibrium assignment using the simple, low-resource, but slowly converging Frank-Wolfe algorithm. This is a widely used method in travel demand modeling, but it is gradually becomign obsolete due to advances in computing capacity and the desire to achieve faster convergence to a narrower tolerance. (The TravelR project exists in part to help explore practical implementations of alternative algorithms.) The steps are these:

Build paths using costs from current equilibrium link volumes (initially free-flow)

Load Traffic

Compute the combination of equilibrium volume and shortest path volume that minimizes the objective function

Update the equilibrium volume to the combined value

Recompute link costs from equilibrium flow

If convergence target is met, stop, otherwise return to step 1.

ParTan

The “Parallel-Tangent” algorithm extends the Frank-Wolfe approach by rectifying the search direction using a previous search direction. This algorithm converges somewhat faster than the basic Frank-Wolfe method. There is an additional line search for the second and subsequent iterations that finds the lowest cost combination of the previous equilibrium volumes and the current combined volume from a standard Frank-Wolfe step. The steps are these:

Build paths using costs from current equilibrium link volumes (initially free-flow)

Load Traffic

Compute the combination of equilibrium volume and shortest path volume that minimizes the objective function

Compute the combination of the new combined value and the equilibrium result at the start of the previous iteration that minimizes the objective function

Save the current equilibrium volume for a later iteration

Update the equlibrium volume with the final combined volume

Recompute link costs from the new equilibrium flow

If convergence target is met, stop, otherwise return to step 1.

Additional algorithms can be implemented in specially named functions provided by the user, through a mechanism similar to (but less sophisticated than) R's S3 methods. The supplied method name is prefixed by “highway.assignment.” and a function by that name is sought in the calling environment of the function. The internal methods are named differently and are sought only when the search for user-defined functions fails. It is thus possible to supply an alternate implementation for one of the internal methods by providing a function with a suitable name (e.g. highway.assignment.Frank.Wolfe)

The function that implements an assignment algorithm will be passed the aset and control parameters, and should return a list of values, with elements comparable to those returned by the standard algorithms. An element called method will be concatenated to the list returned from the algorithm function.

Control Parameters

The control argument is a list of optional parameters that alter the behavior of the assignment algorithms in various ways. The sets of elements relevant to each built-in algorithm are described first, and a description of each follows.

All Methods: intercept (see below), log, verbose
AON: No additional parameters
MSA: max.iter
Frank.Wolfe: max.iter, min.relative.gap, max.elapsed, opt.tol
ParTan: max.iter, min.relative.gap, max.elapsed, opt.tol

`intercept`	If this value is an `intercept.set`, then do select link processing (not set by default); see below
`verbose`	If greater than 0, add additional messages (higher numbers imply more, but all the functions are currently quite terse; default is `1`
`log`	If `TRUE`, return results of each iteration in a `data.frame`; defaults to `FALSE`
`max.iter`	Maximum number of iterations before stopping (defaults to `4` for MSA, and `100` for other algorithms
`min.relative.gap`	Equilibrium algorithms will stop if `relative.gap` statistic drops below this value (default `1e-4`)
`max.elapsed`	Maximum allowable run-time in seconds (default `3600`)
`opt.tol`	Tolerance for line search optimization (default `.Machine$double.eps^0.5`)

Select Link Processing

Travel modelers often seek information on which specific links are assigned demand for particular zone pairs. The select link results are reported either as a matrix of demand from origin to destination that passes through one of the selected links, or as a vector of volumes tha results when the selected demand matrix is assigned.

Internally, select link processing identifies links of interest, constructs a subset of the matrix of the demand matrix that only includes origins and destinations, and assigns that demand to the network. Currently, select link processing applies to all assignment classes, and the selected demand and link volumes for each class are maintained separately. Naturally, one is rarely interested in flows that follow a single path (say the shortest path). Consequently, within the assignment algorithms when an intercept is specified, the intercepts and demands are computed at each iteration, and the results are combined using the same factors used for the total equilibrium flow. Thus, the intercepts will include a portion of traffic due to rarely used alternate paths that may intercept a link of interest.

Needless to say, processing select link intercepts on a large network, or through many iterations, will be substantially slower than simply computing a total equilibrium assignment.

See intercept.set for details about setting up a select link analysis.

Returns a list with various elements. The possible elements are enumerated in the following table, which shows the element name and description. Certain elements are only returned if suitable control values are provided, and they are so indicated.

aset	the assignment set which was assigned (identical to the `aset` argument
costs	a `data.frame` with one column per assignment class and one row per link
paths	the shortest path tree for the final assignment iteration resulting from the final costs
volumes	a `data.frame` of volumes, with one column per assignment class and one row per link
iset	the `control` argument describing the intercept (only present if it was supplied)
intercept	A list of two elements: `od` a list of intercepted demand matrices, one for each class, and `volumes` a data frame with one column per class of intercepted volumes (only present if an intercept set was supplied in the `control` argument)
results	`data.frame` of one row with the assignment statistics from the final iteration
log	`data.frame` with assignment statistics from all iterations
method	the `method` selected either as an argument or by default

Jeremy Raw

Lee, D.-H., and Nie, Y. “Accelerating Strategies and Computational Studies of the Frank-Wolfe Algorithm for the Traffic Assignment Problem”, 2001, Transportation Resarch Record, 1771:97-105. Sheffi, Y., 1985, Urban Transportation Networks, Prentice-Hall; available online as a PDF at http://web.mit.edu/sheffi/www/urbanTransportation.html

assignment.class, assignment.set, assignment.functions for setting up highway assignments;

parse.control for interpreting assignment algorithm control values and defaults;

intercept.set and build.intercepts for details on setting up select link analysis

For a short complete example of a travel model: example{skim.paths}

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