Your browser doesn't support the features required by impress.js, so you are presented with a simplified version of this presentation.
For the best experience please use the latest Chrome, Safari or Firefox browser.
\(
\newcommand{\IN}{\mathbb{N}}
\newcommand{\IZ}{\mathbb{Z}}
\newcommand{\IR}{\mathbb{R}}
\newcommand{\IC}{\mathbb{C}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\U}{\mathfrak{U}}
\newcommand{\coloneqq}{:=}
\newcommand{\Set}[1]{\left\{#1\right\}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\Re}{\mathrm{Re}}
\newcommand{\Im}{\mathrm{Im}}
\newcommand{\clos}[1]{\overline{#1}}
\newcommand{\inte}[1]{\mathring{#1}}
\newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)}
\newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)}
\newcommand{\Ind}{\unicode{x1D7D9}}
\)
Dynamic Flows with Adaptive Route Choice
Lukas Graf^{1}, Tobias Harks
^{1}, Leon Sering
^{2}
^{1} Augsburg University, ^{2} Technische Universität Berlin
↑ Discrete Model
(unsplittable flow particles, discrete time steps)
Continuous Model ↓
(infinitesimal flow particles, continuous time)
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)
Questions:
Existence of IDEs?
Termination of IDEs?
↓
Construction of IDEs?
↓
Quality of IDEs?
Existence (SingleSink)
In singlesink 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}\)
Invariant: Flows are piecewise constant, travel times change piecewise linear.
\(\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 (MultiSink)
In multisink networks IDE flows always exist
(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 nodeinflows 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}\) weakstrongcont., \(K\) nonempty, closed, convex, bounded).
This extension proof is nonconstructive!
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 (SingleSink)
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.
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 NPhard (even for acyclic graphs).
Termination (SingleSink)
In singlesink networks \(G\) all IDE flows terminate
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
sinklike for some interval \([a,b]\) if the sum of
 current flow volume within \(H\) and
 the cummulative inflow into \(H\) over \([a,b]\)
is at most \(\frac{1}{2}\).
Let \(v \in G\setminus H\) be closest to \(t\). Then \(H+v\) is sinklike 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 sinklike 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 (MultiSink)
There exists a multisink network where all IDE flows cycle forever.
For IDEs in multisinknetworks the Price of Anarchy is \(\infty\).
Quality (SingleSink)
For singlesink instances with parameters \(U\) and \(\tau_G\) the Price of Anarchy (PoA) is in \(\mathcal{O}(U\tau_G)\).
For singlesink 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!