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

\( \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}} \)

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