## 3 Flows over Time
### Storing at Vertices  
The third point in the definition of a flow over time requires flow conservation in every timeslot. A different model allows storing at vertices: a vendor may delay the shipment of goods at his convenience, as long as the flow arrives at the terminal vertices within the time horizon. More formally, we generalize the definition of the _excess_ of vertex \(v\) at time \(\theta\) as the amount of stored goods at vertex \(v\) at time \(\theta\):  
\[\text{ex}_{f}(v,\theta):=\sum_{e\in\delta^{-}(v)}\sum_{\xi\leq\theta-\tau(e)}f _{e}(\xi)-\sum_{e\in\delta^{+}(v)}\sum_{\xi\leq\theta}f_{e}(\xi)\]  
While _strict flow conservation_ requires \(\text{ex}_{f}(v,\theta)=0\) for all non-terminal vertices and times in \(\{0,...,T-1\}\), _weak flow conservation_ allows \(\text{ex}_{f}(v,\theta)\geq 0\), except for time \(T-1\), where \(\text{ex}_{f}(v,T-1)=0\) must hold for all \(v\in V(D)\setminus S\). The time-expanded network can be adapted for weak flow conservation by introducing so-called _holdover edges_, \(v_{i}v_{i+1}\), of infinite capacity for each \(v\in V(D)\) and \(i\in\{0,...,T-2\}\). Setting the ranks of these holdover edges in the preference lists allows the investigation of interesting variations. One intuitive view comes from the fact that storing goods is expensive and people are impatient, thus letting the edges, \(v_{i}v_{i+1}\), be the last on \(v_{i}\)'s preference list and the first on \(v_{i+1}\)'s preference list. In the following, we will investigate the four main cases with weak flow conservation, given by varying first and last preferences on the end vertices of holdover edges. In each case, we study how the sets of stable flows obeying the different flow conservation rules are related to each other. We adapt the definition of a blocking walk for the case of intermediate storing. Apart from a starting time, \(\theta\), we need the exact time, \(\theta_{i}\), when the walk in \(D\) leaves a vertex, \(v_{i}\). A walk in \(D\) together with a sequence, \(\{\theta,\theta_{1},\theta_{2},...,\theta_{k}\}\), uniquely determines a walk on \(D^{T}\). **Example 3.9**. : _Introducing waiting at vertices, stable flows may lose their stability, independent from the rank of holdover edges._  
Proof. : Consider the following example:  
All edges in the static network have unit capacity and unit transit time; \(s\) and \(t\) are the non-terminal vertices. The unobvious preferences are shown on the edges. The time-expanded network with \(T=5\) stands on the right side, showing only the vertices and edges that may be used in a feasible flow. On the static network above, there are three stable flows, each of them uses a different incoming edge of \(z\). If waiting is not allowed, then the dynamic flow shown by the thick edges on the second network is stable, since all unsaturated paths are dominated by it at one end. Adding holdover edges to the time-expanded network breaks the scheme: the walk, \(\{u_{1},w_{2},w_{3},z_{4}\}\) (denoted by dashed lines), blocks the flow over time. Note that this is independent of the rank of the holdover edges, since we only need dominance at the ends of the blocking walk. **Theorem 3.10**. : _If \(T\) is sufficiently large and holdover edges always stand on the first place on preference lists, then there is no stable flow with value zero on all holdover edges._  
Proof. : Suppose there is a stable flow on the time-expanded network that does not use any of the holdover edges. Consider all the copies of an arbitrary non-terminal vertex, \(v\): if there are two of them that have a positive value on some incoming (and outgoing) edges, then holdover edges between them form a walk that blocks the flow. Thus, a stable flow over time passes through an arbitrary non-terminal vertex, at most, once.