Time-Expanded Network Flow

The time-expanded network (also called the time-space network) is the workhorse data structure for fleet routing. It bakes both location and time into the graph itself, so that standard network-flow algorithms can solve scheduling problems.

For each station $s$ in the route system and each 15-minute time bucket $t$ in the planning horizon, the network contains a time-space node $(s,t)$. Each scheduled flight is encoded as a flight arc

$$(s_1,\, t_d) \longrightarrow (s_2,\, t_a),$$

where $t_d$ is the departure bucket at the origin $s_1$ and $t_a$ is the arrival bucket at the destination $s_2$. The arrival bucket is the departure bucket plus the block time plus the minimum turnaround buffer, all measured in 15-minute buckets:

$$t_a = t_d + (\text{block buckets}) + (\text{turn buckets}).$$

The flow on a flight arc is the number of aircraft assigned to operate that flight (typically $1$ in a single-fleet model).

For example, a flight departing JFK at $09\!:\!00$ with $2\text{h }30\text{m}$ block time and a $30$-minute turnaround buffer arrives at MIA. Since $09\!:\!00$ corresponds to bucket $36$, block time is $10$ buckets, and turn is $2$ buckets, the flight arc is

$$(\text{JFK},\, 36) \longrightarrow (\text{MIA},\, 36 + 10 + 2) = (\text{MIA},\, 48).$$