Constructing a Time-Expanded Network

Builds the time-expanded representation of a static graph by replicating each node across discrete time steps, adding travel arcs that respect edge travel times, and adding holdover arcs for waiting. Establishes counting formulas for node copies, travel arcs per edge, holdover arcs, and the total arc count of the time-expanded network.

Step 1 of 157%

Tutorial

Node Copies

A time-expanded network unfolds a static graph $G = (V, E)$ over a discrete time horizon $T$ by making time an explicit dimension of the node set.

For every node $v \in V$ and every time step $t \in \{0, 1, \dots, T\}$ , we create a node copy $v_t$ , representing 'being at vertex $v$ at time $t$ .' The node set of the time-expanded network is

V' = \{v_t : v \in V,\ t = 0, 1, \dots, T\},

and its size is

|V'| = |V| \cdot (T+1).

The factor of $T+1$ comes from including both endpoints $t = 0$ and $t = T$ .

For example, if $V = \{A, B, C\}$ and $T = 2$ , then $V'$ contains $3 \cdot 3 = 9$ nodes:

A_0,\ A_1,\ A_2,\ B_0,\ B_1,\ B_2,\ C_0,\ C_1,\ C_2.