Algorithmen für Routenplanung...Folie 27 – 18. Juni 2012 Institut für Theoretische Informatik Lehrstuhl Algorithmik. Eingabe Netzwerk Deutschland jVjˇ4:7 Mio., jEjˇ10:8 Mio

MICROSOFT RESEARCH SILICON VALLEY

Algorithmen für Routenplanung14. Vorlesung, Sommersemester 2012

Daniel Delling | 18. Juni 2012

KIT – Universität des Landes Baden-Württemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft

www.kit.edu

http://www.kit.edu

Abbiegeverbote/-kosten

bisher:Kreuzungen→ KnotenStrassen→ Kanten

aber:Abbiegen manchmal verbotenLinksabbiegen teurer als rechtsKosten U-Turns hochwurde als einfaches Modellierungsdetail abgetan

Daniel Delling – Algorithmen für RoutenplanungFolie 2 – 18. Juni 2012

Institut für Theoretische InformatikLehrstuhl Algorithmik

ModellierungMöglichkeit I:

Vergrössern des Graphen durch Ausmodellierungredundante Informationentferne einen Knoten pro Strassekantenbasierter Graph da

Strassen→ KnotenTurns→ Kanten

Möglichkeit II:behalte Kreuzungen als Knotenspeicher AbbiegetabelleBeobachtung: viele Knoten habendie gleiche Abbiegetabellealso speicher jede Tabelle einmal,Knoten speichern Tabellen-ID



Kantenbasierter Graph

Dijkstra:funktioniert ohne Anpassungmehr Knoten zu scannenFaktor 3 langsamer

CHfunktioniert ohne Anpassungaber grössere Anzahl Knoten/Kanten erhöht Vorberechungszeit

MLDAnzahl Schnittkanten erhöht sichSchnittkanten = Schnittknoteneventuell wechsel zu Knotenseparatoren?



Kompaktes Modell

Dijkstra:Turns müssen in den Suchalgorithmus integriert werdenKreuzungen können mehrfach gescannt werdenjede Kante wird höchstens einmal gescanntSuchraum gleich zu kantenbasiertem ModellVorteil: weniger Speicher für den Graphen

Optimierung:berechne für jede Kreuzung Schrankenreduziert Suchraum um einen Faktor 2



Kompaktes Modell

CHZeugensuche wird komplizierter

für jedes Paar eingehender und ausgehender Kanten muss eineZeugensuche durchgeführt werdenes können Self-Loops entstehen

⇒ Anpassung schwierig⇒ Zeugensuche schlägt häufig fehl



Kompaktes Modell

MLDSchnittkanten bleiben erhaltenSchnittkante→ 2 Knoten auf OverlayTurns müssen nur auf unterstem beachtet werdenauf Overlaygraphen: normaler Dijkstra

⇒ einfache Anpassung, aber Query wird komplizierter



Ergebnisse

Customization QueriesAlgorithm time [s] [MB] #scans time [ms]

1s

MLD-4 [28 : 212 : 216 : 220] 5.8 61.7 3556 1.18CH expanded 3407.4 880.6 550 0.18CH compact 849.0 132.5 905 0.19

100

s MLD-4 [28 : 212 : 216 : 220] 7.5 61.7 3813 1.28CH expanded 5799.2 931.1 597 0.21CH compact 23774.8 304.0 5585 2.11

Beobachtung:CH hat massive Probleme mit TurnsMLD kaum (einer der Hauptgründe für Entwicklung von MLD)



Diskussion

Wie historische Daten einbeziehen?



Zeitabhängiges Szenario

Szenario:Historische Daten fürVerkehrssituation verfügbarVerkehrssituation vorhersagbarBerechne schnellsten Weg bezüglichder erwarteten Verkehrssituation(zu einem gegebenen Startzeitpunkt)

Beobachtung:Kein konzeptioneller Unterschied zu Public TransportSomit Techniken übertragbar?Nein! Dazu bald mehr.



Herausforderung

Hauptproblem:Kürzester Weg hängt von Abfahrtszeitpunkt abEingabegröße steigt massiv an

Vorgehen:ModellierungAnpassung DijkstraAnpassung Beschleunigungstechniken

Heute:Modellierung und Dijkstra



Zeitabhängige Straßennetzwerke

Eingabe:Durchschnittliche Reisezeit zu bestimmten ZeitpunktenJeden Wochentag verschiedenSonderfälle: Urlaubszeit

departure

travel time

Somit an jeder Kante:Periodische stückweise lineareFunktionDefiniert durch StützpunkteInterpoliere linear zwischenStützpunkten



FIFO-Eigenschaft

