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-Constrained Dynamic Traffic Equilibria

Lukas Graf, Tobias Harks
University of Passau
→ static pdf-version

EC'23 (London)

### Model (static)

• directed graph $G=(V,E)$
• commodities $i \in I$ with fixed flow volume $Q_i \in \IR_{\geq 0}$
and finite set $\Pc_i$ of source,sink-paths
• route choices of all agents described by vector $(x_{p})_{p} \in X \coloneqq \Big\{x \in \IR_{\geq 0}^{\sum_{i \in I}\Pc_i} \,\Big|\, \sum_{p \in \Pc_i}x_p = Q_i \text{ f.a. } i \in I\Big\}$
• path costs $\ell: X \to \IR_{\geq 0}^{\sum_{i \in I}\Pc_i}$
$x^\ast \in X$ a Wardrop equilibrium if   $x^\ast_{p}>0 \implies \ell_{p}(x^\ast) \leq \ell_{q}(x^\ast)$   f.a. $p,q \in \Pc_i$.
• additional side-constraints $Z \subseteq X$ (e.g. $Z \coloneqq \Set{x \in X \Mid x_e \leq c_e}$)
• TEXTTEXTTEXT
$x^\ast \in\;$$Z a side-constrained equilibrium if x^\ast_{p}>0 \implies \ell_{p}(x^\ast) \leq \ell_{q}(x^\ast) f.a. p \in \Pc_i and unsaturated q \in \Pc_i. Studied e.g. by [Bernstein, Smith 94], [Larsson, Patriksson 95], [Marcotte, Nguyen, Schoeb 04], [Correa, Schulz, Stier-Moses 04], ... ### Model (dynamic) • directed graph G=(V,E) • commodities i \in I with fixed flow volume Q_i \in \IR_{\geq 0} and finite set \Pc_i of source,sink-paths • route and departure time choices of all agents described by $(h_{p})_{p} \in \Lambda(Q) \coloneqq \Big\{h \in \left(L^2_+([0,T])\right)^{\sum_{i \in I}\Pc_i} \,\Big|\, \sum_{p \in \Pc_i}\int_0^T h_{p}(t)dt=Q_i \text{ for all } i \in I\Big\}$ • effective path delay operator \Psi: \Lambda(Q) \to C([0,T])^{\sum_{i \in I}\Pc_i} h^\ast \in \Lambda(Q) a dynamic equilibrium if 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,t' \in [0,T]. • constraint set S \subseteq \Lambda(Q) • admissible \varepsilon-deviations A_p$$:\;S \rightrightarrows \Pc_i \times \mathcal{M}([0,T]) \times \IR_{\geq 0} \times \IR$
$h^\ast \in S$ a SCDE if   $h^\ast_{p}(t)>0 \implies \Psi_{p}(h^\ast,t) \leq \Psi_{q}(h^\ast,t+\Delta)$   f.a. $p \in \Pc_i$, $(q,\Delta) \in U_p(h^\ast,t)$ $\;\subseteq \Pc_i$, $t \in [0,T]$.
where $U_p(h,t) \coloneqq \Set{(q,\Delta) \in \Pc_i \,|\, \forall \delta > 0, \varepsilon > 0: \exists J \subseteq [t-\delta,t+\delta], \varepsilon' \leq \varepsilon: (q,J,\varepsilon',\Delta) \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(Q) \,|\, 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,\Delta) \,|\, x_e(h',\tau^e(h',t)) \leq c_e(\tau^e(h',t)) \text{ f.a. } t \in J+\Delta, e \in q, h' \coloneqq H_{p \to q}(h,J,\varepsilon,\Delta)}$
Define dynamic Bernstein-Smith equilibrium
arrival time at edge $e$
or     $A_p(h) \coloneqq \Set{(q,J,\varepsilon,\Delta) \,|\, x_e(h,\tau^e(h,t)) + \varepsilon \leq c_e(\tau^e(h,t)) \text{ f.a. } t \in J+\Delta, e \in q \text{ except on prefix if } \Delta=0}$
Define dynamic Marcotte-Nguyen-Schoeb equilibrium
or   ...

### Existence

For $S$ convex, non-empty, closed, bounded and $A_p$ sufficiently nice there exists an SCDE.
Characterization by VI + existence result for VI.
Under the following assumptions there exists a dynamic MNS 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 (weakly) to MNS wrt. $\Psi$
• General abstract framework for side-constrained dynamic equilibria
• Existence for volume constraints (under certain assumptions)
• Characterization via (quasi) variational inequalities
• But no structural insights/combinatorial algorithms (yet)
• More discussion of equilibrium concepts needed
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