Base Model
- directed graph $G=(V,E)$ with edge travel times $\tau_e \in \IR_{>0}$ and capacities $\nu_e \in \IR_{>0}$
- commodities $i \in I$ with source and sink nodes $s_i, t_i \in V$ and bounded network inflow rate $u_i: [0,T] \to \IR_{\geq 0}$
- route choices of all (infinitesimally small) agents: \[(h_{i,P})_{i,P} \in \left(L^2_+([0,T])\right)^{\sum_{i \in I}\Pc_i}\] where $\Pc_i$ is the set of all (simple) $s_i$,$t_i$-paths.
-
path inflows $h$ $\mapsto$ edge flow $(f_e)_e$ $\mapsto$ path arrival times $\mu_{i,P}$
(here: Vickrey queuing model) - For almost all times $\theta \in [0,T]$: \[h_{i,P}(\theta)>0 \implies \mu_{i,P}(\theta) \leq \mu_{i,P'}(\theta) \text{ f.a. } P' \in \Pc_i\] Then $h$ is a Dynamic Equilibrium
Dynamic Equilibria are guaranteed to exist.
by [Han, Friesz, Yao 2013], [Cominetti, Correa, Larré, 2015].
+
Electric Vehicles
- battery consumption $b_{i,e} \in \IR_{\geq 0}$
- initial battery state $b_i \in \IR_{>0}$ and batt. capacity $b_{i,\max} \in \IR_{>0}$
-
recharging stations with different recharging modes
(duration, amount, price, capacity)
-
...and battery consumption $b_{i,e} \in \IR$ and prices $p_{i,e} \in \IR_{\geq 0}$
- ...and initial batt. state $b_i \in \IR_{>0}$, batt. capacity $b_{i,\max} \in \IR_{>0}$ and function converting travel time + price to costs $c_{i,W}$
- route choices of all (infinitesimal small) agents: \[(h_{i,W})_{i,W} \in \left(L^2_+([0,T])\right)^{\sum_{i \in I}\Wc_i}\] where $\Wc_i$ is the set of all (!) energy-feasible $s_i$,$t_i$-walks.
-
walk inflows $h$ $\mapsto$ edge flow $(f_e)_e$ $\mapsto$ walk arrival times $\mu_{i,W}$
walk inflows $h$ $\mapsto$ edge flow $(f_e)_e$ $\mapsto$ walk costs $c_{i,W}$ -
For almost all times $\theta \in [0,T]$:
\[h_{i,W}(\theta)>0 \implies c_{i,W}(\theta) \leq c_{i,W'}(\theta) \text{ f.a. } W' \in \Wc_i\]
Then $h$ is an Energy-Feasible Dynamic Equilibrium
Use a variational inequality (similiar to [Han, Friesz, Yao 2013] and [Cominetti, Correa, Larré, 2015]):
Given
- $K \subseteq \left(L^2([a,b])\right)^d$ non-empty, closed, convex and bounded
- $K \subseteq \left(L^2([a,b])\right)^{\color{red}d}$ non-empty, closed, convex and bounded
- $\A: K \to \left(L^2([a,b])\right)^d$ sequentially weak-strong continuous
For any* multi-commodity network there exists an energy-feasible dynamic equilibrium
(i.e. $h_{i,W}(\theta)>0 \implies c_{i,W}(\theta) \leq c_{i,W'}(\theta) \text{ f.a. } W' \in \Wc_i$).
(i.e. $h_{i,W}(\theta)>0 \implies c_{i,W}(\theta) \leq c_{i,W'}(\theta) \text{ f.a. } W' \in \Wc_i$).
- Find finite set $\Wc' \subseteq \Wc$ of dominating walks (f.a. $h \in K, (i,W) \in \Wc, \theta \geq 0$ there exists $(i,W') \in \Wc'$ s.th. $c_{i,W'}(\theta) \leq c_{i,W}(\theta)$)
- Define $K \coloneqq \Set{h \in \left(L^2([a,b])\right)^\Wc | \sum_{W \in \Wc_i}h_{i,W} = u_i \text{ for all } i \in I}$.
- Define $K \coloneqq \Set{h \in \left(L^2([a,b])\right)^{\color{red}{\Wc}} | \sum_{W \in \Wc_i}h_{i,W} = u_i \text{ for all } i \in I}$.
- Define $K \coloneqq \Set{h \in \left(L^2([a,b])\right)^{\color{red}{\Wc'}} | \sum_{W \in \Wc_i}h_{i,W} = u_i \text{ for all } i \in I}$.
- Define $K \coloneqq \Set{h \in \left(L^2([a,b])\right)^{\Wc'} | \sum_{W \in \Wc_i}h_{i,W} = u_i \text{ for all } i \in I}$.
- Define $\A(h)_{i,W}(\theta) \coloneqq c_{i,W}(\theta) - \min\Set{c_{i,W'}(\theta) | W' \in \Wc_i} \geq 0$.
Then: $\scalar{\A(h^*)}{h-h^*} \geq 0 \text{ for all } h \in K \implies h^*$ is energy-feasible DE.
$\exists$ a finite set $\Wc' \subseteq \Wc$ of dominating walks.
A numerical algorithm for computing energy-feasible dynamic equilibria:
(cf. [Han, Eve, Friesz 2019])
(cf. [Han, Eve, Friesz 2019])
Input: A network $\mathcal{N} = (G,(\tau_e),(\nu_e),(b_{i,e}),(p_{i,e}),(u_i),(s_i),(t_i))$, $\varepsilon > 0$
Output: An (approximate) energy-feasible DE $f$ in $\mathcal{N}$
Output: An (approximate) energy-feasible DE $f$ in $\mathcal{N}$
(1) Compute a finite dominating walk set $\Wc'$
(2) Choose any initial flow $h^0 \in C$, $k \leftarrow 0$
(3) Repeat
(4) .. Calculate network loading for $h^k$ and costs $c$
(5) .. Determine $h^{k+1}$ by shifting flow from expensive walks
(0) .. .. to cheaper walks
(7) Until $\frac{\norm{h^k-h^{k-1}}}{h^k} \leq \varepsilon$
$h^k = h^{k-1} \iff$ $h^k$ is an energy-feasible dynamic equilibrium
The Nguyen Network
The Nguyen Network
Effects of different recharging prices
Effects of different recharging capacities
- Classical model can be augmented with energy-consumption and recharging (incl. different modes/prices)
- Existence proofs for dynamic equilibria carry over with some adjustments
- In fact: The same is true for an even more general model with $h \in S$ for some convex restriction set $S \subseteq \left(L^2([a,b])\right)^\Wc$
- We can (numerically) compute energy-feasible equilibria
- However, runtime explodes with increased network size
- No structural insights in equilibria (yet)
- Flow animations created with a tool by Michael Markl
- All code available on github.com/ArbeitsgruppeTobiasHarks
General Convex Restriction Set
Given some convex set $S \subseteq \left(L^2([a,b])\right)^\Wc$, is there an equilibrium $h^* \in S \cap K$?
$h^* \in S \cap K$ is a Capacitated Dynamic Equilibrium if for all $(i,W) \in \Wc$ and almost all $\theta \in [0,T]$ we have:
\[h^*_{i,W}(\theta) > 0 \implies c_{i,W}(\theta) \leq c_{i,W'}(\theta)\]
for all unsaturated alternative walks $W'$ $\in D_{i,W}(h^*,\theta)$.
The set of unsaturated alternatives for $W$ at time $\theta$ is defined as
\[D_{i,W}(h,\theta) \coloneqq \Set{W' \in \Wc_i | \forall \delta' > 0 \exists \delta \in (0,\delta'], \varepsilon > 0: H_{i,W \to W'}(h,\theta,\varepsilon,\delta) \in S\ }\]
where $H_{i,W \to W'}(h,\theta,\varepsilon,\delta) \coloneqq (h'_{j,Q})$ with
- $h'_{i,W} \coloneqq \left[h_{i,W} - \varepsilon\Ind_{[\theta,\theta+\delta]}\right]_+$
- $h'_{i,W'} \coloneqq h_{i,W'} + h_{i,W} - \left[h_{i,W} - \varepsilon\Ind_{[\theta,\theta+\delta]}\right]_+$
- $h'_{j,Q} \coloneqq h_{j,Q}$ for all $(i,Q) \in \Wc \backslash \Set{(i,W),(i,W')}$
A set $\Wc' \subseteq \Wc$ is a dominating set with respect to $S$ if for any $h \in S \cap K$, $(i,W) \in \Wc$, $\theta \in [0,T]$ we have $c_{i,W'}(\theta) \leq c_{i,W}(\theta)$ and $W \in D_{i,Q}(h,\theta)$ implies $W' \in D_{i,Q}(h,\theta)$.
For any convex, closed restriction set $S \subseteq \left(L^2([a,b])\right)^\Wc$ with non-empty intersection with $K$ and finite dominating set $\Wc' \subseteq \Wc$ w.r.t. $S$ there exists a capacitated dynamic equilibrium.