DefinitionSei f : R+0 → R+0 eine Funktion. f erfüllt die FIFO-Eigenschaft, wennfür jedes ε > 0 und alle τ ∈ R+0 gilt, dass

f (τ) ≤ ε+ f (τ + ε).

DiskussionInterpretation: “Warten lohnt sich nie”Kürzeste Wege auf Graphen mit non-FIFO Funktionen zu findenist NP-schwer.(wenn warten an Knoten nicht erlaubt ist)

⇒ Sicherstellen, dass Funktionen FIFO-Eigenschaft erfüllen.



Diskussion

Eigenschaften:Topologie ändert sich nichtKanten gemischt zeitabhängig und konstantvariable (!) Anzahl Interpolationspunkte pro Kante

Beobachtungen:FIFO gilt auf allen Kantenspäter wichtig



Datenstruktur

firstEdge

targetNode

firstPoint

0

1 3 2 3 2 0

2 3 4 6

time

weight

0

6 8 12 18 20

3 5 4 5 3

8 9 10

2 5 2

−5

0

2

6 9 12 13 14

8 10 12

1 4 1

0 0

1 1

1

2

0

1 2

3

8:00 - 56:00 - 3

18:00 - 520:00 - 3

12:00 - 48:00 - 1

12:00 - 110:00 - 4

8:00 - 2

10:00 - 29:00 - 5

1

firstOutEdge

targetNode

firstPoint

0

1 3 2 3 2 0

2 3 4 6

time

weight

0

6 8 12 18 20

3 5 4 5 3

8 9 10

2 5 2

−5

0

2

6 9 12 13 14

8 10 12

1 4 1

0 0

1 1

sourceNode

lowerBound

firstInEdge 0 1 2 4 6

3

1

0

3

1

2

3

1

0

2

2

1



Anfrageszenarien

Zeit-Anfrage:finde kürzesten Weg für Abfahrtszeit τanalog zu Dijkstra?

Profil-Anfrage:finde kürzesten Weg für alle Abfahrtszeitpunkteanalog zu Dijkstra?



Zeit-Anfragen

Time-Dijkstra(G = (V ,E),s,τ )

dτ [s] = 01Q.clear(), Q.add(s,0)2

while !Q.empty() do3u ← Q.deleteMin()4for all edges e = (u, v) ∈ E do5

if dτ [u] + len(e, τ + dτ [u]) < dτ [v ] then6dτ [v ]← dτ [u] + len(e, τ + dτ [u])7pτ [v ]← u8if v ∈ Q then Q.decreaseKey(v ,dτ [v ])9else Q.insert(v ,dτ [v ])10



Diskussion Zeit-Anfragen

Beobachtung:Nur ein Unterschied zu DijkstraAuswertung der Kanten

non-FIFO Netzwerke:Im Kreis fahren kann sich lohnenNP-schwer (wenn warten an Knoten nicht erlaubt ist)Transportnetzwerke sind FIFO modellierbar (notfalls Multikanten)



Profil-Anfragen

Profile-Search(G = (V ,E),s)

d∗[s] = 01Q.clear(), Q.add(s,0)2

while !Q.empty() do3u ← Q.deleteMin()4for all edges e = (u, v) ∈ E do5

if d∗[u]⊕ len(e) � d∗[v ] then6d∗[v ]← min(d∗[u]⊕ len(e),d∗[v ])7if v ∈ Q then Q.decreaseKey(v ,d [v ])8else Q.insert(v ,d [v ])9



Diskussion Profile-Anfragen

Beobachtungen:Operationen auf FunktionenPriorität im Prinzip frei wählbar(d [u] ist das Minimum der Funktion d∗[u])Knoten können mehrfach besucht werden⇒ label-correcting

Herausforderungen:Wie effizient ⊕ berechnen (Linken)?Wie effizient Minimum bilden?



Operationen

Funktion gegeben durch:Menge von InterpolationspunktenI f := {(t f1,w f1), . . . , (t fk ,w fk )}

3 Operationen notwendig:AuswertungLinken ⊕Minimumsbildung



Auswertung

departure

travel timeEvaluation von f (τ):Suche Punkte mit ti ≤ τ und ti+1 ≥ τdann Evaluation durch

f (τ) = wi + (τ − ti) ·wi+1 − witi+1 − ti

Problem:Finden von ti und ti+1Theoretisch:

Lineare Suche: O(|I|)Binäre Suche: O(log2 |I|)

Praktisch:|I| < 30⇒ lineare SucheSonst: Lineare Suche mit Startpunkt τ

Π· |I|

wobei Π die Periodendauer ist



Linken

DefinitionSeien f : R+0 → R+0 und g : R+0 zwei Funktionen die dieFIFO-Eigenschaft erfüllen. Die Linkoperation f ⊕ g ist dann definiertdurch

