Dynamic Flows with Adaptive Route Choice

Lukas Graf¹, Tobias Harks¹, Leon Sering²

¹ Augsburg University, ² 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

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.

Given an IDE flow $f$ up to some time $\theta$ ,
extend $f$ up to some time $\theta+\varepsilon$ .
Calculate node inflows at time $\theta$ .
Order nodes by their distance to sink $t$ .
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$ ).

Given an IDE flow $f$ up to some time $\theta_0$ , extend $f$ up to some time $\theta_0+\varepsilon$ .
Calculate the node-inflows at time $\theta_0$ .
Order nodes by their distance to sink $t$ .

Let $K := \{g\,|\,g$ extension of $f$ on $[\theta_0, \theta_0+\tau_{\min})$ (not necessarily IDE) $\}$ .
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$

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$

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$

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)