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{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\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}} \)

Dynamic Flows
with Adaptive Route Choice

Tobias Harks and Lukas Graf
Universität Augsburg
February 15, 2019

Dynamic Flows
with Adaptive Route Choice

Tobias Harks and Lukas Graf
Universität Augsburg
February 15, 2019
Augsburg
Potsdam
Amsterdam

The Physical Flow Model

  • Digraph \(G = (V,E)\)
  • Edge \(e \in E\) has length \(\tau_e \in \Z_+\) and capacity \(\nu_e \in \Z_+\)
  • Commodities \(i \in I\) with source \(s_i \in V\) and sink \(t_i \in V\) and constant inflow rate \(u_i: [r_i,R_i] \to \R_+\)
  • Inflow \(>\) Capacity \(\Rightarrow\) Queue forms (with length \(q_e\))
Augsburg
Potsdam
Amsterdam
\(s\)
\(t\)
\(s'\)
\(\tau_e = 1\)
\(\nu_e = 2\)
\(\tau_e = 1\)
\(\nu_e = 3\)
\(\tau_e = 2\)
\(\nu_e = 4\)
\(s\)
\(t\)
\(2\)
\(1\)
\(0\)
\(u_1\)
\(s'\)
\(t\)
\(3\)
\(1\)
\(2\)
\(u_2\)
\(q_e(2) = 1\)

The Behavioral Model

We define the current travel time at time \(\theta\) on edge \(e\) by: \[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\)).
(we call such an edge active)

\(s\)
\(t\)
\(s'\)
\(\tau_e = 1\)
\(\nu_e = 2\)
\(\tau_e = 1\)
\(\nu_e = 3\)
\(\tau_e = 2\)
\(\nu_e = 4\)
\(q_e(\theta) = 1\)
\(q_e(\theta) = 2\)

        Questions:

Existence?Termination?
For any given network: Does an IDE flow exist?Do all IDE flows terminate? I.e. does all flow volume reach a sink in finite time?
single
sink
multi-
sink
\(s\)
\(t\)
\(s'\)
\(\tau_e = 1\)
\(\nu_e = 2\)
\(\tau_e = 1\)
\(\nu_e = 3\)
\(\tau_e = 2\)
\(\nu_e = 4\)
\(q_e(\theta) = 2\)

Existence (Single Sink)

For any multi-source single-sink network \(G\)
there exists an IDE flow.

Given:An IDE flow \(f\) up to some time \(\theta\)
Goal:Extending \(f\) up to some time \(\theta + \varepsilon\), i.e. for every \(v \in V\)
distribute inflow onto active edges at \(\theta\)
such that they remain active on \([\theta,\theta+\varepsilon)\) for some \(\varepsilon >0\)
Idea:Order nodes by increasing distance to the sink \(t\)
Distribute inflow node by node using a suitable Optimization Problem
\(s\)
\(t\)
\(s'\)
\(\tau_e = 1\)
\(\nu_e = 2\)
\(\tau_e = 1\)
\(\nu_e = 3\)
\(\tau_e = 2\)
\(\nu_e = 4\)
\(q_e(\theta) = 2\)
\(q_e(\theta) = 1\)
\(q_e(\theta) = 3\)
\(q_e(\theta) = 6\)

Termination (Single Sink)

For any multi-source single-sink network \(G\)
all IDE flows terminate.

1) The sink can never be part of a cycle
2) The total amount of flow in the network is bounded
Let \(\color{red}H \subseteq G\) be the sink and all edges leading towards the sink
 \(\implies\) The total volume of flow in \(H\) eventually stays small
 \(\implies\) Then all queues in \(H\) are small
 \(\implies\) \(H\) acts as a new sink

\(s\)
\(t\)
\(s'\)
\(H\)

Termination (Multi-Sink)?

There exists a multi-source multi-sink network \(G\),
where IDE flows exist, but none of them terminate.

\(s\)
\(t\)
\(s\)
\(s\)
\(s\)

        Questions:

Existence?Termination?
For any given network: Does an IDE flow exist?Do all IDE flows terminate? I.e. does all flow volume reach a sink in finite time?
single
sink
multi-
sink		?
→ Leon Sering: ?

More details: https://arxiv.org/abs/1811.07381

Augsburg
Potsdam
Amsterdam