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.

\(
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\U}{\mathfrak{U}}
\newcommand{\coloneqq}{:=}
\newcommand{\Set}[1]{\left\{#1\right\}}
\newcommand{\supp}{\mathrm{supp}}
\newcommand{\Re}{\mathrm{Re}}
\newcommand{\Im}{\mathrm{Im}}
\newcommand{\clos}[1]{\overline{#1}}
\newcommand{\inte}[1]{\mathring{#1}}
\)

with Adaptive Route Choice

Tobias Harks and Lukas Graf

Universität Augsburg

February 15, 2019

Universität Augsburg

February 15, 2019

with Adaptive Route Choice

Tobias Harks and Lukas Graf

Universität Augsburg

February 15, 2019

Universität Augsburg

February 15, 2019

Augsburg

Potsdam

Amsterdam

- 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\)

\(\nu_e = 2\)

\(\tau_e = 1\)

\(\nu_e = 3\)

\(\nu_e = 3\)

\(\tau_e = 2\)

\(\nu_e = 4\)

\(\nu_e = 4\)

\(s\)

\(t\)

\(2\)

\(1\)

\(0\)

\(u_1\)

\(s'\)

\(t\)

\(3\)

\(1\)

\(2\)

\(u_2\)

\(q_e(2) = 1\)

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\)

\(\nu_e = 2\)

\(\tau_e = 1\)

\(\nu_e = 3\)

\(\nu_e = 3\)

\(\tau_e = 2\)

\(\nu_e = 4\)

\(\nu_e = 4\)

\(q_e(\theta) = 1\)

\(q_e(\theta) = 2\)

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? | |

single sink | ||

multi- sink |

\(s\)

\(t\)

\(s'\)

\(\tau_e = 1\)

\(\nu_e = 2\)

\(\nu_e = 2\)

\(\tau_e = 1\)

\(\nu_e = 3\)

\(\nu_e = 3\)

\(\tau_e = 2\)

\(\nu_e = 4\)

\(\nu_e = 4\)

\(q_e(\theta) = 2\)

For any multi-source single-sink network \(G\)

there exists an IDE flow.

Given: | An IDE flow \(f\) up to some time \(\theta\) |
---|---|

Goal: | 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\) |

Idea: | 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\)

\(\nu_e = 2\)

\(\tau_e = 1\)

\(\nu_e = 3\)

\(\nu_e = 3\)

\(\tau_e = 2\)

\(\nu_e = 4\)

\(\nu_e = 4\)

\(q_e(\theta) = 2\)

\(q_e(\theta) = 1\)

\(q_e(\theta) = 3\)

\(q_e(\theta) = 6\)

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\)

There exists a multi-source multi-sink network \(G\),

where IDE flows exist, but none of them terminate.

\(s\)

\(t\)

\(s\)

\(s\)

\(s\)

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? | |

single sink | ||

multi- sink | ? → Leon Sering: ? |

More details: https://arxiv.org/abs/1811.07381

Augsburg

Potsdam

Amsterdam