-->

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{\IRnn}{\IR_{\geq 0}} \newcommand{\IRsp}{\IR_{\gt 0}} \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{\PSet}[1]{2^{#1}} \newcommand{\Mid}{\,\middle|\,} \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}{{\Large\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{\diff}{\mathrm{d}} \newcommand{\eps}{\varepsilon} \newcommand{\ql}[1][e]{Q_{#1}} \)

Dynamic Network Flows
with Adaptive Route Choice
based on Current Information

University of Passau
Lukas Graf

Model

\phantom{(}\tau_e\phantom{,\nu_e)} (\tau_e,\nu_e) s_1 t_2 s_2 t_1 v w \small\color{#3333FF}{0},\color{#FF6666}{\infty} \small\color{#3333FF}{\infty},\color{#FF6666}{0} \small\color{#3333FF}{3},\color{#FF6666}{2} \small\color{#3333FF}{10},\color{#FF6666}{9} \small\color{#3333FF}{8},\color{#FF6666}{12} \small\color{#3333FF}{10},\color{#FF6666}{11} \small\color{#3333FF}{11},\color{#FF6666}{13} u_1 u_2
$\ql(\theta) \coloneqq \int_0^\theta f^+_e(\zeta)\diff\zeta - \int_0^{\theta+\tau_e} f^-_e(\zeta)\diff\zeta$
$f^-_e(\theta+\tau_e) = \begin{cases}\nu_e, &\text{ if } \ql(\theta) \gt 0 \\f^+_e(\theta), &\text{ else}\end{cases}$
$f^-_{e,i}(\theta+\tau_e) = \begin{cases}\frac{f^+_{e,i}(\vartheta)}{f^+_e(\vartheta)}\cdot f^-_e(\theta+\tau_e), &\text{ if } f^+_e(\vartheta) \gt 0 \\0, &\text{ else}\end{cases}$
Vickrey flow
$\phantom{(}f_{e\phantom{,i}}^+\phantom{)} \in L^1(\IRnn)\phantom{^I}$
$(f_{e,i}^+) \in L^1(\IRnn)^I$
$\phantom{(}f_{e\phantom{,i}}^-\phantom{)} \in L^1(\IRnn)\phantom{^I}$
$(f_{e,i}^-) \in L^1(\IRnn)^I$
> \theta \theta
$L_{v,i}(\theta) \coloneqq \inf\Set{C_p(\theta) \Mid p \textsf{ a } v,T_i\textsf{-path}}$
$e=vw$ active for $i$ at $\theta$ if $L_{v,i}(\theta) = C_{vw}(\theta) + L_{w,i}(\theta)$
A Vickrey flow $(f^+,f^-)$ is an Instantaneous Dynamic Equilibrium (IDE) if $f^+_{e,i}(\theta) \gt 0 \implies e$ active for $i$ at time $\theta$.

Existence

Computation

Quality

Let $\mathcal{F}$ be a set of partial IDE $(f,\xi)$ such that
  • $\mathcal{F} \neq \emptyset$
    ⤷ zero flow $(0,0)$
  • $(f_1,\xi_1) \preceq (f_2,\xi_2) \preceq \dots \subseteq \mathcal{F} \implies \exists (f,\xi) \in \mathcal{F}: \forall k: (f_k,\xi_k) \preceq (f,\xi)$
    ⤷ limit flow $\lim_k(f_k,\xi_k)$
  • $(f,\xi) \in \mathcal{F} \implies \exists (g,\xi+\eps) \in \mathcal{F}: (f,\xi) \preceq (g,\xi,+\eps)$
    ⤷ extension-lemma
Then $\mathcal{F}$ contains a complete IDE $(f,\infty)$.

Extension Lemma

Let $(f,\xi)$ be a partial IDE. Then there exists an IDE-extension $(g,\xi+\eps)$, i.e. a partial flow $(g,\xi+\eps)$ such that
  1. $f = g$ up to time $\xi$
  2. $g$ satisfies flow conservation at nodes during $[\xi,\xi+\eps)$
  3. $g$ is a Vickrey flow during $[\xi,\xi+\eps)$
  4. $g^+_{vw,i}(\theta) = 0$ whenever $L^g_{v,i}(\theta) \lt C_{vw}(\theta) + L^g_{v,i}(\theta)$ for $\theta \in [\xi,\xi+\eps)$
easy
hard

Define $K \coloneqq \Set{g \text{ satisfying }\color{green}{\text{(a)}}\text{ and }\color{green}{\text{(b)}}}$     (non-empty, convex, closed, compact)

For $g \in K$ define $\Gamma(g) \coloneqq \Set{h \in K \Mid (g^+,h^-) \text{ satisfies }\color{red}{\text{(c)}}\text{ and } h^+ \text{ satisfies }\color{red}{\text{(d)}}\text{ wrt. } g}$     (non-empty, convex)
mmmmmmmmmmmm and $\Gamma: K \to \PSet{K}$ has closed graph

Get $g \in K$ with $g \in \Gamma(g)$ from fixpoint theorem. This is an IDE-extension.

IDE exist.
  • Right-constant flow rates and $\eps$ small $\implies$ finite-dimensional problem
  • $\eps \leq \tau_e \implies$ (c) becomes irrelevant
  • Partition of network $\implies$ subdivide (d) into smaller subproblems
s_1 s_2 t_2 t_1
Input: Single-commodity network with right-constant inflow and $\tau_e \gt 0$
Output: IDE $(f,\infty)$ with right-constant flow rates
(1) Start with $(f,\xi) \leftarrow (0,0)$
(2) Until all flow has reached a sink Repeat
(3) .. Find extension $(g,\xi+\eps)$ of $(f,\xi)$
(4) .. Set $(f,\xi) \leftarrow (g,\xi+\eps)$
  1. Can we compute a single extension?
  2. Can we reach any finite time horizon in finitely many extensions?
  3. Do IDE terminate within a finite time horizon?

Number of Extensions

Lower bound on length of extension intervals?
Extension intervals become arbitrarily small!
For single-commodity and right-constant flows:
A finite number of extensions suffices to reach any finite time horizon.
\theta \small 2 u_s \theta \small 3 \queue_{vt} \theta \small 2 \queue_{wx} s v w x t
Makespan($f$) $\coloneqq$ arrival time of last particle / first time with empty network

Upper Bound for Single-Commodity

In an acyclic network the makespan of any IDE is at most $\hat\theta + \tau_{P_\max} + \frac{U}{\nu_\min}$.
t
In a general network the makespan of any IDE is at most $\hat\theta + 3U\tau(G) + \dots$.

Lower Bound for Multi-Commodity

t_2 t_1
There exists a multi-commodity network where no IDE ever terminates.
s_1 t_1
s_2 s_2 s_2
Let $\mathcal{F}$ be a set of partial IDE $(f,\xi)$ such that
  • $\mathcal{F} \neq \emptyset$
    ⤷ zero flow $(0,0)$
  • $(f_1,\xi_1) \preceq (f_2,\xi_2) \preceq \dots \subseteq \mathcal{F} \implies \exists (f,\xi) \in \mathcal{F}: \forall k: (f_k,\xi_k) \preceq (f,\xi)$
    ⤷ limit flow $\lim_k(f_k,\xi_k)$
  • $(f,\xi) \in \mathcal{F} \implies \exists (g,\xi+\eps) \in \mathcal{F}: (f,\xi) \preceq (g,\xi,+\eps)$
    ⤷ extension-lemma
Then $\mathcal{F}$ contains a complete IDE $(f,\infty)$.
Input: Single-commodity network with right-constant inflow and $\tau_e \gt 0$
Output: IDE $(f,\infty)$ with right-constant flow rates
(1) Start with $(f,\xi) \leftarrow (0,0)$
(2) Until all flow has reached a sink Repeat
(3) .. Extend $(f,\xi)$ to $(f,\xi+\eps)$
  1. We can compute a single extension in polynomial time
  2. We can reach any finite time horizon in finitely many extensions

...+ computing extensions, finitely many extensions, NP-Hardness
Makespan in single-commodity at most $\hat\theta+2U\tau(G)$
t
There exist multi-commodity networks where no IDE terminates.
s_1 ...+ SC lower bound

Bounding the Number of Extensions

Let $v$ be a node with constant inflow and linear node labels at all nodes closer to the sink (during $[\xi,\xi+\eps)$).
Then only finitely many extensions are necessary at $v$.
$h_i: [\xi,\xi+\eps) \to \IRnn, \theta \mapsto C_{vw_i}(\theta) + L_{w_i}(\theta)$
v w_1 w_2 w_3 w_4 f^-_e L_{w_1} L_{w_2} L_{w_3} L_{w_4}

For $K,L \in \INs$ construct $G_{K,L}$ with $U \in \bigO(L3^K), \tau(G_{K,L}) \in \bigO(3^{2K})$:

s s t C_K B_K
In $G_{K,L}$ there exists an IDE flow which terminates after $LK(3^K+1)$.
Dynamic Network Flows with Adaptive Route Choice based on Current Information Lukas Graf
Dynamic Network Flows with Adaptive Route Choice based on Current Information - Model Lukas Graf
Dynamic Network Flows with Adaptive Route Choice based on Current Information - Existence Lukas Graf
Dynamic Network Flows with Adaptive Route Choice based on Current Information - Computation Lukas Graf
Dynamic Network Flows with Adaptive Route Choice based on Current Information - Quality Lukas Graf