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.

→ static pdf-version

# Dynamic Traffic Assignment for Electric Vehicles

Lukas Graf, Tobias Harks, Prashant Palkar
Augsburg University

→ static pdf-version

Seminar “Dynamic Traffic Models in Transportation Science” at Schloss Dagstuhl

## I. Model

### 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 (infinitesimal 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

## II. Existence

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
then there exists some $h^* \in K$ such that $\scalar{\A(h^*)}{h-h^*} \geq 0 \text{ for all } h \in K$.
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$).
1. 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)$)
2. 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}$.
3. 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}$.
4. 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}$.
5. 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}$.
6. 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.
7. Show that $\A$ is sequentially weak-strong continuous:
$\exists$ a finite set $\Wc' \subseteq \Wc$ of dominating walks.
Only visit a node again with increased battery state.

## III. Structure and Computation

A numerical algorithm for computing energy-feasible dynamic equilibria:
(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}$

(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) .. Find functions $v_i: [0,T] \to \IR$ s.th. f.a. $i \in I, \theta \in [0,T]$:
(0) .. .. $\sum_{(i,W) \in \Wc'} \left[h^k_{i,W}(\theta) - \alpha c_{i,W}(\theta) + v_i(\theta)\right]_+ = u_i(\theta)$

(6) .. Set $h^{k+1}_{i,W} \leftarrow \left[h^k_{i,W}(\theta) - \alpha c_{i,W}(\theta) + v_i(\theta)\right]_+$ and increment $k$

(7) Until $\frac{\norm{h^k-h^{k-1}}}{h^k} \leq \varepsilon$

$h^k = h^{k-1}$
$\iff \frac{1}{\alpha}v_i(\theta) = \min\Set{c_{i,W}(\theta) | (i,W) \in \Wc'}$
$\iff$ $h^k$ is an energy-feasible dynamic equilibrium

## IV. Conclusion

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

### 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.
Dynamic Traffic Assignment for Electric Vehicles Lukas Graf
Dynamic Traffic Assignment for Electric Vehicles - I. Model Lukas Graf
Dynamic Traffic Assignment for Electric Vehicles - II. Existence Lukas Graf
Dynamic Traffic Assignment for Electric Vehicles - III. Structure Lukas Graf
Dynamic Traffic Assignment for Electric Vehicles - IV. Conclusion Lukas Graf
Dynamic Traffic Assignment for Electric Vehicles - V. Generalization Lukas Graf