Virtual Wait Edges and Ground-Hold Modeling

Augment a routing graph with virtual wait self-loops so that ground holds, airborne holds, and downstream-capacity restrictions can be modeled as first-class search choices for A*. Compute total path durations and delay costs, derive the minimum ground hold required to respect a sector-open time, and split a required delay between ground and airborne segments subject to a ground-hold cap.

Step 1 of 157%

Tutorial

Virtual Wait Edges

In a routing graph, spatial edges represent flying from one fix to another. To let the search consider waiting in place, we augment the graph with virtual wait edges: self-loops attached to selected nodes, each carrying a cost equal to one fixed time quantum $\Delta t$ .

For every node $v$ where holding is allowed,

w(v,v)=\Delta t.

Traversing $k$ wait edges at $v$ delays the aircraft by $k\cdot \Delta t$ without changing its location. The total duration of a path that mixes travel and waiting is

T_{\text{path}}=\sum_{i}\tau_i \;+\; \sum_{v} k_v\cdot \Delta t,

where $\tau_i$ are the travel times of the spatial edges traversed and $k_v$ is the number of wait edges taken at node $v$ .

This augmentation lets A* treat ground holds as ordinary edges: the search will lengthen a path by adding wait edges exactly when doing so reduces total cost downstream.

For example, with $\Delta t = 3$ min, a path that traverses a 10-min edge, takes 2 wait edges at the next node, then traverses a 7-min edge has duration

10 + 2\cdot 3 + 7 = 23 \text{ min}.