Related Terms

acyclic subgraph

An acyclic subgraph is a network without cycles (a cycle is a complete circuit). When following the network from node to node, a node is never visited twice.

backward shortest path

A the shortest path computation that starts at the destination node. This is used when there is a preferred arrival time.

dynamic passenger assignment model

A model that simulates the performance (reliability) and dynamics (capacity constraints, interactions) of a system of passenger demand and scheduled or on-demand transportation services (transit, TNCs, taxis) that run on a physical transportation network.

dynamic transit passenger assignment model

A dynamic passenger assignment model that is designed for scheduled transit service.

forward shortest path

A shortest path computation that starts at the origin node. This is used when there is a preferred departure time.

hyperlink

A hyperlink consists of a set of transit links from a single origin to multiple possible destination nodes [ for forward-shortest-path finding ] or a set of links from a single destination to multiple possible origin nodes [ for backward-shortest-path finding ]. There may be multiple transit departures within a hyperlink.

hyperpath

An acyclic subnetwork with at least one link connecting the origin to the destination, and where at each node, there are probabilities for choosing the alternative links. In most hyperpath-based frameworks, this can be equivalent to the path choice set.

kirchoff model

An alternative formulation to the path-size logit model which considers the relative size of the total utilities of the path. For example, deltas of short paths are perceived differently than deltas on long paths. For paths that are generally the same size, the results will be similar to a logit model formulation.

overlap scale parameter

The parameter in the path-size logit model that scales the impact of the path size term.

passenger assignment

For all unassigned passenger-trips, select a path from the passenger-trip’s pathset based on probabilities calculated from a path-choice model and pathset costs and summarize vehicle loads.

passenger path set generation

The process of initializing the label stop queue, updating, and then finalizing the stop states. The origin or destination state now has a label that has a cost that encapsulates the costs of all the trip links and transfers, but with inaccuracies regarding the timing of the non-transit links, which must be updated using path enumeration.

path choice model

A mathematical model for selecting a path from a set of feasible choices. Examples include the recursive logit model, path-size logit model, Kirchhoff model.

path cost

Path cost or generalized cost is a measure of impedance on a network object. It is typically composed of different variables, each with a fixed weight. Terms may include cost, in-vehicle time, number of transfers, wait time etc.

path enumeration

Walk the labeled hyperpath and generate all of the actual, realizable paths from it. At this point, we can fix the timing of the walk links and therefore have actual wait times. The path costs here are used to calculate the probability of each of these paths. The output of this process is a pathset.

path feasibility check

Flag passenger trips that are not on a valid path due to missed transfers or overcapacity vehicles based on capacity priority rules.

path labeling

The process of initializing the label stop queue, updating, and then finalizing the stop states. The origin or destination state now has a label that has a cost that encapsulates the costs of all the trip links and transfers, but with inaccuracies regarding the timing of the non-transit links, which must be updated using path enumeration.

path overlap variable

An additive measure of similarity between paths. In road-based path-choice models, this is often the distance of the shared links. In passenger-based path-choice models, this could include considerations for shared-routes, similar-routes, on/off stations, traversed stations, traverse distance and more. If the overlap variable is an indicator variable (𝛿), then it can be 1 or 0; if it distance or cost, then it is a continuous variable.

path overlap

In a set of possible paths through a transportation network, some portion of each of the paths may share a facility meaning that each choice in a choice set is not mutually exclusive. This is important in the context of choice modeling, since it violates the “Independence” in the IIA property of a Multinomial Logit. Formulations that compensate for this violation by discounting the “independence” of each path based on a measurement of commonality (the path overlap variable) include the path-size logit model.

path size logit model

A modified logit choice model where the utility equation for a path adds a path size variable to the utility of a path alternative in order to account for overlap between different path options.

pathset update

Update pathset paths based on transit vehicle trajectory cost updates and path feasibility.

stop label

In the context of a shortest path algorithm, stops are labeled with the overall generalized cost of travelling from that stop to the destination (in a forward shortest-path) or from that stop to the origin (in a backwards shortest-path). Stops can be iteratively updated throughout the algorithm.

stop state finalization

When all stops are removed from the label stop queue, the final costs for the destination (in forward-shortest-path) or origin (in backward-shortest-path) is finalized based on the cost labels of the emanating egress or access links.

stop state initialization

The first step of a shortest-path algorithm. Stop labels should be initialized to be greater-than or equal to their final cost and should allow for the greatest number of emanating links (i.e. for a walk access link in a forward-shortest-path, assume it is as early as possible). All stops are added to the label stop queue.

stop state updating

Updating stop states when a stop is removed from the label stop queue.

transit vehicle trajectory update

If the results of the passenger assignment have an effect on transit vehicle timings (i.e. boarding and alighting activity at stop that affect vehicle dwell times), update the transit vehicle trajectories to reflect it.

unassigned passenger pathset generation loop

Passengers with no valid paths in the simulation loop, see if any new paths can be generated based on updated costs and available paths.

Relevant Articles