Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
INSTITUT FÜR THEORETISCHE INFORMATIK · ALGORITHMIK · PROF. DR. DOROTHEA WAGNER
Algorithmen für Routenplanung5. Sitzung, Sommersemester 2013
Julian Dibbelt | 6. Mai 2013
KIT – Universität des Landes Baden-Württemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft
www.kit.edu
Letztes Mal: ALT und Arc-Flags
Wie Suche zielgerichtet machen?Nichtbeachten von Kanten oder Knoten die in die “falsche”Richtung führenReihenfolge in der Knoten besucht werden ändern
Jetzt: ersteres
Julian Dibbelt – Algorithmen für RoutenplanungFolie 2 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Arc-Flags
Idee:partitioniere Graphen in k Zellenhänge Label mit k Bits an jede Kantegibt an, ob e für Ziele in Zielzelle T benötigt wird
Julian Dibbelt – Algorithmen für RoutenplanungFolie 3 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
RandknotenbäumeBeobachtung: Man muss durch Randknoten in die Zelle
setze Intra-Zellen Kanten auf trueeinen Rückwärts Dijkstra-Baum pro Randknoten bsetze Flagge AFregion(b)(e) = true wenn e Baumkante desBaums von b ist
1 1 1
1 1 1 1 1 1
1 1 11 0 0
100
1 101 1 0
Julian Dibbelt – Algorithmen für RoutenplanungFolie 4 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Zentralisierte Bäume
verallgemeinere Dijkstra:für jede Region r (mit Randknotenmenge Br )hänge Label l(u) der Größe |Br | an jeden Knoten uspeichert den Abstand d(u,b) für alle b ∈ Br
triviale Intialisierung der Randknoten, füge alle in Queue einnehme Knoten u aus der Queue (key: min{l(u})relaxiere Kanten (u, v):
erzeuge Label l durch l(u) + len(u, v)checke ob l das Label l(v) verbessert
breche ab, wenn keine Verbesserungen mehr möglich sindsetze Flagge auf true wenn d(u,b) + len(u, v) = d(v ,b) gilt
Julian Dibbelt – Algorithmen für RoutenplanungFolie 5 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Zentralisierte Bäume
Bemerkungen:Knoten können mehrfach besucht werden (label-correcting)Prioritäten der Knoten beliebig wählbar
z.B. Minimum über alle Einträge von u
hoher Speicherverbrauch durch n Label der Größe |Br |18 Mio. Knoten und 1000 Randknoten⇒ 72 GBteile Arbeit in mehrere Schritte mit maximal 100 Randknotenmeist Beschleunigung um Faktor 4 gegenüber Randknotenansatz
Julian Dibbelt – Algorithmen für RoutenplanungFolie 6 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Automatisches Setzen von Flaggen
0001
0001
000111111111
1111
Beobachtung:Für manche Kanten kann mandie Flaggen automatisch setzen
Angehangene Bäume:Kanten zur Wurzel hin haben alle Flaggen gesetztKanten von Wurzel weg haben nur eine Flagge gesetztAlso: Entferne Bäume vor Arcs-Flag-Berechnung aus GraphKnotenzahl verringert sich um 1 Drittel
Anmerkung: Alle Knoten eines angehangenen Baumes müssen zurgleichen Zelle wie dessen Wurzel gehören.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 7 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Partitionierung
Anforderungen:balanciert
mögliche Partitionen:GitterQuad-Baum
iterativ in 4 Zellen unterteilen
kd-BaumVerallgemeinerung vonQuad-Baum
weitere Anforderungen?
Julian Dibbelt – Algorithmen für RoutenplanungFolie 8 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Partitionierung
Anforderungen:ausbalanciertwenige Randknotenzusammenhängend
Black-Box Partitionierer (METIS, ...):benutzen keine Einbettungoft: teilen rekursiv Graphen in kTeile mit kleinem Schnittbringen gute Lösungen fürArc-Flags
Julian Dibbelt – Algorithmen für RoutenplanungFolie 9 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Suchraum
Julian Dibbelt – Algorithmen für RoutenplanungFolie 10 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Suchraum
Julian Dibbelt – Algorithmen für RoutenplanungFolie 10 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Diskussion
Vorteile:einfacher Anfrage Algorithmusleicht on-top auf bestehende Systeme zu setzenausreichende Beschleunigung
Nachteile:hohe Vorberechnungsdauerweitere?
Julian Dibbelt – Algorithmen für RoutenplanungFolie 11 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Coning-Effekt
Beobachtung:lange Zeit nur eine Kante wichtigdaher immer nur ein Knoten in derQueueaber: je näher an der Zelle, destomehr Kanten werden wichtigSuche fächert sich aufin Zelle werden dann alle Kantenrelaxiert
Zwei Ansätze:bidirektionale Flagsmulti-level Flags
Julian Dibbelt – Algorithmen für RoutenplanungFolie 12 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Bidirektionale Arc-Flags
Vorberechung:Vorwärts- und RückwärtsflaggenRückwärtsflaggen können analog für eingehende Kantenberechnet werdenVorberechungszeit in gerichteten Graphen erhöht sich umFaktor 2
Anfrage:bidirektional:
Vorwärtssuche relaxiert nur Kanten mit Flagge für TRückwärtssuche nur Kanten mit Flaggen für S
normales Stopp-Kriterium von bidirektionalem Dijkstra
Julian Dibbelt – Algorithmen für RoutenplanungFolie 13 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Bidirektionale Arc-Flags
Problem:Eindeutigkeit der Wegeeventuell nicht korrekt
Lösung:kommt in Straßengraphen kaum vordaher öffne Flaggen für alle möglichen Wege
Julian Dibbelt – Algorithmen für RoutenplanungFolie 14 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Bidirektionale Arc-Flags
Problem:Eindeutigkeit der Wegeeventuell nicht korrekt
Lösung:kommt in Straßengraphen kaum vordaher öffne Flaggen für alle möglichen Wege
Julian Dibbelt – Algorithmen für RoutenplanungFolie 14 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Bidirektionale Arc-Flags
Problem:Eindeutigkeit der Wegeeventuell nicht korrekt
Lösung:kommt in Straßengraphen kaum vordaher öffne Flaggen für alle möglichen Wege
Julian Dibbelt – Algorithmen für RoutenplanungFolie 14 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Bidirektionale Arc-Flags
Problem:Eindeutigkeit der Wegeeventuell nicht korrekt
Lösung:kommt in Straßengraphen kaum vordaher öffne Flaggen für alle möglichen Wege
Julian Dibbelt – Algorithmen für RoutenplanungFolie 14 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Suchraum
Nachteile?
Julian Dibbelt – Algorithmen für RoutenplanungFolie 15 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Suchraum
Nachteile?
Julian Dibbelt – Algorithmen für RoutenplanungFolie 15 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Suchraum
Nachteile?
Julian Dibbelt – Algorithmen für RoutenplanungFolie 15 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Multi-Level Arc-Flags
Problem:Anfragen in einer Zelle ohneBeschleunigungviele Real-Welt Anfragensind lokal
Multi-Level Arc-Flags:Multi-Level Partitionberechne partielle Flaggen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 16 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Multi-Level Arc-Flags
Problem:Anfragen in einer Zelle ohneBeschleunigungviele Real-Welt Anfragensind lokal
Multi-Level Arc-Flags:Multi-Level Partitionberechne partielle Flaggen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 16 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Multi-Level Arc-Flags
Problem:Anfragen in einer Zelle ohneBeschleunigungviele Real-Welt Anfragensind lokal
Multi-Level Arc-Flags:Multi-Level Partitionberechne partielle Flaggen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 16 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Multi-Level Arc-Flags
Problem:Anfragen in einer Zelle ohneBeschleunigungviele Real-Welt Anfragensind lokal
Multi-Level Arc-Flags:Multi-Level Partitionberechne partielle Flaggen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 16 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Multi-Level Arc-Flags
Vorberechnung:oberster Level wie gehabtauf unteren Leveln:
von jedem Randknoten führe Dijkstra aus, bis alleKnoten der Superzelle abgearbeitet worden sindsetze Flaggen für alle Kanten (u, v) für die u inSuperzelleHinweis: es reicht nicht, nur den Subgraphen derSuperzelle zu betrachten (Übungsaufgabe)
Anfragen:bestimme gemeinsamen Level l von u und twerte Flaggen auf dem Level l aus
Julian Dibbelt – Algorithmen für RoutenplanungFolie 17 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Suchraum
Julian Dibbelt – Algorithmen für RoutenplanungFolie 18 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Suchraum
Julian Dibbelt – Algorithmen für RoutenplanungFolie 18 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Datenstruktur
1 1 0
1 1 11 10
1001 0 0
Effizient Flaggen speichern?pro Kante eine FlaggeBeobachtung: AnzahlKombinationen begrenzt
Idee:speichere Flaggen in MatrixZeiger von Kanten auf die Matrixverringert Speicherverbrauch um einen Faktor 5
Julian Dibbelt – Algorithmen für RoutenplanungFolie 19 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Flaggenkompression
1 1 0
1 1 11 10
1001 0 0
Beobachtung:kippen eines Bits von 1auf 0 verbotenkippen eines Bits von 0auf 1 erlaubt (weiterhinkorrekt, eventuelllangsamer)
Idee:verringere Anzahl eindeutiger Arc-Flags durch kippendadurch Kompression der Matrixfinde “gutes” Mapping
Julian Dibbelt – Algorithmen für RoutenplanungFolie 20 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Flaggenkompression
1 1 0
1 1 11 10
Beobachtung:kippen eines Bits von 1auf 0 verbotenkippen eines Bits von 0auf 1 erlaubt (weiterhinkorrekt, eventuelllangsamer)
Idee:verringere Anzahl eindeutiger Arc-Flags durch kippendadurch Kompression der Matrixfinde “gutes” Mapping
Julian Dibbelt – Algorithmen für RoutenplanungFolie 20 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Flaggenkompression(Multi-Level, unidirektional)
0e+00 2e+05 4e+05 6e+05 8e+05
0.5
1.0
1.5
2.0
2.5
3.0
3.5
4.0
#Entfernte Flags
Lauf
zeit
Europagraph, Kostenfkt., Häufigkeitsfakt. 0,5
0.518118
3.90533
−−−
1_2_4_8_16_321_2_4_8_32_641_2_4_8_64_128
Julian Dibbelt – Algorithmen für RoutenplanungFolie 21 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Beobachtungen
kaum Verlust bis zu 60% entfernte Flaggengeringer Verlust bis zu 80% entfernte Flaggenkippen von niedrig-leveligen Flaggen billiger
Julian Dibbelt – Algorithmen für RoutenplanungFolie 22 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Zufallsanfragen: Anzahl Regionen
Prepro Querytime space # settled time spd
regions [min] [B/n] nodes [ms] up0 0 0 9 114 385 5 591.6 1.0200 1 028 19 2 369 1.6 3 494.8400 1 366 20 1 868 1.2 4 659.7600 1 723 21 1 700 1.1 5 083.3800 1 892 23 1 642 1.4 3 994.01000 2 156 25 1 593 1.1 5 083.3
Beobachtungen:lange Vorberechnunghohe Beschleunigunggeringer Speicherverbrauchmehr als 200 Regionen lohnt sich nicht
Julian Dibbelt – Algorithmen für RoutenplanungFolie 23 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Anfragen Arc-Flags I
●●●●●●
●
●●
●
●●●
●
●
●●●●●●●●●●●●
●●
●●●
●
●●
●
●●
●
●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●
●
●
●●
●
●
●●●
●
●●●●●● ●●●●●●
●
●
●●●●●●●●
●
●●●●●●●
●
●●●●
●●●●●●●
●
●
●●●●●●●
●
●
●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●
●
●●●●●●● ●●
●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●
●
●●●●●●●
●●
●
●
●●●
●
●●●
●
●●●●
●
●●●
●
●
●
●●●●●●●●●●●●●
●
●●
●
●●●●●●●●●
●●
●
●
●●●●●
●●●●
●●●●●
●●●
●
●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●
●●●●●
●
●
●
●●●●●●
●
●
●●
●
●
●●●●
●
●●
●●
●●●
●●●●●●
●
●●
●●
●●●●●●●●●
●
●
●●●
●
●●
●●
●
●●
●
●
●●●
●
●
●●
●
●
●●●●●
●●●
●
●
●●●
●
●●●
●
●●●●●●
●
●
●●●●●●●●●●
●●
●
●●
●
●
●●
●
●●●
●
●●●●
●●●●
●●●●●●
●
●●
●●●
●
●●●
●●●●●●
●
●●●
●●●
●●●●
●●
●
●●●
●
●
●●
●●
●●
●
●
●
●
●
●
●
●●
●
●●●●●●●●●
●
●●●●●●●
●
●●●●●
●●
●
●●
●
●
●●●
●●
●
●●
●●
●●●●
●
●●
●●●
●●●
●
●
●
●
●●
●
●
●●●●●●●
●
●●●●●
●
●●●●
●●●●●●●●●
●
●●●●●●●●
●●●●
●
●●●
●
●●●●
●
●●
●●●
●
●●
●
●
●●
●●●●●●
●
●●●
●
●●●●
●
●●●●
●
●
●●
●●●
●●
●
●●●●●●
●●●●●
●
●
●●
●
●
●
●
●●
●●●●●●
●
●●●●
●
●●●●●
●
●
●
●●●●●●●
●●●●
●
●
●
●
●●●
●
●●
●
●●●●●●●
●
●●●●●
●
●●●
●
●●●●●
●●
●
●●●●●
●
●
●
●
●
●
●●
●
●●●●●●
●●●●●●●●●●
●●
●
●●
●●●●●●
●
●●●
●
●●●●●●●
●●●
●●
●●●●●●●●●●
●●
●
●●●
●
●●●●
●
●●●
●
●
●●
●
●
●
●●●●●●●
●
●●●●●●
●
●
●
●●
●
●●●●●●●●●●●
●● ●●●●●●●●●●
●
●●●●●●●●●●
●●●●●●
●●
●●
●
●
●
●●●●●●●●●
●
●
●
●
●
●
●●●●●●●
●●●●●●●●●●●●●
●
●●●●●●●
●
●●●●●●●●●●
●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●●
●●●●
●
●●●●●●●●●
●
●●●●
●
●
●●●●
●
●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●
●
●●●
●●
●
●
●●
●
●●●●●
●
●●●●●●
●
●●●●●
●●
●●●●●●●●●●●●●●
●
●
●●●
●
●
●●●●●●●●
●
●●
●
●●
●●
●
●●
●●●●●●●
●
●
●
●●●●
●●
●
●
●●
●
●●
●●
●
● ●●
●
●
●●
●
●●●●●●●●●●●
●
●
●●
●
●●●
●
●●●●
●
●●●●●●●
●
●●●●
●
●●●●
●
●
●
●
●●
●
●●●●●
●
●
●●●●●
●●
●
●
●●●
●
●
●
●●●●●●
●●●●●●●
●
●● ●●●
●●
●●
●
●
●
●
●
●●●●
●●
●●
●
●●●●●●
●
●
●●●
●
●
●●
●●
●●●●
●●
●●●●●●●●●●
●
●
●●
●●●●●
●●●●●●●●
●
●
●●●
●
●
●
●
●●
●
●● ●●●
●
●●●●●●●●
●
●●●
●
●●●●●●●●●●
●
●
●
●
●
●
●●●
●
●●
●
●●
●
●
●
●
●●●●●●●●●●●●●●●●●
●●●●●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●●
●
●●●●●●
●
●
●●●●●●
●
●●●
●
●
●●
●●
●
●●●●●●●●●●●●
●●
●●●●
●
●●●
●●
●
●
●●●
●
●
●●
●
●●●●●●●
●
●●●●●
●
●●●
●
●●●
●
●●●●●
●
●●●
●
●●
●●●●●●●●●●●●●●
●
●●●
●
●
●
●●
●●
●●●
●
●●
●●
●●●
●
●
●
●
●
●
●●●
●
●●●●●●
●
●●●
●
●●
●●●●●
●
●
●
●
●●●●
●●●●●●●
●
●
●
●
●
●●●
●
●
●●
●●●●●●●
●
●
●
●●●●●
●●●
●●●●
●
●●●●●●●●●
●
●
●●●
●
●
●●●●●
●
●●●
●
●●●●●●●
●
●●●
●
●
●
●
●●●
●
●
●●
●
●●●●●
●●
●●●●
●●●●●●
●
●
●
●
●
●●●●
●●
●
●
●
●●
●●●●●
●●
●●
●
●●●●●
●●
●
●
●
●●●●
●●●
●
●●●●●●●
●
●
●●
●
●
●●●
●
●
●●
●●●●●●
●
●
●●●
●
● ●●●
●
●●
●
●
●
●●●●
●
●
●
●
●●
●●
●
●●●
●
●
●●●●●●●●●●●●●●●
●
●●●●
●●●●●
●●
●
●●
●
●●
●
●
●
●●●●
●
●
●●●●●●●●
●●
●
●●●●
●
●
●●
●
●
●
●
●●
●
●
●
●●●●●●
●
●●●●
●●●●●●●●
●●
●●
●
●
●●●●●
●
●
●●●●●
●●
●
●●
●
●
●
●●●●
●
●●●
●●
●
●●
●
●
●
●
●
●●
●●
●●●
●
●
●
●●
●
●
●
●
●●
●●
●
●●●
●
●●●
●●●●
●●
●●●
●●
●
●●
●●●●
●●●
●
●●●
●●
●●●●
●
●●
●
●●
●
●●
●
●●●
●
●
●
●
●
●
●●●●
●
●●
●●
●
●●
●
●
●●
●
●
●
●
●
●
●
●●
●●●●●●
●
●●●
●●
●
●●
●
●●
●
●
●
●●●
●●●
●
●
●●
●●●
●
●
●●
●●
●
●
●
●
●●
●
●
●
●●
●●
●●
●
●
●●
●
●
●
●●
●
●
●
●
●●●
●
●
●
●
●●
●●●●●
●●
●
●
●
●
●●
●●
●
●
●
●●●
●
●
●●●
●
●
●●
●
●
●
●
●
●
●●
●●
●
●
●●
●
●
●
●
●
●
●
●●
●●
●
●●●●
●●
●
●●
●
●
●
●
●●●
●
●●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●●●●
●
●
●●●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●
●●●●●●●●
●
●
●●
●
●●
●
●●
●
●●
●●
●●
●●●
●●
●●●
●
●●
●
●●●●●
●●●●
●
●
●
●
●
●
●●
●●
●●
●
●
●
●●
●
●●
●●●●
●
●
●
●
●●
●
●●
●●
●●●
●●
●
●
●
●●●●
●
●●
●●●
●
●
●
●
●●
●●
●
●
●
●
●●●
●
●
●
●
●
●●
●
●●●●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●
●●●
●●
●●●●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●●
●
●
●●●
●
●
●
●●
●
●●
●●
●●●
●
●
●●
●●●
●
●
●
●●●●●
●
●
●
●
●
●
●
●
●●
●
●●
●
●
●
●●●●
●
●●●
●
●
●
●
●●
●
●●●●●●●
●
●
●
●
●
●
●●
●
●
●
●●●●
●
●●
●
●●
●●●●●
●●
●●
●●
●
●
●●
●
●
●
●●
●
●●●●●●●●●●●●●●●●●● ●
●●●●●●●●●● ●●●●●●●●●●●●
●●●
●●●●●●●●●●●●●●●●●●●●●● ●●●●
●● ●●●●●●●●
●●●●●●●●
●●●
●
●●●
●●●
●●●
●●
●●●●●●●●●●●●●●
●
●
●
●
●●
●
●
●
●●●●●
●●●
●●●
●●●●●
●
●
●
●●
●●
●
●
●
●
●●●●
●●●
●●
●●
●●
●
●
●
●
●●●●●
●●
●●●
●
●●
●●
●
●●●
●
●●●●●●●
●
●
●
●●
●
●●●
●
●●
●
●
●
●
●
●
●
●●●
●
●
●●●
●●
●●
●
●
●
●
●
●
●
●
●●
●
●●
●
●●●
●
●●●
●
●
●
●●●
●●●
●●●
●
●●
●
●
●
●
●
●●●
●●●●
●●●
●
●
●
●
●●
●
●
●
●
●
●●
●●
●
●
●●●●
●●
●
●
●
●●
●●
●●
●
●
●
●
●●●
●
●
●●●●●
●
●
●
●●
●
●
●
●
●●
●
●●
●
●●
●
●●●●●
●
●
●
●
●
●
●
●●●
●●
●
●
●●●
●
●●
●
●●●
●
●
●
●●●
●●●●●●
●●●●●
●●●●
●●●
●●
●●
●●●●●
●●
●●
●
●
●
●
●
●
●
●●●
●
●
●
●●
●●●●
●●●
●
●
●
●●
●●
●
●●●●
●●●
●
●
●
●
●●
●
●●
●
●
●●●●
●
●
●●●
●
●●
●●
●●●●●●
●
●●
●●
●
●●
●●
●●
●●●
●
●
●●
●
●●●●●
●
●●
●
●●
●
●
●●
●
●●●●●●●●●●
●
●●●●●●
●
●●●
●
●●●●●●●●● ●●●●●●●●
●●●
●
●●●●
●●●●
●
●●●●●●
●●●●●●●●●●
●●●●●●●●●●
●
●●●●●●
●
●
●●●●●●●●●●
●
●●●●●●●
●●●●●●●●●●●●
●●●●●●
●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●●●●●●●●●
●
●●●
●●
●●●●●●●
●●●●●●
●●
●
●
●●●●●●●●●●
●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●
●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●
●
●●●
●●●
●
●
●●●●
●●●
●●●●
●●
●
●
●●
●●
●
●
●
●●
●●●
●●●●
●
●●
●●
●●●●●
●●
●
●●●
●
●
●●
●
●
●●
●
●●
●●●●●●
●●
●●
●●●
●
●●●●
●●●●●●
●
●
●●
●●
●●●
●
●
●●●
●
●●
●
●
●●
●
●
●
●●●
●
●
●
●●
●
●●●
●
●
●
●●
●
●●●●●●●●
●●●
●●●
●●●
●●
●
●
●
●●
●
●●
●
●
●
●
●
●●
●●●●●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●●●●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●●
●●●
●
●
●
●●
●
●
●
●●●●●●
●●
●
●
●●
●●●●●
●
●
●
●
●●●●
●
●●
●●
●●●
●
●
●
●
●
●●
●
●●●
●
●●●
●●●
●●
●
●
●●
●
●●●●●
●●●
●
●●
●
●
●
●●●
●●●●●
●
●
●●●●●
●
●●●●●●●
●●●●●
●
●●●
●
●
●●●●●●
●
●●
●
●●●
●
●●●●●
●
●●●●●●●●●
●
●
●
●
●●●
●
●●
●
●●●●
●●●●●
●●
●
●●●
●
●●
●
●●
●
●
●●●●●●●
●●●●●●●●●●●
●
●
●
●●
●
●
●●●●
●
●
●●
●●●
●
●●
●
●●●●●
●●●
●
●●●●●●
●●●
●●●
●
●
●
●●●●●●●●
●●●●●●
●
●
●●●●●
●
●
●●●
●●●●●●●●●●●●●●●
●●●●
●
●
●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●●●
●●●●●●●
●●●●●
●●●
●
●
●
●
●●●●●
●●●●●●●●
●●●
●
●●
●●●●●●●●●●●●
●
●
●●●●●
●
●●●
●
●
●●●
●
●●●●●●●
●●●●●●●●●●
●●●●●●●●
●
●●●
●
●
●●●●●●●●
●●●●
●
●
●
●
●
●●●
Dijkstra Rank
Que
ry T
ime
[ms]
20 21 22 23 24 25 26 27 28 29 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
0.01
0.1
13
1010
010
0010
000
DijkstraArc−Flags (128 regions)bidirectional Arc−Flags (128 regions)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 24 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Anfragen Arc-Flags I
●●●●
●
●●●●●●●
●
●
●
●●●●●●●
●
●●●●●●●●
●
●●●●●
●
●●●●●●●●●●
●
●●●
●
●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●●●●
●●
●●●
●
●●●●●●●●●●●
●
●●●●
●●
● ●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●
●
●
●
●●●●
●
●●●●●●
●
●●●●●●●●●●●●●●
●●●●●●
●
●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●●●●●●
●
●
●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●
●
●
●●●●●●●●●●
●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●
●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●
●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●
●●●●●
●
●●●●●
●
●●●●●
●
●
●
●●●● ●●●●●●●●●
●
●●●●●●●●
●●
●●●
●
●●●●●●●● ●●●●●●●●
●
●●●●
●●●●●●●●●●
●
●●●●●
●
●●●●●●●
●●●●●●●●●●●
●
●●●●●●
●
●
●●●●●●●●●●●●
●
●●●●●●●● ●●●●●●●●●●
●●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●
●●●●●●●●●●●●●●●●●●●●
●
●
●
●
●
●●
●
●●
●
●●
●
●
●●●
●
●●
●
●●
●
●
●
●
●
●●●
●
●
●●●●
●●
●
●
●
●
●●●
●●
●
●
●
●
●●●●●●●●
●
●●●●
●
●
●
●●
●●
●●●●
●
●●●●●●●●
●●
●
●●
●
●
●●
●
●●●●●●●
●●●●●●
●
●●
●
●
●●
●●●
●●
●●●
●●●●
●●
●
●
●
●
●●●●●●●
●
●●
●●●●●
●●●
●
●●●●
●
●
●●●●●●●●
●
●●●
●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●
●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●
●●●●●●●●●●●●●
●
●●●
●
●
●
●●
●
●●●
●
●
●
●●
●●
●●●
●●
●
●●
●●●●
●●
●
●●
●
●
●●
●
●
●
●
●
●●
●●●
●
●
●●
●
●●●●●●
●
●●
●
●●●●●●●
●
●
●●
●●
●
●
●
●
●
●●●
●
●●●●
●
●
●●●
●
●●
●
●●●●●
●
●●●●●●
●●
●●●
●●●
●●
●●●●
●●●●●
●
●●●●
●●
●
●
●
●●●●
●●
●
●●
●●
●●
●
●
●●
●●
●●●
●●
●●●●
●
●
●●●
●
●●●
●
●
●●●
●
●●
●
●
●
●
●●
●●●●●
●●●
●
●
●
●
●●●●
●
●
●
●
●
●●●●
●
●
●
●
●
●●
●
●
●
●●●
●
●
●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●
●
●
●
●
●
●
●
●
●●
●
●
●
●●
●●●●●●●
●
●●
●
●●
●
●
●
●●
●
●●
●●
●●●●●●●
●● ●
●
●●
●
●
●●
●
●
●
●
●
●
●
●●●
●
●●●●
●
●●●
●●
●●●
●
●
●●
●
●
●
●●
●●
●●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●●
●
●
●
●
●
●●●
●
●
●
●●
●●
●
●●●
●●
●●●
●
●
●●
●●
●●●
●●●●
●●
●
●
●
●
●●
●
●
●●
●
●
●●●●
●
●●
●
●●
●
●●●
●
●●
●
●
●●
●
●
●●●
●●●●●
●
●●●
●●●
●
●
●●●●●●
●●●
●●●
●
●●
●
●
●●●●●●●
●
●
●●●
●
●●●●
●
●
●●●●
●●
●●●●●●
●
●
●●
●
●
●
●
●●●●●●●
●
●
●
●
●●
●●●
●
●●●
●●●
●●●
●●
●●●●●●●●●●●●●●
●
●
●
●
●●
●
●
●
●●●●●
●●●
●●●
●●●●●
●
●
●
●●
●●
●
●
●
●
●●●●
●●●
●●
●●
●●
●
●
●
●
●●●●●
●●
●●●
●
●●
●●
●
●●●
●
●●●●●●●
●
●
●
●●
●
●●●
●
●●
●
●
●
●
●
●
●
●●●
●
●
●●●
●●
●●
●
●
●
●
●
●
●
●
●●
●
●●
●
●●●
●
●●●
●
●
●
●●●
●●●
●●●
●
●●
●
●
●
●
●
●●●
●●●●
●●●
●
●
●
●
●●
●
●
●
●
●
●●
●●
●
●
●●●●
●●
●
●
●
●●
●●
●●
●
●
●
●
●●●
●
●
●●●●●
●
●
●
●●
●
●
●
●
●●
●
●●
●
●●
●
●●●●●
●
●
●
●
●
●
●
●●●
●●
●
●
●●●
●
●●
●
●●●
●
●
●
●●●
●●●●●●
●●●●●
●●●●
●●●
●●
●●
●●●●●
●●
●●
●
●
●
●
●
●
●
●●●
●
●
●
●●
●●●●
●●●
●
●
●
●●
●●
●
●●●●
●●●
●
●
●
●
●●
●
●●
●
●
●●●●
●
●
●●●
●
●●
●●
●●●●●●
●
●●
●●
●
●●
●●
●●
●●●
●
●
●●
●
●●●●●
●
●●
●
●●
●
●
●●
●
●●●●●●●●●●
●
●●●●●●
●
●●●
●
●●●●●●●●● ●●●●●●●●
●●●
●
●●●●
●●●●
●
●●●●●●
●●●●●●●●●●
●●●●●●●●●●
●
●●●●●●
●
●
●●●●●●●●●●
●
●●●●●●●
●●●●●●●●●●●●
●●●●●●
●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●●●●●●●●●
●
●●●
●●
●●●●●●●
●●●●●●
●●
●
●
●●●●●●●●●●
●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●
●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●
●
●●●
●●●
●
●
●●●●
●●●
●●●●
●●
●
●
●●
●●
●
●
●
●●
●●●
●●●●
●
●●
●●
●●●●●
●●
●
●●●
●
●
●●
●
●
●●
●
●●
●●●●●●
●●
●●
●●●
●
●●●●
●●●●●●
●
●
●●
●●
●●●
●
●
●●●
●
●●
●
●
●●
●
●
●
●●●
●
●
●
●●
●
●●●
●
●
●
●●
●
●●●●●●●●
●●●
●●●
●●●
●●
●
●
●
●●
●
●●
●
●
●
●
●
●●
●●●●●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●●●●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●●
●●●
●
●
●
●●
●
●
●
●●●●●●
●●
●
●
●●
●●●●●
●
●
●
●
●●●●
●
●●
●●
●●●
●
●
●
●
●
●●
●
●●●
●
●●●
●●●
●●
●
●
●●
●
●●●●●
●●●
●
●●
●
●
●
●●●
●●●●●
●
●
●●●●●
●
●●●●●●●
●●●●●
●
●●●
●
●
●●●●●●
●
●●
●
●●●
●
●●●●●
●
●●●●●●●●●
●
●
●
●
●●●
●
●●
●
●●●●
●●●●●
●●
●
●●●
●
●●
●
●●
●
●
●●●●●●●
●●●●●●●●●●●
●
●
●
●●
●
●
●●●●
●
●
●●
●●●
●
●●
●
●●●●●
●●●
●
●●●●●●
●●●
●●●
●
●
●
●●●●●●●●
●●●●●●
●
●
●●●●●
●
●
●●●
●●●●●●●●●●●●●●●
●●●●
●
●
●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●●●
●●●●●●●
●●●●●
●●●
●
●
●
●
●●●●●
●●●●●●●●
●●●
●
●●
●●●●●●●●●●●●
●
●
●●●●●
●
●●●
●
●
●●●
●
●●●●●●●
●●●●●●●●●●
●●●●●●●●
●
●●●
●
●
●●●●●●●●
●●●●
●
●
●
●
●
●●●
Dijkstra Rank
Que
ry T
ime
[ms]
20 21 22 23 24 25 26 27 28 29 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
0.01
0.1
13
1010
010
0010
000
bidirectional Dijkstrabidirectional Arc−Flags (16 regions)bidirectional Arc−Flags (128 regions)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 25 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Beobachtungen
birektionale Arc-Flags deutlich schneller als unidirektionalegegenüber Dijkstra nur Beschleunigung für weite Anfragen128 Regionen deutlich besser 16 (bei 224 nahezu gleich auf)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 26 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Übersicht: bisherige Techniken
Vorberechnung AnfrageZeit Platz Such Zeit
[h:m] [byte/n] raum [ms] Beschl.Dijkstra 0:00 0 9 114 385 5 591.6 1.0Bi-Dijkstra 0:00 0 4 764 110 2 713.2 2.1Uni-ALT-16 1:25 128 815 639 327.6 17.1Uni-ALT-64 1:08 512 604 968 288.5 19.4Bi-ALT-16 1:25 128 74 669 53.6 104.3Bi-ALT-64 1:08 512 25 324 19.6 285.3Uni Arc-Flags (128) 8:34 10 92 545 31.9 175.3Bi Arc-Flags (128) 17:08 20 2 764 0.8 6 988.1
Beobachtung:ALT: deutlich unterlegen bei Anfragen und PlatzverbrauchArc-Flags: deutlich längere Vorberechnungszeiten
Julian Dibbelt – Algorithmen für RoutenplanungFolie 27 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Anfragen Vergleich
●●●●
●
●●●●●●●
●
●
●
●●●●●●●
●
●●●●●●●●
●
●●●●●
●
●●●●●●●●●●
●
●●●
●
●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●
●
●
●●●●
●●
●●●
●
●●●●●●●●●●●
●
●●●●
●●
● ●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●
●
●
●
●●●●
●
●●●●●●
●
●●●●●●●●●●●●●●
●●●●●●
●
●●●●●●●
●
●●●●●●●●●●●●●●●
●
●●●●●●●
●
●
●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●
●
●
●●●●●●●●●●
●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●
●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●
●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●
●●●●
●
●●
●
●●●●●●
●
●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●
●●●●
●
●●● ●●
●
●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●
●●●●●●●●●●
●
●
●
●●
●
●
●●●●●●
●
●●●●●●●●●●
●●●●●●●
●
●●●●●●●●●●
●
●●●●●●●●●●●●●●●
●●●
●
●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●
●
●●●●●●●
●
●●●●●●●●●●●●●●●●●●●
●●●
●●●●●●●
●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●
●
●●
●
●
●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●
●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●●●●
●●●●●●●●●●
●
●
●●●●
●
●●●●●●●●●●●
●●●●●●●●●
●●●●●●●●
●●●●●●●●●●●
●
●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●●● ●
●
●●●●●●
●●●●●●●●●●●●
●
●●●●●●●●
●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●
●
●
●●●●●●●●●●●●
●●●●●●●●●●
●●●
●●●●●
●●●●
●
●●
●●
●
●●●●●
●●●●
●
●●●●●●●●●●
●
●
●●●●
●
●●●●●●●●●●●●●
●
●●●●●●●
●●
●●
●
●●●●
●●●
●
●●●●●
●●●●●●●
●
●●●●●●
●●●●
●
●
●
●
●●●●●
●●●●●●●●●●●●●●●
●●
●●●●●●
●●●
●●
●
●
●●
●●●●
●
●
●●
●●●●●●
●●●●●●●●●
●●●●●●●●●●●●●●●
●
●●
●●●●
●
●
●●
●●●
●●●●●●●
●
●●
●●●●●
●
●
●●●●●●
●
●
●
●
●
●●●●●
●●●●
●
●
●
●●
●●
●●●
●
●●●
●●
●
●●
●
●
●
●●
●
●●
●●●
●
●●●●
●●●●●
●●●●
●●
●●●●●●●●●
●
●
●●
●●●●●●●●●●●●●
●●
●
●●
●●
●●●●●●●
●
●
●
●●
●
●
●
●
●●●●●
●●
●●
●●●●●●
●●●●●
●●
●●●●●●●●
●
●
●
●
●
●●●
●
●●●●●●●●●
●●●
●
●●●●
●●●●●●●●●●
●
●●●●
●●●●●●●
●●●●●
●●
●●●●
●●●
●
●
●
●
●
●●
●
●●●
●
●
●●●●
●●●●●●
●
●●
●●●●●●
●●
●●
●●
●
●●●
●
●
●
●
●●●●●●●●
●
●●●●●
●●●●●
●●●●●●
●●
●●
●●
●●●●●●
●●●●●
●●●
●●●●
●
●●
●●●●●●●●
●●●
●●
●
●●●
●
●●●●●●
●●●●●●●●●●●●●●
●
●●●●●●●
●
●●
●●
●●
●●●
●●●●●●
●
●●●●●
●
●●●●●●●
●
●●●●
●●
●●●
●
●
●
●
●●●
●
●●●●
●
●
●●●●●
●
●●
●
●
●
●
●●
●●●
●
●●●
●●●
●
●●●
●●●
●
●
●●
●●●●
●●●
●●●●
●
●●
●●
●●●
●
●●●
●
●
●●●
●●
●
●●●●
●●
●●●●●●●●●
●●●●●●●●●●●●●●
●
●
●●
●
●
●
●●
●
●●
●
●●●●●●●●●
●
●●●
●●●●●●
●
●
●
●
●●
●
●●
●●●●●●●
●
●●●●●●
●
●
●●
●
●
●
●
●●●●●●●●
●
●
●
●
●
●
●
●●
●
●●●
●
●●●
●●●
●●●
●●
●●●●●●●●●●●●●●
●
●
●
●
●●
●
●
●
●●●●●
●●●
●●●
●●●●●
●
●
●
●●
●●
●
●
●
●
●●●●
●●●
●●
●●
●●
●
●
●
●
●●●●●
●●
●●●
●
●●
●●
●
●●●
●
●●●●●●●
●
●
●
●●
●
●●●
●
●●
●
●
●
●
●
●
●
●●●
●
●
●●●
●●
●●
●
●
●
●
●
●
●
●
●●
●
●●
●
●●●
●
●●●
●
●
●
●●●
●●●
●●●
●
●●
●
●
●
●
●
●●●
●●●●
●●●
●
●
●
●
●●
●
●
●
●
●
●●
●●
●
●
●●●●
●●
●
●
●
●●
●●
●●
●
●
●
●
●●●
●
●
●●●●●
●
●
●
●●
●
●
●
●
●●
●
●●
●
●●
●
●●●●●
●
●
●
●
●
●
●
●●●
●●
●
●
●●●
●
●●
●
●●●
●
●
●
●●●
●●●●●●
●●●●●
●●●●
●●●
●●
●●
●●●●●
●●
●●
●
●
●
●
●
●
●
●●●
●
●
●
●●
●●●●
●●●
●
●
●
●●
●●
●
●●●●
●●●
●
●
●
●
●●
●
●●
●
●
●●●●
●
●
●●●
●
●●
●●
●●●●●●
●
●●
●●
●
●●
●●
●●
●●●
●
●
●●
●
●●●●●
●
●●
●
●●
●
●
●●
●
●●●●●●●●●●
●
●●●●●●
●
●●●
●
●●●●●●●●● ●●●●●●●●
●●●
●
●●●●
●●●●
●
●●●●●●
●●●●●●●●●●
●●●●●●●●●●
●
●●●●●●
●
●
●●●●●●●●●●
●
●●●●●●●
●●●●●●●●●●●●
●●●●●●
●●●●●●●●●●●●●●●●●●●
●
●●●
●
●●●●●●●●●●●●●●●●●●●●●●●●●●
●
●●●●●●●●●
●●●●●●●●●
●
●●●
●●
●●●●●●●
●●●●●●
●●
●
●
●●●●●●●●●●
●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●●●
●●●●●●●●●●●●●
●●●●●●●●●●
●●●●●
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●● ●●
●
●●●
●●●
●
●
●●●●
●●●
●●●●
●●
●
●
●●
●●
●
●
●
●●
●●●
●●●●
●
●●
●●
●●●●●
●●
●
●●●
●
●
●●
●
●
●●
●
●●
●●●●●●
●●
●●
●●●
●
●●●●
●●●●●●
●
●
●●
●●
●●●
●
●
●●●
●
●●
●
●
●●
●
●
●
●●●
●
●
●
●●
●
●●●
●
●
●
●●
●
●●●●●●●●
●●●
●●●
●●●
●●
●
●
●
●●
●
●●
●
●
●
●
●
●●
●●●●●
●
●
●●
●●●
●
●
●
●
●
●
●
●
●●●●
●
●
●●
●
●
●
●
●●
●
●
●
●
●
●
●
●●
●
●●
●●●
●
●
●
●●
●
●
●
●●●●●●
●●
●
●
●●
●●●●●
●
●
●
●
●●●●
●
●●
●●
●●●
●
●
●
●
●
●●
●
●●●
●
●●●
●●●
●●
●
●
●●
●
●●●●●
●●●
●
●●
●
●
●
●●●
●●●●●
●
●
●●●●●
●
●●●●●●●
●●●●●
●
●●●
●
●
●●●●●●
●
●●
●
●●●
●
●●●●●
●
●●●●●●●●●
●
●
●
●
●●●
●
●●
●
●●●●
●●●●●
●●
●
●●●
●
●●
●
●●
●
●
●●●●●●●
●●●●●●●●●●●
●
●
●
●●
●
●
●●●●
●
●
●●
●●●
●
●●
●
●●●●●
●●●
●
●●●●●●
●●●
●●●
●
●
●
●●●●●●●●
●●●●●●
●
●
●●●●●
●
●
●●●
●●●●●●●●●●●●●●●
●●●●
●
●
●●●●●●●●●●●●●●●
●
●●●●●●●●●●●●●●●●●
●●●
●●●●●●●
●●●●●
●●●
●
●
●
●
●●●●●
●●●●●●●●
●●●
●
●●
●●●●●●●●●●●●
●
●
●●●●●
●
●●●
●
●
●●●
●
●●●●●●●
●●●●●●●●●●
●●●●●●●●
●
●●●
●
●
●●●●●●●●
●●●●
●
●
●
●
●
●●●
Dijkstra Rank
Que
ry T
ime
[ms]
20 21 22 23 24 25 26 27 28 29 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224
0.01
0.1
13
1010
010
0010
000
bidirectional Dijkstrabidirectional ALTbidirectional Arc−Flags (128 regions)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 28 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Zusammenfassung
Arc-FlagsTeile Graphen in k RegionenFlaggen zeigen an, ob Kante wichtig für Zielregion istEinfacher Anfrage-AlgorithmusVorberechnung
Kürzeste-Wege-Baum von jedem RandknotenManche Flaggen können automatisch gesetzt werden
Bidirektional und multi-level ErweiterungenBeschleunigung von bis zu 7000Nahe Anfragen nicht schneller als DijkstraVorberechnung dauert allerdings (immer noch) ca. 1 Tag
Julian Dibbelt – Algorithmen für RoutenplanungFolie 29 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Literatur
Literatur (Arc-Flags):
Moritz Hilger and Ekkehard Köhler and Rolf H. Möhring andHeiko Schilling:Fast Point-to-Point Shortest Path Computations withArc-FlagsIn: Shortest Paths: Ninth DIMACS Implementation Challenge,2009
Julian Dibbelt – Algorithmen für RoutenplanungFolie 30 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Partitionierung
Anforderungen:ausbalanciertwenige Randknotenzusammenhängend
Black-Box Partitionierer:benutzen keine Einbettungoft: teilen rekursiv Graphen in kTeile mit kleinem Schnittlassen sich auf eine VielzahlGraphklassen anwendenheute (Exkurs): spezielleStrassengraph-Partitionierer
Julian Dibbelt – Algorithmen für RoutenplanungFolie 31 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Graph Partitionierung
Informell: teile Graphen in lose verbundene Regionen (Zellen).
Julian Dibbelt – Algorithmen für RoutenplanungFolie 32 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Graph Partitionierung
Formale definition:Eingabe: ungerichteter graph G = (V ,E)Ausgabe: Partition von V in Zellen V1, V2, . . . , Vk
Ziel: minimale Anzahl Kanten zwischen Zellen
Standard Variante: |Vi | ≤ U für festes U:Anzahl Zellen kann variieren (≥ dn/Ue).
Balancierte Variante: k Zellen und Unausgeglichenheit ε:genau k Zellen (können unzusammenhängend sein) Zellen,Grösse ≤ (1 + ε)dn/Ue.
beides NP schwer⇒ benutze Heuristiken
Julian Dibbelt – Algorithmen für RoutenplanungFolie 33 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Graph Partitionierung
Formale definition:Eingabe: ungerichteter graph G = (V ,E)Ausgabe: Partition von V in Zellen V1, V2, . . . , Vk
Ziel: minimale Anzahl Kanten zwischen Zellen
Standard Variante: |Vi | ≤ U für festes U:Anzahl Zellen kann variieren (≥ dn/Ue).
Balancierte Variante: k Zellen und Unausgeglichenheit ε:genau k Zellen (können unzusammenhängend sein) Zellen,Grösse ≤ (1 + ε)dn/Ue.
beides NP schwer⇒ benutze Heuristiken
Julian Dibbelt – Algorithmen für RoutenplanungFolie 33 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Generelle VerfahrenMETIS [KK99]SCOTCH [PR96]DiBaP [MMS09]Kappa [HSS10], KaSPar [OS10], Kaffpa [SS11], KaffpaE [SS12]
Julian Dibbelt – Algorithmen für RoutenplanungFolie 34 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Natural Cuts
Strassengraphen: dichte Regionen (Gitter) abwechselnd mitnatürlichen SchnittenFlüsse, Berge, Wüsten, Wälder, Parks, Grenzen, Autobahnen, . . .
PUNCH: Partitioner Using Natural-Cut Heuristics
Julian Dibbelt – Algorithmen für RoutenplanungFolie 35 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Übersicht
1 Ausdünnung:entspricht “match + contract” auf Folie 34
finde natürliche Schnitte (auf richtigerSkala)behalte Schnittkanten, kontrahiere alleanderen
2 Zusammensetzen:partitioniere (kleineren) kontrahierten graph“initial partitioning”greedy + lokale Suche [+ Kombinationen]“uncontract + local improvements”
Julian Dibbelt – Algorithmen für RoutenplanungFolie 36 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Übersicht
1 Ausdünnung:entspricht “match + contract” auf Folie 34
finde natürliche Schnitte (auf richtigerSkala)behalte Schnittkanten, kontrahiere alleanderen
2 Zusammensetzen:partitioniere (kleineren) kontrahierten graph“initial partitioning”greedy + lokale Suche [+ Kombinationen]“uncontract + local improvements”
Julian Dibbelt – Algorithmen für RoutenplanungFolie 36 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Schnitte: DefinitionenSchnitt
Partition des Graphen in 2 Teile (V1, V2)Grösse: Anzahl Schnittkanten (|S|)
Minimaler s-t Schnittentferne minimale Anzahl Kanten, so dass s und t im Graphennicht mehr verbunden sindkann in maximalen Fluss überführt werdenin Polynomialzeit zu berechnen
Dünnster SchnittSchnitt mit |S|/min{|V1|, |V2|} minimalNP schwer
Exact Graph BisectionSchnitt mit |S| minimal und |V1|, |V2| < d|V |/2eNP schwer
Julian Dibbelt – Algorithmen für RoutenplanungFolie 37 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Finde Natürliche Schnitte
Wir brauchen dünne Schnittezwischen dichten Regionen:
Dünnster Schnitt?Zu aufwendig.
Berechne minimalen s-t Schnitt (fürzufälliges s, t)?
Meist trivial: Knotengrade sind klein.
Wir brauchen was anderes:s-t Schnitte zwischen Regionen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 38 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Finde Natürliche Schnitte1 Wähle ein Zentrum v .2 Breitensuche der Grösse U um v :
Erste U/10 Knoten: KernVerbliebene Knoten in der Queue:Ring
3 Finde minimum Kern/Ring Schnitt:standard s–t minimaler Schnitt.
4 Wiederhole für verschiedene“zufällige” v :
bis jeder Knoten in ≥ 2 Kernen war
v
Berechene kleine Schnitte extra:identifiziere 1- and 2-Schnittereduziert Strassengraph um Faktor 2beschleunigt Schnittfindung
Julian Dibbelt – Algorithmen für RoutenplanungFolie 39 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Finde Natürliche Schnitte1 Wähle ein Zentrum v .2 Breitensuche der Grösse U um v :
Erste U/10 Knoten: KernVerbliebene Knoten in der Queue:Ring
3 Finde minimum Kern/Ring Schnitt:standard s–t minimaler Schnitt.
4 Wiederhole für verschiedene“zufällige” v :
bis jeder Knoten in ≥ 2 Kernen war
v
U/10 nodes
Berechene kleine Schnitte extra:identifiziere 1- and 2-Schnittereduziert Strassengraph um Faktor 2beschleunigt Schnittfindung
Julian Dibbelt – Algorithmen für RoutenplanungFolie 39 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Finde Natürliche Schnitte1 Wähle ein Zentrum v .2 Breitensuche der Grösse U um v :
Erste U/10 Knoten: KernVerbliebene Knoten in der Queue:Ring
3 Finde minimum Kern/Ring Schnitt:standard s–t minimaler Schnitt.
4 Wiederhole für verschiedene“zufällige” v :
bis jeder Knoten in ≥ 2 Kernen war
v
U/10 nodes
U nodes
Berechene kleine Schnitte extra:identifiziere 1- and 2-Schnittereduziert Strassengraph um Faktor 2beschleunigt Schnittfindung
Julian Dibbelt – Algorithmen für RoutenplanungFolie 39 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Finde Natürliche Schnitte1 Wähle ein Zentrum v .2 Breitensuche der Grösse U um v :
Erste U/10 Knoten: KernVerbliebene Knoten in der Queue:Ring
3 Finde minimum Kern/Ring Schnitt:standard s–t minimaler Schnitt.
4 Wiederhole für verschiedene“zufällige” v :
bis jeder Knoten in ≥ 2 Kernen war
v
U/10 nodes
U nodes
Berechene kleine Schnitte extra:identifiziere 1- and 2-Schnittereduziert Strassengraph um Faktor 2beschleunigt Schnittfindung
Julian Dibbelt – Algorithmen für RoutenplanungFolie 39 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Eigenschaften der Ausdünung
1 viele Kanten werden nie geschnitten2 Schnittkanten partitionieren den Graphen in
Fragmente3 Fragmentgrösse ≤ U (meist viel kleiner)
Generiere Fragmentgraphen:Fragment→ gewichteter Knotenbenachbarte Fragmente→ gewichteteKante
U fragments frag size
4 096 605 864 3065 536 104 410 173
1 048 576 10 045 1 793(Europe: 18M nodes)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 40 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;
kombiniere adjazente Zellen;stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;
stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;
stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;
stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;
stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;
stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
KonstruktionsphaseFragmentgröße deutlich unterhalbvon U, Schnitt unnötig großFinde bessere Partition durchZusammenfassen von FragmentenAlgorithmus:
starte mit isolierten Fragmenten;kombiniere adjazente Zellen;stoppe wenn maximal.
Zufällig greedy:füge Fragmente zusammen, die stärker verbunden......im Verhältnis zu ihrer Grösse (= # Knoten, die sie repräsentieren).
Ergebnis okay, aber es geht besser.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 41 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Suche(Lokale Reoptimierung auf teilweise entpacktem Graphen)
Für paarweise benachbarte Zellen:Zerteilung in Fragments;lass konstruktiven, randomisiertenAlgorithmus auf Subproblem laufen;behalte Lösung wenn besser.
Variante benutzt auch Nachbarzellen:mehr Flexibilität;beste Ergebnisse (standard).
Nachbarzellen können auch inFragmente zerteilt werden:
Subprobleme zu gross;schlechtere Ergebnisse.
Evaluiere jedes Subproblem mehrmals (mit Zufall).
Julian Dibbelt – Algorithmen für RoutenplanungFolie 42 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Suche(Lokale Reoptimierung auf teilweise entpacktem Graphen)
Für paarweise benachbarte Zellen:Zerteilung in Fragments;lass konstruktiven, randomisiertenAlgorithmus auf Subproblem laufen;behalte Lösung wenn besser.
Variante benutzt auch Nachbarzellen:mehr Flexibilität;beste Ergebnisse (standard).
Nachbarzellen können auch inFragmente zerteilt werden:
Subprobleme zu gross;schlechtere Ergebnisse.
Evaluiere jedes Subproblem mehrmals (mit Zufall).
Julian Dibbelt – Algorithmen für RoutenplanungFolie 42 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Suche(Lokale Reoptimierung auf teilweise entpacktem Graphen)
Für paarweise benachbarte Zellen:Zerteilung in Fragments;lass konstruktiven, randomisiertenAlgorithmus auf Subproblem laufen;behalte Lösung wenn besser.
Variante benutzt auch Nachbarzellen:mehr Flexibilität;beste Ergebnisse (standard).
Nachbarzellen können auch inFragmente zerteilt werden:
Subprobleme zu gross;schlechtere Ergebnisse.
Evaluiere jedes Subproblem mehrmals (mit Zufall).
Julian Dibbelt – Algorithmen für RoutenplanungFolie 42 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Suche(Lokale Reoptimierung auf teilweise entpacktem Graphen)
Für paarweise benachbarte Zellen:Zerteilung in Fragments;lass konstruktiven, randomisiertenAlgorithmus auf Subproblem laufen;behalte Lösung wenn besser.
Variante benutzt auch Nachbarzellen:mehr Flexibilität;beste Ergebnisse (standard).
Nachbarzellen können auch inFragmente zerteilt werden:
Subprobleme zu gross;schlechtere Ergebnisse.
Evaluiere jedes Subproblem mehrmals (mit Zufall).
Julian Dibbelt – Algorithmen für RoutenplanungFolie 42 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Lokale Suche(Lokale Reoptimierung auf teilweise entpacktem Graphen)
Für paarweise benachbarte Zellen:Zerteilung in Fragments;lass konstruktiven, randomisiertenAlgorithmus auf Subproblem laufen;behalte Lösung wenn besser.
Variante benutzt auch Nachbarzellen:mehr Flexibilität;beste Ergebnisse (standard).
Nachbarzellen können auch inFragmente zerteilt werden:
Subprobleme zu gross;schlechtere Ergebnisse.
Evaluiere jedes Subproblem mehrmals (mit Zufall).
Julian Dibbelt – Algorithmen für RoutenplanungFolie 42 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Weitere Verbesserungen
Mehrfacher Test für jedesPaar
lokale Suche hatZufallskomponenten
Multistart:konstruktiv+lokale Suche;behalte beste Lösung.
Kombination:kombiniere mancheLösungen;merge + lokale Suche.
●
●
●
●
●●
●●
● ● ●
ASSEMBLY TIME (s)
CU
T S
IZE
1000
011
000
1200
013
000
1400
015
000
0.1 1 10 100 1000 10000
●
●●
●● ● ●
Local search retriesMultistartCombination
(Europe, U = 216)
längere Laufzeit→ bessere Lösungen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 43 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Laufzeit
● ● ● ● ● ● ●
Maximum cell size (U)
Tim
e (s
)
● ●
●
●
●
●
●
●
●
●
●● ● ●
●
● ●
●
●
●
●
020
4060
8010
012
014
016
018
020
0
210 212 214 216 218 220 222
Tiny cutsNatural cutsGreedy + Local searchTotal
Europe (18M vertices), 12 cores
Flaschenhalse: Aufbau für kleine U, Ausdünnung für grosse U
Julian Dibbelt – Algorithmen für RoutenplanungFolie 44 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Qualität
U A B B/√
U B/ 3√
U
1 024 895 16.8 0.52 1.664 096 3 602 27.6 0.43 1.73
16 384 14 437 45.6 0.36 1.8065 536 57 376 72.7 0.28 1.80
262 144 222 626 103.7 0.20 1.621 048 576 826 166 134.3 0.13 1.324 194 304 3 105 245 127.9 0.06 0.79
(Europe, 16 retries, no multistart/combination)U: maximal erlaubte Zellengrösse
A: durchschn. Zellengrösse der Lösungen
B: durchschn. Randknoten pro Zelle
Strassengraphen haben sehr kleine Separatoren
Julian Dibbelt – Algorithmen für RoutenplanungFolie 45 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
Andere Verfahren lösen balancierte Variante:finde k Zellen mit Grösse ≤ (1 + ε)dn/Ue.
Erweiterung von PUNCH:1 benutze standard PUNCH
mit U = (1 + ε)dn/Ue;2 wähle k Basis Zellen,
verteile den Rest (Multistart)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 46 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Balancierte Partitionen
PUNCH: bessere Lösungen...
K=4 K=16 K=64
Solution Quality
Rel
ativ
e cu
t siz
e (P
UN
CH
=1)
0.0
0.5
1.0
1.5
2.0
2.5
3.0
PUNCHKAFFPAKASPARKAPPASCOTCHMETIS
(Europe, ε = 0.03)
...in vernünftiger Zeit.
K=4 K=16 K=64
Running Times
Run
ning
Tim
e [s
]
050
010
0015
0020
0025
0030
00
PUNCHKAFFPAKASPARKAPPASCOTCHMETIS
(Europe, ε = 0.03)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 47 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Vancouver mit METIS
Julian Dibbelt – Algorithmen für RoutenplanungFolie 48 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Vancouver mit PUNCH
Julian Dibbelt – Algorithmen für RoutenplanungFolie 49 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Portland mit METIS
Julian Dibbelt – Algorithmen für RoutenplanungFolie 50 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Portland mit PUNCH
Julian Dibbelt – Algorithmen für RoutenplanungFolie 51 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Bemerkungen
reduziert Randknoten gegenüber METIS um mehr als Faktor 2Beschleunigung von Arc-Flags Vorberechnung um Faktor 2auch multi-level Partitionen berechnenbartop-down liefert beste Ergebnisse
dabei Vorteile gegenüber METIS sogar grösserWie weit vom Optimum entfernt?Wird für die Bing Routing Engine benutzt.
Julian Dibbelt – Algorithmen für RoutenplanungFolie 52 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Literatur
Literatur (Partitionierung):
George Karypis, Vipin Kumar:A Fast and High Quality Multilevel Scheme for PartitioningIrregular GraphsIn: SIAM Journal on Scientific Computing, 1998Peter Sanders, Christian Schulz:Distributed Evolutionary Graph PartitioningIn: ALENEX, 2012Daniel Delling, Andrew Goldberg, Ilya Razenshteyn, RenatoWerneck:Graph Partitioning with Natural CutsIn: IPDPS, 2011
Julian Dibbelt – Algorithmen für RoutenplanungFolie 53 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Hierarchische Techniken
Bisher: zielgerichtete SucheNächste Idee: Nutze “Hierarchie” im Graphen
in etwa: Seiten-, Haupt-, Land-, Bundesstraßen, Autobahnen
Ideensammlung:identifiziere wichtige Knoten mit Zentralitätsmaßüberspringe unwichtige Teile des Graphen
Jetzt: letzteres
Julian Dibbelt – Algorithmen für RoutenplanungFolie 54 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Overlay Graph
GegebenEingabegraph G = (V ,E , len)Knotenmenge V ⊇ VL
BerechneBerechne GL = (VL,EL, lenL), so dass Distanzen in GL wie in G
Wie VL wählen?
Heute: Randknoten
Julian Dibbelt – Algorithmen für RoutenplanungFolie 55 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Overlay Graph
GegebenEingabegraph G = (V ,E , len)Knotenmenge V ⊇ VL
BerechneBerechne GL = (VL,EL, lenL), so dass Distanzen in GL wie in G
Wie VL wählen?Heute: Randknoten
Julian Dibbelt – Algorithmen für RoutenplanungFolie 55 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
PartitionierungLetztes Mal: Strassengraphen haben natürliche Schnitte
Jeder Pfad durch eine Zelle betritt/verlässt die Zelle durch einenRandknoten
⇒ Minimiiere # Schnittkanten mit Zellgrösse ≤ U(Eingabeparameter)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 56 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ausnutzung der PartitionIdee: Berechne Distanzen zwischen Randknoten in jeder Zelle
Overlay Graph:RandknotenCliquen in jeder ZelleSchnittkanten
s
t
Suchgraph:Start- und Zielzelle......plus Overlaygraph.(bidirektionaler) Dijkstra
Example215 Knoten pro Zelle, 626 Zellen⇒ 34 k Knoten im Overlaygraphen
Julian Dibbelt – Algorithmen für RoutenplanungFolie 57 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ergebnisse
Worst-Case:Kanten scans: O(
∑cliques + 2 · cell size).
Grösse des Overlaygraphen is metrikunabhängig
Beispiel:
Metric Customization Queriesmetric time [s] space [MB] scans time [ms]
Travel time 20 10 45134 10Distance 20 10 47127 11
(partition: ≤ 214 nodes/cell)
West Europa (18 M nodes, 42 M edges)Intel Core-i7 920 (four cores at 2.67 GHz)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 58 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ergebnisse
Worst-Case:Kanten scans: O(
∑cliques + 2 · cell size).
Grösse des Overlaygraphen is metrikunabhängig
Beispiel:
Metric Customization Queriesmetric time [s] space [MB] scans time [ms]
Travel time 20 10 45134 10Distance 20 10 47127 11
(partition: ≤ 214 nodes/cell)
West Europa (18 M nodes, 42 M edges)Intel Core-i7 920 (four cores at 2.67 GHz)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 58 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Ergebnisse
Worst-Case:Kanten scans: O(
∑cliques + 2 · cell size).
Grösse des Overlaygraphen is metrikunabhängig
Beispiel:
Metric Customization Queriesmetric time [s] space [MB] scans time [ms]
Travel time 20 10 45134 10Distance 20 10 47127 11
(partition: ≤ 214 nodes/cell)
West Europa (18 M nodes, 42 M edges)Intel Core-i7 920 (four cores at 2.67 GHz)
Julian Dibbelt – Algorithmen für RoutenplanungFolie 58 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik
Nächste Termine
Mittwoch, 8.5.2013Montag, 13.5.2013
Julian Dibbelt – Algorithmen für RoutenplanungFolie 59 – 6. Mai 2013
Institut für Theoretische InformatikLehrstuhl Algorithmik