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.

adjacent notes

Nodes that are reachable from a node via a single link

arrival time window

A timeframe within which all paths that the passenger considers must arrive at the destination

backward shortest path

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

departure time window

A timeframe within which all paths that passenger considers must depart the origin.

destination

A node that represents a person trip end-point.s

downstream link

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

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)

drive access link

A link that connect a drive access point and an origin via non-transit vehicle. Generally exist for a continuous period of time.

drive access point

A node that represents an access point to transit via driving such as a parking lot or drop-off point.

drive egress link

A link that connect a drive access point and a destination via non-transit vehicle. Generally exist for a continuous period of time.

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 cost

The disutility of a specific hyperpath or portion thereof for a specific user class. Based on both link features, path features, and the path weight parameters.

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.

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.

link feature

A feature that can be accurately represented for an individual link (e.g. in-vehicle-time, wait-time, walk-time). Some features, like fares, can be represented at a link level, but may not be accurate if used without understanding of the entire path due to dependent features such as maximum fares or transfers.

link

a connection between nodes.

node

a specific point in space that represents a feature of the transit network

non-motorized access link

A link that connects a transit stop and a destination via foot or other form of non-motorized travel. Generally exist for a continuous period of time.

non-motorized egress link

A link that connects a transit stop and an origin via foot or other form of non-motorized travel. Generally exist for a continuous period of time.

origin

A node that represents where a person trip starts.

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 feature

Feature of a path that is summarized for the entire path. Can be an aggregation of the link features comprising the path (i.e. wait-time), or a variable that can only be calculated at the level of the entire path (e.g. fare, directness).

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.

pathfinding cost

The cost of each path as calculated during pathfinding, typically including costs of each leg plus some non-additive costs. Because of the non-additive components (e.g. fares) and the adjustment of some components (e.g. travelers may leave their origin later than their preferred time to match their bus departure time), it’s typically computed fully only after the path is fully defined (origin to destination and all legs in between). Differs from the simulation cost in that the travel times may not be accurate because the simulation step hasn’t happened yet which would load passengers onto vehicles, thereby slowing them down for boarding/alighting and possibly bumping passengers.

pathfinding probability

The probability of each path in the pathset based on the pathfinding cost. Differs from simulated probability in that the simulation step hasn’t occurred yet so the probabilities are subject to change; for example, some paths may become infeasible if the simulation fills up some vehicles so the the passenger cannot board the vehicle for this leg. May also include path overlap penalties (although Fast-Trips doesn’t calculate it in Pathfinding, only in Simulation).

joint person tour

A set of paths between an origin and destination with specific costs, waypoints, and timings. In hyperpath-based frameworks this is often derived from the hyperpath.

simulated cost

The cost of each path as calculated during simulation. It differs from the pathfinding cost in that it includes the effect of simulation (loaded vehicles and updated vehicle travel times, crowding costs or costs associated from being bumped from the vehicle).

simulated probability

The probability of each path as calculated during simulation. Like the simulated cost, it differs from the pathfinding probability in that it includes the effect of simulation (loaded vehicles and updated vehicle travel times, crowding costs or costs associated from being bumped from the vehicle, which may make the path infeasible, giving it 0% probability).

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.

stop state

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

stop

A node that represents a transit stop.

transfer link

A link that connects two transit stops or a transit stop and another mode (i.e. a drive access point). Generally exists for a continuous period of time.

transit link

a link that connects two transit stops via a transit service. Generally exists for a specific, discrete time.

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)

user classes

Passenger market segments who use the same parameters (including path weight parameters) to find and assess paths. Common user class segmentations are by travel purpose and captive versus choice users.

Relevant Articles