f ⊕ g := f + g ◦ (id+f )

Oder(f ⊕ g)(τ) := f (τ) + g(τ + f (τ))



Linken

v wu

1216

7:00 8:00

11

16

7:00 8:00

7:00 8:00

24

32

8:16

7:45

Linken zweier Funktionen f und gf ⊕ g enthält auf jeden Fall{(t f1,w

f1 + g(t

f1 + w

f1)), . . . ,

(t fl ,w

fl + g(t

fl + w

fl ))}

Zusätzliche Interpolationspunktean t−1j mit f (t

−1j ) + t

−1j = t

gj

Füge (t−1j , f (t−1j ) + w

gj ) für

alle Punkte von g zu f ⊕ gDurch linearen Sweeping-Algorithmus implementierbar



Diskussion Linken

LaufzeitSweep AlgorithmusO(|I f |+ |Ig |)Zum Vergleich: Zeitunabhängig O(1)

SpeicherverbrauchGelinkte Funktion hat ≈ |I f |+ |Ig | Interpolationspunkte

Problem:Während Profilsuche kann ein Pfad mehreren Tausend KantenentsprechenShortcuts. . .



Merge von Funktionen

departure time

travel time

Minimum zweier Funktionen f und gFür alle (t fi ,w

fi ): behalte Punkt, wenn w

fi < g(t

fi )

Für alle (tgj ,wgj ): behalte Punkt, wenn w

gj < f (t

gj )

Schnittpunkte müssen ebenfalls eingefügt werden

Vorgehen:Linearer sweepEvaluiere, welcher Abschnitt obenChecke ob Schnittpunkt existiert



Diskussion Merge

LaufzeitSweep AlgorithmusO(|I f |+ |Ig |)Zum Vergleich: Zeitunabhängig: O(1)

SpeicherverbrauchMinimum-Funktion kann mehr als |I f |+ |Ig | Interpolationspunkteenthalten

Problem:Während Profilsuche werden Funktionen gemergtLaufzeit der Profilsuchen wird durch diese Operationen dominiert



Eingabe

Netzwerk Deutschland |V | ≈ 4.7 Mio., |E | ≈ 10.8 Mio.5 Verkehrszenarien:

Montag: ≈ 8% Kanten zeitabhängigDienstag - Donnerstag: ≈ 8%Freitag: ≈ 7%Samstag: ≈ 5%Sonntag: ≈ 3%



”Grad” der Zeitabhängigkeit

#delete mins slow-down time [ms] slow-downkein 2,239,500 0.00% 1219.4 0.00%Montag 2,377,830 6.18% 1553.5 27.40%DiDo 2,305,440 2.94% 1502.9 23.25%Freitag 2,340,360 4.50% 1517.2 24.42%Samstag 2,329,250 4.01% 1470.4 20.59%Sonntag 2,348,470 4.87% 1464.4 20.09%

Beobachtung:kaum Veränderung in SuchraumAnfragen etwas langsamer durch Auswertung



Profilsuchen

/Beobachtung:

Nicht durchführbar durch zu großen Speicherbedarf (> 32 GiBRAM)Interpoliert:

Suchraum steigt um ca. 10%Suchzeiten um einen Faktor von bis zu 2 500

⇒ inpraktikabel



Zusammenfassung

Zeitabhängige Netzwerke (Basics)Funktionen statt Konstanten an KantenOperationen werden teurer

O(log |I|) für AuswertungO(|I f |+ |Ig |) für Linken und MinimumSpeicherverbrauch explodiert

Zeitanfragen:Normaler DijkstraKaum langsamer (lediglich Auswertung)

Profilanfragennicht zu handhaben



LiteraturAbbiegekosten:

Robert Geisberger, Christian Vetter Efficient Routing in RoadNetworks with Turn CostsIn: Proceedings of the 10th International Symposium onExperimental Algorithms (SEA’11), 2011Daniel Delling, Andrew V. Goldberg, Thomas Pajor, RenatoWerneckCustomizable Route PlanningIn: Proceedings of the 10th International Symposium onExperimental Algorithms (SEA’11), 2011

Zeitabhänige RoutenplanungDaniel Delling:Engineering and Augmenting Route Planning AlgorithmsPh.D. Thesis, Universität Karlsruhe (TH), 2009.



Nächste Termine

Mittwoch, 20.6.2012Montag, 25.6.2012Montag, 2.7.2012



AbbiegekostenZeitabängige Routenplanung

Documents

Algorithmen für Routenplanung...Folie 27 – 18. Juni 2012 Institut für Theoretische Informatik Lehrstuhl Algorithmik. Eingabe Netzwerk Deutschland jVjˇ4:7 Mio., jEjˇ10:8 Mio