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{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \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}{{\small\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \newcommand{\CharF}[1]{\Ind_{#1}} \)

Dynamic Network Flows with Adaptive Route Choice

Lukas Graf, Tobias Harks, Leon Sering
s_1 v_1 s_2 v_2 v_3 t_{1/2}

↑ Discrete Model

(atomic flow particles, discrete time steps)

Continuous Model ↓

(infinitesimal flow particles, continuous time)

(1,1) \color{DodgerBlue}{q_e(\theta)=2} \color{DodgerBlue}{q_e(\theta)=1} s_1 s_\color{#FF441F}{1} v_1 s_2 s_\color{DodgerBlue}{2} v_2 v_3 t_{1/2} t_{\color{#FF441F}{1}/\color{DodgerBlue}{2}} \color{#FF441F}{\CharF{[0,1]}} \color{DodgerBlue}{3\cdot\CharF{[0,1]}}

Physical Model

  • Directed graph \(G = (V,E)\)
  • For \(e \in E\): free flow travel time \(\tau_e \in \IR_{\geq 0}\) and service rate \(\nu_e \in \IR_{\geq 0}\)
  • Commodities \(I\) with source node \(s_i\), sink node \(t_i\)
    and network inflow rate \(u_i: \IR_{\geq 0} \to \IR_{\geq 0}\)
  • (Edge)flow $(f_{e,i}^+,f_{e,i}^-) \in L^1(\IR_{\geq 0},\IR_{\geq 0})^2$
  • Inflow \(\gt\) service rate \(\implies\) queues form
      \(f_e^+(\theta) \gt \nu_e\)                             (length \(q_e(\theta)\))

Behavioral Model

  • Current travel time $c_e(\theta) \coloneqq \tau_e + q_e(\theta)/\nu_e$
  • Current distance $\ell_{v,i}(\theta) \coloneqq \min\Set{c_e(\theta)+\ell_{w,i}(\theta) \mid e=vw}$
A flow is in Instantaneous Dynamic Equilibrium (IDE) if
\[f^+_{e,i}(\theta) \gt 0 \implies \ell_{v,i}(\theta) = c_e(\theta) + \ell_{w,i}(\theta)\] for all $e=vw \in E$, $i \in I$ and almost all $\theta \in \IR_{\geq0}$

Results:

Partial IDE can always be extended for some $\alpha \gt 0$
Via...
  • Variational inequality
  • Fixed point theorem
  • Convex optimization
For single-commodity and piecewise constant flow rates:
Finitely many extensions suffice...
...and any extension can be computed in poly time
IDE related decision problems are NP-hard.
Single-commodity: PoA $\in \Omega(U\log \tau) \cap \bigO(U\tau)$
Multi-commodity: Flow may cycle forever

Potential Directions for Future Research:

Dynamic Flows with Adaptive Route Choice Lukas Graf
Dynamic Flows with Adaptive Route Choice - Model Lukas Graf
Dynamic Flows with Adaptive Route Choice - Results Lukas Graf
Dynamic Flows with Adaptive Route Choice - Future Research Lukas Graf