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 Flows with Adaptive Route Choice

Lukas Graf, Tobias Harks, Leon Sering

## ↑ Discrete Model

(atomic flow particles, discrete time steps)

## Continuous Model ↓

(infinitesimal flow particles, continuous time)

### Physical Model

• Directed graph $G = (V,E)$
• For $e \in E$: free flow travel time $\tau_e \in \IR_{\geq 0}$ and service rate $\nu_e \in \IR_{\geq 0}$
• Commodities $I$ with source node $s_i$, sink node $t_i$
and network inflow rate $u_i: \IR_{\geq 0} \to \IR_{\geq 0}$
• (Edge)flow $(f_{e,i}^+,f_{e,i}^-) \in L^1(\IR_{\geq 0},\IR_{\geq 0})^2$
• Inflow $\gt$ service rate $\implies$ queues form
$f_e^+(\theta) \gt \nu_e$                             (length $q_e(\theta)$)

### Behavioral Model

• Current travel time $c_e(\theta) \coloneqq \tau_e + q_e(\theta)/\nu_e$
• Current distance $\ell_{v,i}(\theta) \coloneqq \min\Set{c_e(\theta)+\ell_{w,i}(\theta) \mid e=vw}$
A flow is in Instantaneous Dynamic Equilibrium (IDE) if
$f^+_{e,i}(\theta) \gt 0 \implies \ell_{v,i}(\theta) = c_e(\theta) + \ell_{w,i}(\theta)$ for all $e=vw \in E$, $i \in I$ and almost all $\theta \in \IR_{\geq0}$

## Results:

• Existence
• Computation
• Complexity
• Quality
Partial IDE can always be extended for some $\alpha \gt 0$
Via...
• Variational inequality
• Fixed point theorem
• Convex optimization
For single-commodity and piecewise constant flow rates:
Finitely many extensions suffice...
...and any extension can be computed in poly time
IDE related decision problems are NP-hard.
Single-commodity: PoA $\in \Omega(U\log \tau) \cap \bigO(U\tau)$
Multi-commodity: Flow may cycle forever

## Potential Directions for Future Research:

• Closing gaps between bounds (Complexity/Quality)
• Improving quality (e.g. better predictions, network design)
• Different viewpoint (IDE as result from decentralized routing protocol)
• Generalizations (e.g. different flow dynamics)
• Convergence (discrete to continuous)
Dynamic Flows with Adaptive Route Choice Lukas Graf
Dynamic Flows with Adaptive Route Choice - Model Lukas Graf
Dynamic Flows with Adaptive Route Choice - Results Lukas Graf
Dynamic Flows with Adaptive Route Choice - Future Research Lukas Graf