Related Terms

backward shortest path

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

downstream node

A node that is reachable from a node (forward shortest-path) or a node that can reach the current node (backward shortest path)

emanating link

Links coming into or going out of a node.

forward shortest path

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

departure time window

The ordered queue that contains stops with stop states that need to have their costs updated in order to find the shortest path. Stops are processed in order of cost, with least cost stops processed first.

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.

passenger simulation

Probabilistic assignment of passengers to paths in their pathset based on costs. Update of pathset feasibility.

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.

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

stop state

The combination of a stop label (l) and upstream (forward shortest-path) or downstream (backward shortest-path) links (Pa).

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.

upstream link

A link that is reachable from a node (backward shortest-path) or a link that can reach the current node (forward shortest path)

upstream node

A node that is reachable from a node (backward shortest-path) or a node that can reach the current node (forward shortest path)

Relevant Articles