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

Lukas Graf1, Tobias Harks1, Leon Sering2

1 Augsburg University, 2 Technische Universität Berlin
Goal

## ↑ Discrete Model

(unsplittable flow particles, discrete time steps)

## Continuous Model ↓

(infinitesimal flow particles, continuous time)

### Physical Model

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

## Questions:

Existence of IDEs?

Termination of IDEs?

Construction of IDEs?

Quality of IDEs?

## Existence (Single-Sink)

In single-sink networks IDE flows always exist
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$$
Extend flow for all times using Zorn's Lemma
$$s$$
$$u = 3\cdot \Ind_{[0,3]}$$
$$v$$
$$w$$
$$x$$
$$y$$
$$t$$

## Existence (Multi-Sink)

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{v,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).
This extension proof is non-constructive!
However, there is also an constructive extension proof using MIP
However, solving an MIP is hard!
$$s_1$$
$$s_2$$
$$t_2$$
$$t_1$$

## Construction (Single-Sink)

A distribution of the node inflow to active edges satisfying
$$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}$$
can be found in polynomial time.
Define $$h_{vw}\big(f_{vw}^+(\theta)\big) := c'_{vw}(\theta) + \dists{w,t}{\theta}$$.
For acyclic graphs the above algorithm computes an IDE with a finite number of phases within $$[0,T]$$ for every time horizon $$T \geq 0$$.
Computing an IDE flow is NP-hard (even for acyclic graphs).

## Termination (Single-Sink)

In single-sink networks $$G$$ all IDE flows terminate
within at most $$4U\tau_G$$.
In an acyclic graph the termination time is $$\tau_{\max}+U$$.
Without queues the active edges form a static acyclic graph.
With only small queues the active edges form a static acyclic graph.
A subgraph $$H \subseteq G$$ containing the sink $$t$$ as well as all its shortest paths towards the sink
is sink-like for some interval $$[a,b]$$ if the sum of
• current flow volume within $$H$$ and
• the cummulative inflow into $$H$$ over $$[a,b]$$
is at most $$\frac{1}{2}$$.
Let $$v \in G\setminus H$$ be closest to $$t$$. Then $$H+v$$ is sink-like for $$\left[a,b-\sum_{e \text{ edge between } v \text{ and } H}(\tau_e + \frac{1}{\nu_e})\right]$$.
$$\implies$$ If $$H := \{t\}$$ is sink-like for $$\tau_G+|E|$$, the flow terminates.
$$\implies$$ The sink has inflow of at least $$\frac{1}{2}$$ all $$2\tau_G$$ time steps.
$$s_1$$
$$v_2$$
$$v_1$$
$$s_3$$
$$s_2$$
$$t$$

## Termination (Multi-Sink)

There exists a multi-sink network where all IDE flows cycle forever.
For IDEs in multi-sink-networks the Price of Anarchy is $$\infty$$.
$$s_1$$
$$t_1$$
$$s$$
$$s$$
$$s$$

## Quality (Single-Sink)

For single-sink instances with parameters $$U$$ and $$\tau_G$$ the Price of Anarchy (PoA) is in $$\mathcal{O}(U\tau_G)$$.
For single-sink instances with parameters $$U$$ and $$\tau_G$$ the Price of Anarchy (PoA) is in $$\Omega(U\log\tau_G)$$.

Close the gap between the bounds for the PoA!

## Connection?

Dynamic Flows with Adaptive Route Choice Lukas Graf