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.

\( \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}{{\small\raise{-1pt}{\unicode{x1D7D9}}\,}} \newcommand{\bigO}{\mathcal{O}} \newcommand{\abs}[1]{\left|#1\right|} \newcommand{\rDeriv}{\partial_+} \newcommand{\lDeriv}{\partial_-} \newcommand{\queue}{q} \)

A Finite Time Combinatorial Algorithm
for Instantaneous Dynamic Equilibrium Flows

(and their Computational Complexity)


Lukas Graf, Tobias Harks
Augsburg University




I. Model

Physical Model

  • A directed graph $G = (V,E)$
  • Edge travel times $\tau_e \in \INs$ (here $\tau_e=1$)
  • Edge capacities $\nu_e \in \INs$ (here, mostly, $\nu_e \in \Set{1,\infty}$)
  • Single sink $t \in V$
  • Network inflow rates $u_v: \IR_{\geq 0} \to \IR_{\geq 0}$ for all nodes $v \neq t$
    (piece-wise constant, finitely lasting with finitely many steps)
  • Inflow $f_e^+(\theta)$ \(\gt\) capacity $\nu_e$ \(\implies\) queues form at the start (with length \(q_e(\theta)\))

Behavioral Model

The current travel time at time \(\theta\) on edge \(e\) is \(c_e(\theta) := \tau_e + q_e(\theta)/\nu_e\).

A flow is in Instantaneous Dynamic Equilibrium (IDE) if the following holds:
Whenever positive flow enters an edge, this edge must lie on a currently shortest path towards the respective sink (w.r.t. \(c\)).

\[f^+_{vw}(\theta) > 0 \implies \ell_v(\theta) = c_{vw}(\theta) + \ell_w(\theta)\]

where $\ell_v(\theta) \coloneqq \begin{cases}0, & \text{if } v=t \\ \min_{e=vw}\{\ell_w(\theta) + c_e(\theta)\}, &\text{else}\end{cases}$

(we then call edge $vw$ active at time $\theta$)

Question: Can we compute an IDE?
\text{time} \small U \small 2 u_s \text{time} \small 1 \queue_{vt} s v w x t (\tau_{sx},\nu_{sx}) (\,\,1\,\,\,\,,\infty) (\tau_{vt},{\tiny\nu_{vt}}) (\,1\,\,\,,\,{\tiny 1}\,\,) c_{vt}(\theta) = 1+2 = 3 \small 0 \small 1 \small 2 \small 3 \small 3

II. Algorithm

An Algorithm for Computing IDEs:

Input: A single-sink network $\mathcal{N} = (G,\tau,\nu,u,t)$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$

(2) While not all flow has reached $t$ Do

(3) .. Extend $f$

(3) .. Assume all $f_e^{^-}$ constant on $[\theta,\theta+\alpha_0)$

(3) .. Sort nodes s.th. $\ell_{v_1}(\theta) \leq \ell_{v_2}(\theta) \leq \dots$
(4) .. For $i = 1, \dots, n$ Do

(5) .... Find constant IDE extension of $f$ at $v_i$
(5) .... for some $[\theta,\theta+\alpha_i]$ with $\alpha_i \gt 0$

(6) .. Extend $f$ up to $\theta \coloneqq \theta+\min\Set{\alpha_i}$

Distribute to (currently) active edges $vw$ s.th.:
$f^+_{vw}(\theta) > 0 \implies \phantom{\rDeriv}\ell_{v}(\theta) = \phantom{\rDeriv} c_{vw}(\theta) + \phantom{\rDeriv}\ell_{w}(\theta)$
$f^+_{vw}(\theta) = 0 \implies \phantom{\rDeriv}\ell_{v}(\theta) \leq \phantom{\rDeriv} c_{vw}(\theta) + \phantom{\rDeriv}\ell_{w}(\theta)$
$f^+_{vw}(\theta) > 0 \implies \rDeriv\ell_{v}(\theta) = \rDeriv c_{vw}(\theta) + \rDeriv\ell_{w}(\theta)$
$f^+_{vw}(\theta) = 0 \implies \rDeriv\ell_{v}(\theta) \leq \rDeriv c_{vw}(\theta) + \rDeriv\ell_{w}(\theta)$
Can be computed in polynomial time.
The algorithm is correct.             □
The algorithm is finite.                 ?
  • IDE flows in single-sink networks terminate. [GHS, IPCO2019]
  • Only a finite number of extension phases is necessary...
\text{time} \small U \small 2 u_s s v w x t

III. Finiteness

An Algorithm for Computing IDEs (in acyclic networks):

Input: An acyclic single-sink network $\mathcal{N}$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$
(2) While not all flow has reached $t$ Do
(3) .. Sort nodes s.th. $\ell_{v_1}(\theta) \leq \ell_{v_2}(\theta) \leq \dots$
(4) .. For $i = 1, \dots, n$ Do
(5) .... Find constant IDE extension of $f$ at $v_i$
(5) .... for some $[\theta,\theta+\alpha_i]$
(6) .. Extend $f$ up to $\theta \coloneqq \theta\,+\,\min\Set{\alpha_i}$
Input: An acyclic single-sink network $\mathcal{N}$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$
(2) Fix some topological order $v_1 \lt v_2 \lt \dots$
(3) While not all flow has reached $t$ Do
(4) .. For $i = 1, \dots, n$ Do
(5) .... Find constant IDE extension of $f$ at $v_i$
(5) .... for some $[\theta,\theta+\alpha_i]$
(6) .. Extend $f$ up to $\theta \coloneqq \theta\,\,+$$\,\,\min\Set{\alpha_i}$
Input: An acyclic single-sink network $\mathcal{N}$
Output: An IDE flow $f$ in $\mathcal{N}$
(1) Let $f$ be an IDE flow up to time $\theta = 0$
(2) Fix some topological order $v_1 \lt v_2 \lt \dots$
(3) While not all flow has reached $t$ Do
(4) .. For $i = 1, \dots, n$ Do
(5) .... Find piecewise constant IDE extension
(5) .... of $f$ at $v_i$ for $[\theta,\theta+1]$
(6) .. Extend $f$ up to $\theta \coloneqq \theta\,\,+$$\,\,1$
$h_i: [\theta_1, \theta_2] \to \IR_{\geq 0}, \theta \mapsto \tau_{vw_i}+\frac{\queue_{vw_i}(\theta)}{\nu_{vw_i}} + \ell_{w_i}(\theta)$
v w_1 w_2 w_3 w_4 f^-_e
\ell_{w_1} \ell_{w_2} \ell_{w_3} \ell_{w_4}
Given a node $v$ and an IDE $f$ up to $\theta_1$, extended to an IDE up to $\theta_2 > \theta_1$ for all nodes closer to $t$ than $v$, s.th.
  • the inflow into node $v$ is constant over $[\theta_1,\theta_2]$ and
  • the labels at all nodes closer to $t$ thant $v$ are linear.
Then we can extend $f$ at $v$ to an IDE up to time $\theta_2$ in a finite number of subphases.
For acyclic networks the above algorithm constructs an IDE flow in finite time.
We only need the network to be acyclic for the fixed topological order.

The subgraph of active edges is always acyclic.

For general networks: Show that we only need to change the topological order finitely often.
For general single-sink networks the extension algorithm computes an IDE flow in finite time.

(in at most $\bigO\left(P(2(\Delta+1)^{4^\Delta+1})^{T\abs{V}\cdot \abs{E}/C}\right)$ phases)

IV. Complexity

The following decision problems are NP-hard:
  • Given a network and a specific edge: Is there an IDE flow not using this edge?
  • Given a network and a specific edge: Is there an IDE flow using this edge?
  • Given a network and some time $T$: Is there an IDE terminating before $T$?
  • Given a network and some number $k$: Is there an IDE flow with at most $k$ phases?
Reduction from 3Sat:
\[\big(x_1 \,\,\,\vee\,\,\, \neg x_1 \,\,\,\vee\,\,\, x_2\big) \,\,\qquad\qquad\wedge\,\,\qquad\qquad \big(\neg x_1 \,\,\,\vee\,\,\, \neg x_2 \,\,\,\vee\,\,\, \neg x_3\big)\]
c_1 c_2 x_1 \neg x_1 x_2 \neg x_2 x_3 \neg x_3 t s \mathcal{N}' \theta \small 1 u_{c_i}

V. Conclusion

What we learned:

  • IDEs can be computed in finite time.
  • Existence of IDEs with natural properties is hard.
  • IDEs can be analyzed locally (in time and space).

What's still to learn:

  • Can we improve the bound on the number of extension phases?
  • Can we allow zero-travel-time edges? (i.e. $\tau_e=0$)
  • What happens with multiple sinks? (i.e. different commodities)
A Finite Time Combinatorial Algorithm for IDE Flows Lukas Graf
A Finite Time Combinatorial Algorithm for IDE Flows - I. Model Lukas Graf
A Finite Time Combinatorial Algorithm for IDE Flows - II. Algorithm Lukas Graf
A Finite Time Combinatorial Algorithm for IDE Flows - III. Finiteness Lukas Graf
A Finite Time Combinatorial Algorithm for IDE Flows - IV. Complexity Lukas Graf
A Finite Time Combinatorial Algorithm for IDE Flows - V. Conclusion Lukas Graf