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.

# Dynamic Network Flowswith Adaptive Route Choicebased on Current Information

Universität Augsburg
Lukas Graf

## Model

$\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$
$\xrightarrow{\hspace{2em}\displaystyle{\Phi_{e,\xi}}\hspace{2em}}$
$\phantom{(}f_{e\phantom{,i}}^-\phantom{)} \in L^1(\IRnn)\phantom{^I}$
$(f_{e,i}^-) \in L^1(\IRnn)^I$
• Existence & uniqueness
• Continuity
• Structure preserving
• Monotonicity
• No ideling
$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$.

### Quality ([GH22])

Let $\mathcal{F}$ be a set of partial flows $(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 flow $(f,\infty)$.
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 (a) and (b)}}$     (non-empty, convex, closed, compact)

For $g \in K$ define $\Gamma(g) \coloneqq \Set{h \in K \Mid (g^+,h^-) \text{ satisfies (c) and } h^+ \text{ satisfies (d) 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
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 $(f,\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?

### Computing Extensions

We can compute an IDE-extension on a node-by-node basis in polynomial time.
Given node $v$ with constant inflow during $[\xi,\xi+\eps)$ and linear travel times closer to the sink.
Compute $g^+_e(\theta)$         and $L^g_v(\theta)$ on $[\xi,\xi+\eps)$ such that:
• $\sum_{e \in \delta^+(v)}g^+_e(\theta) = u_v(\theta) + \sum_{e \in \delta^-(v)}f^-_e(\theta)$
• $L^g_v(\theta) = \min\Set{C^g_{vw}(\theta) + L^g_w(\theta) \Mid vw \in \delta^+(v)}$
• $g^+_{vw}(\theta) \gt 0 \implies L^g_v(\theta) = C^g_{vw}(\theta) + L^g_w(\theta)$
Compute $x^+_e \in \IRnn$ and $a_v \in \IR$                      such that:
• $\sum_{e \in \delta^+(v)}g^+_e(\theta) = u_v(\theta) + \sum_{e \in \delta^-(v)}f^-_e(\theta)$
• $L^g_v(\theta) = \min\Set{C^g_{vw}(\theta) + L^g_w(\theta) \Mid vw \in \delta^+(v)}$
• $g^+_{vw}(\theta) \gt 0 \implies L^g_v(\theta) = C^g_{vw}(\theta) + L^g_w(\theta)$
Compute $x^+_e \in \IRnn$ and $a_v \in \IR$                      such that:
• $\sum_{e \in \delta^+(v)}x^+_e = u_v(\xi) + \sum_{e \in \delta^-(v)}f^-_e(\xi)$
• $a_v = \min\Set{\psi_{vw}(x^+_{vw}) + a_w \Mid vw \in \delta^+(v) \text{ active at } \xi}$
• $x^+_{vw} \gt 0 \implies a_v = \psi_{vw}(x^+_{vw}) + a_w$ and $vw$ active at $\xi$
Compute $x^+_e \in \IRnn$ and $a_v \in \IR$                      such that:
• $\sum_{e \in \delta^+(v)}x^+_e = u_v(\xi) + \sum_{e \in \delta^-(v)}f^-_e(\xi)$
• $a_v \leq \psi_{vw}(x^+_{vw}) + a_w$ f.a. $vw \in \delta^+(v) \text{ active at } \xi$
• $x^+_{vw} \gt 0 \implies a_v = \psi_{vw}(x^+_{vw}) + a_w$ and $vw$ active at $\xi$
where $\psi_e(x^+_e) \coloneqq \begin{cases}\tfrac{x^+_e}{\nu_e}-1, &\ql(\xi) \gt 0 \\\max\{\tfrac{x^+_e}{\nu_e}-1,0\},&\text{else}\end{cases}$
Possible via water-filling:

### 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)$
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}$.
In a general network the makespan of any IDE is at most $\hat\theta + 3U\tau(G) + \dots$.

### Lower Bound for Multi-Commodity

There exists a multi-commodity network where no IDE ever terminates.
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)$.
...+ other existence proofs
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 $(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
3. Do IDE terminate within a finite time horizon?
Makespan in single-commodity at most $\hat\theta+2U\tau(G)$
There exist multi-commodity networks where no IDE terminates.
...+ SC lower bound, PoA

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

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