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}} \newcommand{\tPmax}{\tau(P_{\max})} \newcommand{\tPmin}{\tau(P_{\min})} \newcommand{\tG}{\tau(G)} \newcommand{\Oc}{\mathcal{O}} \)

Termination Time of IDE Flows
in Single Sink Networks

Lukas Graf1, Tobias Harks1, Leon Sering2
1 Augsburg University, 2 Technische Universität Berlin s v t u|_{[0,1]} \equiv 4 (\tau_{sv}, \nu_{sv}) (\tau_{vt}, {\tiny\nu_{vt}}) z_{vt}(\theta)
s v t u|_{[0,1]} \equiv 4

Nash Equilibrium

Every flow particle
  • chooses one source-sink path,
  • such that it is a shortest path in hindsight
  • i.e. takes into account future flow evolution

Instantaneous Dynamic Equilibrium (IDE)

Every flow particle
  • may change its route at every node
  • always chooses a shortest path at the moment
  • i.e. only considers the present state of the network
The current travel time at time \(\theta\) on edge \(e\) is: $c_e(\theta) := \tau_e + z_e(\theta)/\nu_e$
A flow is in Instantaneous Dynamic Equilibrium (IDE) if the following holds:

Whenever flow enters an edge, this edge must lie on a currently shortest path towards the respective sink (w.r.t. \(c\)).

(we call such an edge \(vw\) active)

What is known about IDEs?

Existence

Proof by iteratively extending given IDE flow up to some time $\theta_0$
  • For the multi-source single-sink case:
    (almost) constructive
  • For the multi-source multi-sink case:
    non-constructive using variational inequality

Termination /

  • For one-source two-sink instances:
    Non-Termination possible
  • For multi-source single-sink instances:
    Termination guaranteed
        → but when?
t
t_1 t_2

From now on: Only single-sink instances and all flow particles enter the network before time $\theta = 0$

An Upper Bound for Acyclic Graphs

Any feasible flow in an acyclic network $G$ terminates after at most $\tPmax + U,$
where $\tPmax \coloneqq \max\Set{\sum_{e \in P}\tau_e | P \style{font-family:inherit;font-size:130%;}{\text{ a source-sink path}}}$ and $U \coloneqq$ total network inflow
For any $k = \tPmax, \tPmax -1, \dots, 1, 0$ and any time $\theta$ define $F_{\leq k}(\theta)$ as:

The total volume of all flow particles with maximal distance at most $k$ to $t$ at time $\theta$

Then $F_{\leq k}(\theta) \geq \min\Set{U,\theta-(\tPmax-k)}$
  • $k = \tPmax$: clear
  • $k \to k-1$: w.l.o.g. $F_{\leq k}(\theta) = \min\Set{U,\theta-(\tPmax-k)}$
    $\quad \implies$ flow arrives at rate $1$ at level $k$ $\quad \implies$ no queues form at level $k$
    $\quad \implies F_{\leq k-1}(\theta+1) = \min\Set{U,\theta-(\tPmax-k)}$
k= 5 4 3 2 1 0 P_{\max} t

A Worst-Case Instance

z(\theta) \approx U s t t
Current Termination-time:
$\approx \tPmax + U$
$\approx \tPmin + U$
$\approx \tPmax + U - ?$
$\approx \tPmax + U - (\tPmax-\tPmin)$
$\approx \tPmin + U$
$\approx \tPmin + U + \frac{1}{2}(\tPmax-\tPmin)$
$\approx \tPmax + U$
$\approx \ln(\tPmax) \cdot U$
Goal: Termination-time:             $\tPmax + U$
t t

A General Upper Bound

Any IDE flow in a single-sink network $G$ terminates in $\Oc(U \cdot \tG),$ where $\tG \coloneqq \sum_{e \in E}\tau_e$.
  • In an acyclic network termination is guaranteed (within $\tG + U$)
  • If the total flow volume is $\lt 1$, only physically shortest paths can be active
A subgraph $T \subseteq G$ is called sink-like for some intervall $[a,b]$ if
  • it contains all (physically) shortest $w$-$t$ paths for $w \in T$
  • total flow volume in $T$ at time $a$ $+$ total inflow into $T$ over $[a,b]$ is bounded by $\frac{1}{2}$
t v T
Let $T \subsetneq G$ be sink-like for $[a,b]$,

${\color{red}v} \in G\setminus T$ the closest node to $t$

and $b' \coloneqq b - 2\sum_{e \in \delta(v,T)}\tau_e \geq a$

Then $T \cup \Set{v}$ is sink-like for $[a,b']$

If $T = G$ is sink-like, the IDE flow terminates within $\tG$

$\implies t$ has an inflow of $\geq \frac{1}{2}$ for every intervall $[a, a + 2\sum_{e \in E}\tau_e]$. Otherwise the flow terminates.

Conclusion

The termination time of an IDE flow can be
at least: at most:
for acyclic graphs $\tPmax + U$ $\tPmax + U$
for general graphs $\Omega(U \cdot \ln\tG)$ $\Oc(U \cdot \tG)$

Open Questions

Termination Time of IDE Flows in Single Sink Networks Lukas Graf