Tracing Cargo Through a Time-Expanded Multi-Commodity Network

A time-expanded multi-commodity network represents each physical location $i$ at each discrete time step $t = 0, 1, \dots, T$ as a separate node $(i, t)$. Two kinds of arcs connect these time-stamped nodes:

• Transit arcs $(i, t) \to (j, t + \tau_{ij})$ representing physical movement from $i$ to $j$ taking $\tau_{ij}$ time units.
• Holdover arcs $(i, t) \to (i, t + 1)$ representing cargo waiting at location $i$ from time $t$ to time $t + 1$.

When several commodities share the network, each arc $a$ carries a separate flow variable $x_a^k \geq 0$ for each commodity $k$. The total flow on arc $a$ is $\sum_k x_a^k$, but each commodity's behavior is captured by its own variables.

To trace commodity $k$, we examine only the arc flows $\{x_a^k\}$ and discard the flows of other commodities. The arcs with $x_a^k > 0$ are exactly the arcs along which units of commodity $k$ travel.

For example, on the arc $a = ((A,0),(B,1))$, suppose $x_a^1 = 4$ and $x_a^2 = 2$. Then $4$ units of commodity $1$ and $2$ units of commodity $2$ both move from $A$ to $B$ during that time step. To trace commodity $1$, we record $x_a^1 = 4$ and ignore the value $2$.