Time-Dependent Shortest Paths and the FIFO Property

Earliest-arrival shortest paths in time-dependent flight networks. Introduces departure-dependent edge travel-time functions, the FIFO (First-In, First-Out) property and its role in keeping Dijkstra/A* correct, and how to compute earliest-arrival paths when FIFO holds.

Step 1 of 157%

Tutorial

Time-Dependent Edge Costs

In live air routing, the time it takes to fly a leg depends on when you fly it: winds aloft shift, sector congestion fluctuates, and convective cells drift. To model this, each directed edge $e=(u,v)$ carries a travel-time function $\tau_e(t)$ rather than a fixed weight. If you depart $u$ at time $t$ , you arrive at $v$ at time

a_v \;=\; t + \tau_e(t).

We discretize $t$ into 15-minute buckets, so $\tau_e$ is a lookup table indexed by departure bucket $b$ , where bucket $b$ starts at clock time $15b$ minutes past the reference.

Example: edge $\mathrm{KSFO}\to\mathrm{KDEN}$ , travel times in minutes:

\begin{array}{c|cccc} b & 0 & 1 & 2 & 3 \\ \hline \text{window start} & 12{:}00 & 12{:}15 & 12{:}30 & 12{:}45 \\ \tau_e(b) & 145 & 150 & 140 & 135 \end{array}

Departing at the start of bucket $1$ (12:15) gives arrival

12{:}15 + 150\text{ min} = 14{:}45.