Processing math: 100%

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.

Dynamic Flows with Adaptive Route Choice


Lukas Graf1, Tobias Harks1, Leon Sering2

1 Augsburg University, 2 Technische Universität Berlin
IPCO 2019,
Ann Arbor

Agenda

Agenda

Goal of this Talk: Answer 24 questions about IDE flows:

Do IDE flows always exist?
Do all IDE flows terminate?
I.e. does all flow volume reach a sink in finite time?

Single-Sink: Existence

In single-sink networks IDE flows always exist
and we can always "construct" such an IDE flow.
  1. Given an IDE flow f up to some time θ,
    extend f up to some time θ+ε.
  2. Calculate node inflows at time θ.
  3. Order nodes by their distance to sink t.
  4. Distribute node inflow to active edges such that:
    f+vw(θ)>0distcv,t(θ)=cvw(θ)+distcw,t(θ)
    f+vw(θ)=0distcv,t(θ)cvw(θ)+distcw,t(θ)
Invariant: Flows are piecewise constant, travel times change piecewise linear.
Distribution stays valid for some ε>0
s1
v2
distcv2,t(θ)=2
v1
v3
s2
distcs2,t(θ)=3
distcs2,t(θ)=2
distcs2,t(θ)=1
t1/2
(τe,νe)
qe(θ)=2
qe(θ)=1
qe(θ)=0

Single-Sink: Termination

In single-sink networks all IDE flows terminate.
The sink can never be part of a cycle.
The total amount of flow in the network is bounded.
 Let HG be the subgraph consisting of
the sink and all edges leading towards the sink.
  Volume of flow in H eventually stays small.
  All queues in H are small.
  H acts as a new sink.
 Add to H all edges leading into H.
s1
v2
v1
s3
u3=6𝟙[1.5,2]
s2
t
H

Multi-Sink: Existence

In multi-sink networks IDE flows always exist
(even for more general inflow rate functions ui).
  1. Given an IDE flow f up to some time θ0, extend f up to some time θ0+ε.
  2. Calculate the node-inflows at time θ0.
  3. Order nodes by their distance to sink t.
  1. Let K:={g|g extension of f on [θ0,θ0+τmin) (not necessarily IDE)}.
  2. Consider the mapping A:KL2([θ0,θ0+τmin))I×E,g=(gi,e)h=(hi,e),
    where hi,vw(θ):=distcw,ti(θ)+cvw(θ)distcw,ti(θ) =0vw is active
v
w
ti

Then: gK is IDE extension g,A(g)=0 A(g),gg0 f.a. gK

  1. Such a g always exists (A weak-strong-cont., K non-empty, closed, convex, bounded).
s1
s2
t2
t1

Multi-Sink: Termination

There exists a multi-sink network where all IDEs cycle.
s1
t1
s
s
s
Model Single-Sink Networks Multi-Sink Networks
Physical Behavioral Existence: Termination: Existence: Termination:
si
ti
f+i,e(θ)
qe(θ)
(τe,νe)
IDE-Flows only use currently shortest paths (active edges)
Dynamic Flows with Adaptive Route Choice Lukas Graf