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 Flowswith Adaptive Route Choice

Tobias Harks and Lukas Graf
Universität Augsburg
February 15, 2019

# Dynamic Flowswith Adaptive Route Choice

Tobias Harks and Lukas Graf
Universität Augsburg
February 15, 2019
Augsburg
Potsdam
Amsterdam              ## The Physical Flow Model

• Digraph $$G = (V,E)$$
• Edge $$e \in E$$ has length $$\tau_e \in \Z_+$$ and capacity $$\nu_e \in \Z_+$$
• Commodities $$i \in I$$ with source $$s_i \in V$$ and sink $$t_i \in V$$ and constant inflow rate $$u_i: [r_i,R_i] \to \R_+$$
• Inflow $$>$$ Capacity $$\Rightarrow$$ Queue forms (with length $$q_e$$)
Augsburg
Potsdam
Amsterdam
$$s$$
$$t$$
$$s'$$
$$\tau_e = 1$$
$$\nu_e = 2$$
$$\tau_e = 1$$
$$\nu_e = 3$$
$$\tau_e = 2$$
$$\nu_e = 4$$
$$s$$
$$t$$ $$2$$
$$1$$
$$0$$
$$u_1$$
$$s'$$
$$t$$ $$3$$
$$1$$
$$2$$
$$u_2$$
$$q_e(2) = 1$$ ## The Behavioral Model

We define the current travel time at time $$\theta$$ on edge $$e$$ by: $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$$).
(we call such an edge active)

$$s$$
$$t$$
$$s'$$
$$\tau_e = 1$$
$$\nu_e = 2$$
$$\tau_e = 1$$
$$\nu_e = 3$$
$$\tau_e = 2$$
$$\nu_e = 4$$
$$q_e(\theta) = 1$$
$$q_e(\theta) = 2$$

## Questions:

 Existence? Termination? For any given network: Does an IDE flow exist? Do all IDE flows terminate? I.e. does all flow volume reach a sink in finite time? singlesink multi-sink
$$s$$
$$t$$
$$s'$$
$$\tau_e = 1$$
$$\nu_e = 2$$
$$\tau_e = 1$$
$$\nu_e = 3$$
$$\tau_e = 2$$
$$\nu_e = 4$$
$$q_e(\theta) = 2$$

## Existence (Single Sink)

For any multi-source single-sink network $$G$$
there exists an IDE flow.

Given: An IDE flow $$f$$ up to some time $$\theta$$ Extending $$f$$ up to some time $$\theta + \varepsilon$$, i.e. for every $$v \in V$$ distribute inflow onto active edges at $$\theta$$ such that they remain active on $$[\theta,\theta+\varepsilon)$$ for some $$\varepsilon >0$$ Order nodes by increasing distance to the sink $$t$$ Distribute inflow node by node using a suitable Optimization Problem
$$s$$
$$t$$
$$s'$$
$$\tau_e = 1$$
$$\nu_e = 2$$
$$\tau_e = 1$$
$$\nu_e = 3$$
$$\tau_e = 2$$
$$\nu_e = 4$$
$$q_e(\theta) = 2$$
$$q_e(\theta) = 1$$
$$q_e(\theta) = 3$$
$$q_e(\theta) = 6$$

## Termination (Single Sink)

For any multi-source single-sink network $$G$$
all IDE flows terminate.

1) The sink can never be part of a cycle
2) The total amount of flow in the network is bounded
Let $$\color{red}H \subseteq G$$ be the sink and all edges leading towards the sink
$$\implies$$ The total volume of flow in $$H$$ eventually stays small
$$\implies$$ Then all queues in $$H$$ are small
$$\implies$$ $$H$$ acts as a new sink

$$s$$
$$t$$
$$s'$$ $$H$$ ## Termination (Multi-Sink)?

There exists a multi-source multi-sink network $$G$$,
where IDE flows exist, but none of them terminate.

$$s$$
$$t$$                      $$s$$          $$s$$          $$s$$            ## Questions:

 Existence? Termination? For any given network: Does an IDE flow exist? Do all IDE flows terminate? I.e. does all flow volume reach a sink in finite time? singlesink  multi-sink ?→ Leon Sering: ? More details: https://arxiv.org/abs/1811.07381

Augsburg
Potsdam
Amsterdam