Dynamic Flows with Adaptive Route Choice
Lukas Graf1, Tobias Harks
1, Leon Sering
2
1 Augsburg University, 2 Technische Universität Berlin
Model
Physical Model
- Directed (Multi-)Graph G=(V,E)
- For all edges e∈E: length τe and capacity νe
- Commodities I with source node si, sink node ti
and constant inflow rate ui:[ai,bi]→R≥0
- Inflow > capacity ⟹ queues form
f+e(θ)>νe (length qe(θ))
s1
u1=𝟙[0,1]
v2
v1
v3
s2
u2=3⋅𝟙[0,1]
t1/2
(τe,νe)
f+e(θ)=3
qe(θ)=2
qe(θ)=1
ce(θ)=1+21
ce(θ)=1+11
Behavioral Model
The current travel time at time θ on edge e is: ce(θ):=τe+qe(θ)/ν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(θ)>0⟹distcv,t(θ)=cvw(θ)+distcw,t(θ)
(we call such an edge vw active)
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.
-
Given an IDE flow f up to some time θ,
extend f up to some time θ+ε.
-
Calculate node inflows at time θ.
-
Order nodes by their distance to sink t.
-
Distribute node inflow to active edges such that:
f+vw(θ)>0⟹distcv,t′(θ)=c′vw(θ)+distcw,t′(θ)
f+vw(θ)=0⟹distcv,t′(θ)≥c′vw(θ)+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 H⊆G 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).
- Given an IDE flow f up to some time θ0, extend f up to some time θ0+ε.
- Calculate the node-inflows at time θ0.
- Order nodes by their distance to sink t.
- Let K:={g|g extension of f on [θ0,θ0+τmin) (not necessarily IDE)}.
- Consider the mapping A:K→L2([θ0,θ0+τmin))I×E,g=(gi,e)↦h=(hi,e),
where hi,vw(θ):=distcw,ti(θ)+cvw(θ)−distcw,ti(θ) =0⟺vw is active
v
w
ti
Then: g∈K is IDE extension ⟺⟨g,A(g)⟩=0 ⟺⟨A(g),g′−g⟩≥0 f.a. g′∈K
- Such a g always exists (A weak-strong-cont., K non-empty, closed, convex, bounded).
Multi-Sink: Termination
There exists a multi-sink network where all IDEs cycle.
Conclusion:
stepwise extension:
order nodes by their distance to sink
↓
send flow to active edges by waterfilling
→ constructive
stepwise extension:
correct extension is solution to var. inequality:
⟨A(g),g′−g⟩≥0
→ non-constructive