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.

# Side-ConstrainedDynamic TrafficEquilibria

Lukas Graf, Tobias Harks
University of Passau

13th Day on Computational Game Theory (Amsterdam)

### Base Model  ...

• directed graph $G=(V,E)$
• commodities $i \in I$ with fixed network inflow rate $r_i: [0,T] \to \IR_{\geq 0}$ and (finite) set $\Pc_i$ of source,sink-paths
• route choices of all (infinitesimally small) agents described by path inflow rates $(h_{p})_{p} \in \Lambda(r) \coloneqq \Big\{h \in \left(L^2_+([0,T])\right)^{\sum_{i \in I}\Pc_i} \,\Big|\, \sum_{p \in \Pc_i}h_{p}=r_i \text{ for all } i \in I\Big\} \subseteq \left(L^2_+([0,T])\right)^{\sum_{i \in I}\Pc_i}.$
• (effective) path delay operator $\Psi: \Lambda(r) \to C([0,T])^{\sum_{i \in I}\Pc_i}$
compact, convex
continuous
$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

• constraint set $S \subseteq \Lambda(r)$
convex?
• admissible $\varepsilon$-deviations $A_p: S \rightrightarrows \Pc_i \times \mathcal{M}([0,T]) \times \IR_{\geq 0}$
$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.

### 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}$
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