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{\IN}{\mathbb{N}} \newcommand{\INs}{\mathbb{N}^\ast} \newcommand{\INo}{\mathbb{N}_0} \newcommand{\IZ}{\mathbb{Z}} \newcommand{\IR}{\mathbb{R}} \newcommand{\IC}{\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}} \newcommand{\dist}[2]{\mathrm{dist}^c_{#1}(#2)} \newcommand{\dists}[2]{{\mathrm{dist}^c_{#1}}'(#2)} \newcommand{\Ind}{{\Large\raise{0pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\norm}[1]{\left\|#1\right\|} \newcommand{\scalar}[2]{\left\langle #1,#2 \right\rangle} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \newcommand{\Pc}{\mathcal{P}} \newcommand{\Wc}{\mathcal{W}} \)

Side-Constrained Dynamic Traffic Equilibria

Lukas Graf, Tobias Harks
University of Passau
s v t time volume

13th Day on Computational Game Theory (Amsterdam)

Base Model  ...

$h^\ast \in \Lambda(r)$ a dynamic equilibrium iff   $h^\ast_{p}(t)>0 \implies \Psi_{p}(h^\ast,t) \leq \Psi_{q}(h^\ast,t)$   f.a. $p,q \in \Pc_i$ and $t \in [0,T]$.
$h^\ast \in \Lambda(r)$ a dynamic equilibrium iff   $\langle \Psi(h^\ast),h-h^\ast\rangle \geq 0$   f.a. $h \in \Lambda(r)$.
DE exist.$\implies$

...  +  Side-Constraints

$h^\ast \in\;$$\Lambda(r)$ a dynamic equilibrium iff   $\langle \Psi(h^\ast),h-h^\ast\rangle \geq 0$   f.a. $h \in\;$$\Lambda(r)$.
$h^\ast \in\;$$S$ a side-constrained dynamic equilibrium if   $\langle \Psi(h^\ast),h-h^\ast\rangle \geq 0$   f.a. $h \in\;$$S$.
SCDE exist.$\implies$
$h^\ast \in\;$$\Lambda(r)$ a dynamic equilibrium iff   $h^\ast_{p}(t)>0 \implies \Psi_{p}(h^\ast,t) \leq \Psi_{q}(h^\ast,t)$   f.a. $p,$ $q\;$$\in \Pc_i$ and $t \in [0,T]$.
$h^\ast \in\;$$S$ a side-constrained dynamic equilibrium if   $h^\ast_{p}(t)>0 \implies \Psi_{p}(h^\ast,t) \leq \Psi_{q}(h^\ast,t)$   f.a. $p \in \Pc_i$, $q \in U_p(h^\ast,t)$ $\;\subseteq \Pc_i$, $t \in [0,T]$.
      where $U_p(h,t) \coloneqq \Set{q \in \Pc_i \,|\, \forall \delta > 0, \varepsilon > 0: \exists J \subseteq [t-\delta,t+\delta], \varepsilon' \leq \varepsilon: (q,J,\varepsilon') \in A_p(h)}$
If $S$ is convex and $A_p$ are sufficiently nice, SCDE are characterized by VI.
If $A_p$ are sufficiently nice, SCDE are characterized by QVI.
s v t time volume
time inflow \color{red}{\varepsilon} \color{red}{J} \color{DodgerBlue}{h_p} time inflow \color{DodgerBlue}{h_q} time inflow \color{DodgerBlue}{h'_p} time inflow \color{DodgerBlue}{h'_q} \color{DodgerBlue}{h} \color{DodgerBlue}{h' \coloneqq H_{p \to q}(h,J,\varepsilon)} (q,J,\varepsilon) \in A_p(h):

Volume Constraints

  • volume constraints $c_e: \IR_{\geq 0} \to \IR_{\geq 0}$ for every edge $e \in E$
Define $S \coloneqq \Set{h \in \Lambda(r) \,|\, x_e(h,\theta) \leq c_e(\theta) \text{ f.a. } \theta \in \IR_{\geq 0}, e \in E}$
flow volume on edge $e$
Define $A_p(h) \coloneqq \Set{(q,J,\varepsilon) \,|\, x_e(h',\tau^e(h',t)) \leq c_e(\tau^e(h',t)) \text{ f.a. } t \in J, e \in q, h' \coloneqq H_{p \to q}(h,J,\varepsilon)}$
Define dynamic Bernstein-Smith equilibrium
arrival time at edge $e$
    or     $A_p(h) \coloneqq \Set{(q,J,\varepsilon) \,|\, x_e(h,\tau^e(h,t)) + \varepsilon \leq c_e(\tau^e(h,t)) \text{ f.a. } t \in J, e \in q}$
Define dynamic Larsson-Patriksson equilibrium
    or   ...

Existence

Under the following assumptions there exists a dynamic Larsson-Patricksson equilibrium:
  • flow dynamics described by deterministic queuing or linear edge delays
  • side-constraints are non-decreasing edge volume-constraints
  • there is always at least one unsaturated path
  • Define penalty function $\xi_e(h,\theta) \coloneqq \max\Set{0,x_e(h,\theta)-c_e(\theta)}$
  • Define new path delay $\Psi_p^\lambda(h,t) \coloneqq \Psi_p(h,t) + \lambda\sum_{e \in p}\xi_e(h,\tau^e(h,t))$
  • $\implies$ DE wrt. $\Psi^\lambda$ exist (f.a. $\lambda$) and converge to LPDE wrt. $\Psi$
Also works with departure time choice, other flow dynamics, stronger equilibria, ...
  • Previous definition/existence result for side-constrained dynamic equilibria is flawed
  • New general framework for side-constrained dynamic equilibria
  • Characterization via (quasi) variational inequalities
  • Existence for volume constraints (under certain assumptions)
  • But no structural insights (yet)
Side-Constrained Dynamic Traffic Equilibria Lukas Graf
Side-Constrained Dynamic Traffic Equilibria - Model Lukas Graf
Side-Constrained Dynamic Traffic Equilibria - Existence Lukas Graf
Side-Constrained Dynamic Traffic Equilibria - Conclusion Lukas Graf