Time Discretization Choices and Their Trade-Offs

How the choice of time step $\Delta t$ in a time-expanded multi-commodity network controls the trade-off between graph size (memory and solver cost) and temporal accuracy (rounding error on travel times).

Step 1 of 157%

Tutorial

Time Step and the Size of a Time-Expanded Graph

A time-expanded network is built by choosing a time horizon $T$ and a time step $\Delta t$ , then creating one copy of each physical node for every discrete time instant $0, \Delta t, 2\Delta t, \ldots, T$ .

The number of discrete time instants is

N_t = \dfrac{T}{\Delta t} + 1.

If the underlying physical network has $|V|$ nodes, the time-expanded graph has

|V_{TE}| = |V|\cdot N_t = |V|\left(\dfrac{T}{\Delta t}+1\right)

nodes.

Trade-off. A smaller $\Delta t$ produces more time copies, so the graph is larger (more memory, slower to solve) but captures timing more precisely. A larger $\Delta t$ shrinks the graph but loses temporal resolution.

For instance, with $T = 12$ hours and $\Delta t = 2$ hours,

N_t = \dfrac{12}{2}+1 = 7.

With $|V|=4$ physical nodes, the time-expanded graph has $4\cdot 7 = 28$ nodes.