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 Graf1, Tobias Harks1, Leon Sering2

1 Augsburg University, 2 Technische Universität Berlin
IPCO 2019,
Ann Arbor

Model

Physical Model

  • Directed (Multi-)Graph \(G = (V,E)\)
  • For all edges \(e \in E\): length \(\tau_e\) 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)

Agenda

Agenda

Goal of this Talk: Answer 24 questions about IDE flows:

Do IDE flows always exist?
Do all IDE flows terminate?
I.e. does all flow volume reach a sink in finite time?

Single-Sink: Existence

In single-sink networks IDE flows always exist
and we can always "construct" such an IDE flow.
  1. Given an IDE flow \(f\) up to some time \(\theta\),
    extend \(f\) up to some time \(\theta+\varepsilon\).
  2. Calculate node inflows at time \(\theta\).
  3. Order nodes by their distance to sink \(t\).
  4. 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\)
\(s_1\)
\(v_2\)
\(\dist{v_2,t}{\theta}=2\)
\(v_1\)
\(v_3\)
\(s_2\)
\(\dist{s_2,t}{\theta}=3\)
\(\dist{s_2,t}{\theta}=2\)
\(\dist{s_2,t}{\theta}=1\)
\(t_{{\color{blue}1}/{\color{red}2}}\)
\((\tau_e, \nu_e)\)
\(q_e(\theta) = 2\)
\(q_e(\theta) = 1\)
\(q_e(\theta) = 0\)

Single-Sink: Termination

In single-sink networks all IDE flows terminate.
The sink can never be part of a cycle.
The total amount of flow in the network is bounded.
 Let \(H \subseteq G\) be the subgraph consisting of
the sink and all edges leading towards the sink.
 \(\implies\) Volume of flow in \(H\) eventually stays small.
 \(\implies\) All queues in \(H\) are small.
 \(\implies\) \(H\) acts as a new sink.
 Add to \(H\) all edges leading into \(H\).
\(s_1\)
\(v_2\)
\(v_1\)
\(s_3\)
\(u_3 = 6\cdot\Ind_{[1.5,2]}\)
\(s_2\)
\(t\)
\(H\)

Multi-Sink: Existence

In multi-sink networks IDE flows always exist
(even for more general inflow rate functions \(u_i\)).
  1. Given an IDE flow \(f\) up to some time \(\theta_0\), extend \(f\) up to some time \(\theta_0+\varepsilon\).
  2. Calculate the node-inflows at time \(\theta_0\).
  3. Order nodes by their distance to sink \(t\).
  1. Let \(K := \{g\,|\,g\) extension of \(f\) on \([\theta_0, \theta_0+\tau_{\min})\) (not necessarily IDE)\(\}\).
  2. 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{w,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\)

  1. Such a \(g\) always exists (\(\mathcal{A}\) weak-strong-cont., \(K\) non-empty, closed, convex, bounded).
\(s_1\)
\(s_2\)
\(t_2\)
\(t_1\)

Multi-Sink: Termination

There exists a multi-sink network where all IDEs cycle.
\(s_1\)
\(t_1\)
\(s\)
\(s\)
\(s\)

Conclusion:

stepwise extension:

order nodes by their distance to sink
↓
send flow to active edges by waterfilling

→ constructive
growing sink:

\(t\)
stepwise extension:

correct extension is solution to var. inequality:

\(\langle \mathcal{A}(g),g'-g\rangle \geq 0\)

→ non-constructive
Gadget-Network:
\(s\)
\(s\)
\(s\)
Model Single-Sink Networks Multi-Sink Networks
Physical Behavioral Existence: Termination: Existence: Termination:
\(s_i\)
\(t_i\)
\(f_{i,e}^+(\theta)\)
\(q_{e}(\theta)\)
\((\tau_e, \nu_e)\)
 IDE-Flows only use currently shortest paths (active edges)
Dynamic Flows with Adaptive Route Choice Lukas Graf