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

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.

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