Dynamic Flows with Adaptive Route Choice
Lukas Graf1, Tobias Harks1, Leon Sering2
1 Augsburg University, 2 Technische Universität Berlin
Goal
↑ Discrete Model
(unsplittable flow particles, discrete time steps)
Physical Model
- Directed (Multi-)Graph \(G = (V,E)\)
- For all edges \(e \in E\): length \(\tau_e \in \IN\) and capacity \(\nu_e\)
- Commodities \(I\) with source node \(s_i\), sink node \(t_i\)
and constant inflow rate \(u_i: [a_i,b_i] \to \IR_{\geq 0}\) - Inflow \(\gt\) capacity \(\implies\) queues form
\(f_e^+(\theta) \gt \nu_e\) (length \(q_e(\theta)\))
\(s_1\)
\(u_1 = \Ind_{[0,1]}\)
\(v_2\)
\(v_1\)
\(v_3\)
\(s_2\)
\(u_2 = 3\cdot\Ind_{[0,1]}\)
\(t_{{\color{blue}1}/{\color{red}2}}\)
\((\tau_e, \nu_e)\)
\(f_e^+(\theta)=3\)
\(q_e(\theta) = 2\)
\(q_e(\theta) = 1\)
\(c_e(\theta)=1 + \frac{2}{1}\)
\(c_e(\theta)=1 + \frac{1}{1}\)
Behavioral Model
The current travel time at time \(\theta\) on edge \(e\) is: \[c_e(\theta) := \tau_e + q_e(\theta)/\nu_e\]
A flow is in Instantaneous Dynamic Equilibrium (IDE) if the following holds:
Whenever positive flow enters an edge, this edge must lie on a currently shortest path towards the respective sink (w.r.t. \(c\)).
\[f^+_{vw}(\theta) > 0 \implies \dist{v,t}{\theta} = c_{vw}(\theta) + \dist{w,t}{\theta}\]
(we call such an edge \(vw\) active)
Existence (Single-Sink)
In single-sink networks IDE flows always exist
-
Given an IDE flow \(f\) up to some time \(\theta\),
extend \(f\) up to some time \(\theta+\varepsilon\). - Calculate node inflows at time \(\theta\).
- Order nodes by their distance to sink \(t\).
-
Distribute node inflow to active edges such that:
\(f_{vw}^+(\theta) > 0 \implies \dists{v,t}{\theta} = c_{vw}'(\theta) + \dists{w,t}{\theta}\)
\(f_{vw}^+(\theta) = 0 \implies \dists{v,t}{\theta} \geq c_{vw}'(\theta) + \dists{w,t}{\theta}\)
\(\implies\) Distribution stays valid for some \(\varepsilon > 0\)
Extend flow for all times using Zorn's Lemma
\(s\)
\(u = 3\cdot \Ind_{[0,3]}\)
\(v\)
\(w\)
\(x\)
\(y\)
\(t\)
Existence (Multi-Sink)
In multi-sink networks IDE flows always exist
(even for more general inflow rate functions \(u_i\)).
(even for more general inflow rate functions \(u_i\)).
- Given an IDE flow \(f\) up to some time \(\theta_0\), extend \(f\) up to some time \(\theta_0+\varepsilon\).
- Calculate the node-inflows at time \(\theta_0\).
- Order nodes by their distance to sink \(t\).
- Let \(K := \{g\,|\,g\) extension of \(f\) on \([\theta_0, \theta_0+\tau_{\min})\) (not necessarily IDE)\(\}\).
- Consider the mapping \(\mathcal{A}: K \to L^2([\theta_0,\theta_0+\tau_{\min}))^{I \times E}, g=(g_{i,e}) \mapsto h = (h_{i,e}),\)
where \(h_{i,vw}(\theta) := \dist{w,t_i}{\theta} + c_{vw}(\theta) - \dist{v,t_i}{\theta}\) \(= 0 \iff vw\) is active
\(v\)
\(w\)
\(t_i\)
Then: \(g \in K\) is IDE extension \(\iff \langle g, \mathcal{A}(g)\rangle = 0\) \(\iff \langle \mathcal{A}(g),g'-g\rangle \geq 0\) f.a. \(g' \in K\)
- Such a \(g\) always exists (\(\mathcal{A}\) weak-strong-cont., \(K\) non-empty, closed, convex, bounded).
This extension proof is non-constructive!
However, there is also an constructive extension proof using MIP
However, solving an MIP is hard!
However, there is also an constructive extension proof using MIP
However, solving an MIP is hard!
\(s_1\)
\(s_2\)
\(t_2\)
\(t_1\)
Construction (Single-Sink)
A distribution of the node inflow to active edges satisfying
\(f_{vw}^+(\theta) > 0 \implies \dists{v,t}{\theta} = c_{vw}'(\theta) + \dists{w,t}{\theta}\)
\(f_{vw}^+(\theta) = 0 \implies \dists{v,t}{\theta} \geq c_{vw}'(\theta) + \dists{w,t}{\theta}\)
can be found in polynomial time.
\(f_{vw}^+(\theta) > 0 \implies \dists{v,t}{\theta} = c_{vw}'(\theta) + \dists{w,t}{\theta}\)
\(f_{vw}^+(\theta) = 0 \implies \dists{v,t}{\theta} \geq c_{vw}'(\theta) + \dists{w,t}{\theta}\)
can be found in polynomial time.
Define \(h_{vw}\big(f_{vw}^+(\theta)\big) := c'_{vw}(\theta) + \dists{w,t}{\theta}\).
For acyclic graphs the above algorithm computes an IDE with a finite number of phases within \([0,T]\) for every time horizon \(T \geq 0\).
Computing an IDE flow is NP-hard (even for acyclic graphs).
Termination (Single-Sink)
In single-sink networks \(G\) all IDE flows terminate
within at most \(4U\tau_G\).
within at most \(4U\tau_G\).
In an acyclic graph the termination time is \(\tau_{\max}+U\).
Without queues the active edges form a static acyclic graph.
With only small queues the active edges form a static acyclic graph.
A subgraph \(H \subseteq G\) containing the sink \(t\) as well as all its shortest paths towards the sink
is sink-like for some interval \([a,b]\) if the sum of
Let \(v \in G\setminus H\) be closest to \(t\). Then \(H+v\) is sink-like for \(\left[a,b-\sum_{e \text{ edge between } v \text{ and } H}(\tau_e + \frac{1}{\nu_e})\right]\).
\(\implies\) If \(H := \{t\}\) is sink-like for \(\tau_G+|E|\), the flow terminates.
\(\implies\) The sink has inflow of at least \(\frac{1}{2}\) all \(2\tau_G\) time steps.
is sink-like for some interval \([a,b]\) if the sum of
- current flow volume within \(H\) and
- the cummulative inflow into \(H\) over \([a,b]\)
Let \(v \in G\setminus H\) be closest to \(t\). Then \(H+v\) is sink-like for \(\left[a,b-\sum_{e \text{ edge between } v \text{ and } H}(\tau_e + \frac{1}{\nu_e})\right]\).
\(\implies\) If \(H := \{t\}\) is sink-like for \(\tau_G+|E|\), the flow terminates.
\(\implies\) The sink has inflow of at least \(\frac{1}{2}\) all \(2\tau_G\) time steps.
\(s_1\)
\(v_2\)
\(v_1\)
\(s_3\)
\(s_2\)
\(t\)
Termination (Multi-Sink)
There exists a multi-sink network where all IDE flows cycle forever.
For IDEs in multi-sink-networks the Price of Anarchy is \(\infty\).
\(s_1\)
\(t_1\)
\(s\)
\(s\)
\(s\)
Quality (Single-Sink)
For single-sink instances with parameters \(U\) and \(\tau_G\) the Price of Anarchy (PoA) is in \(\mathcal{O}(U\tau_G)\).
For single-sink instances with parameters \(U\) and \(\tau_G\) the Price of Anarchy (PoA) is in \(\Omega(U\log\tau_G)\).
Close the gap between the bounds for the PoA!
Connection?
