Praktikum Routenplanung - Themenvorstellung ... · INSTITUT F ¨UR THEORETISCHE INFORMATIK ALGORITHMIK PROF. DR. DOROTHEA WAGNER Praktikum Routenplanung Themenvorstellung & Gruppeneinteilung,

INSTITUT FUR THEORETISCHE INFORMATIK · ALGORITHMIK · PROF. DR. DOROTHEA WAGNER

Praktikum RoutenplanungThemenvorstellung & Gruppeneinteilung, Wintersemester 2018/2019

Valentin Buchhold, Jonas Sauer, Tim Zeitz, Tobias Zundorf | 21. November 2018

KIT – Universitat des Landes Baden-Wurttemberg undnationales Großforschungszentrum in der Helmholtz-Gemeinschaft

www.kit.edu

http://www.kit.edu

Ergebnisse des Ubungsblatts

Gruppen:Daniel Seemaier, Alexander GellnerNina Zimbel, Max WolkDimitri Hohler, Adrian Feilhauer, Felix Diel

Valentin Buchhold, Jonas Sauer, Tim Zeitz, Tobias Zundorf – Praktikum RoutenplanungFolie 2 – 21. November 2018

Institut fur Theoretische InformatikLehrstuhl Algorithmik

Zeitplan

Wann? Wo? Was?

Heute SR -120 Themen & Gruppeneinteilung5.12. um 14:00 SR -120 Anfangsvortrage13.3. um 14:00 SR 301 Abschlussvortrage

31.3. — Abgabe Ausarbeitung



Git-Repo

Pro Gruppe ein Repohttps://i11git.iti.kit.edu/git/Praktika/Routenplanung/2018_2019/gruppenname

Wichtig:git config --global user.name "yourname"git config --global user.email "email"

Macht bitte nur Commits mit eurem AccountWir schauen uns die Commits an, um festzustellen, dass jedergleich viel in der Gruppe arbeitet.



https://i11git.iti.kit.edu/git/Praktika/Routenplanung/2018_2019/gruppenname

https://i11git.iti.kit.edu/git/Praktika/Routenplanung/2018_2019/gruppenname

Verbindliche Anmeldung

Wenn jetzt ein Student abbricht, dann ist das fur seine Gruppeein ProblemDeswegen: Verbindliche AnmeldungAbbrechen = Durchgefallen



Themen

Zu jedem Thema kriegt ihr 1-2 PaperIhr sollt Teile des Papers reimplementierenIhr sollt eine Auswahl der Experimente des Papers wiederholenIhr sollt euch ein paar zusatzliche Experimente ausdenken unddurchfuhrenDer Umfang des Themas hangt von der Gruppengroße ab→3er-Teams mussen mehr machen



Anfangsvortrage

Anfangsvortrage am 5.12. um 14:00 SR -12010min langIhr sollt eine sehr high-level Ubersicht fur eure Kollegen gebenIhr sollt einen groben Zeitplan vorstellenIhr sollt uns davon uberzeugen, dass ihr das Paper verstandenhabt



Customization

ProblemstellungSchnelles Berechnen von kurzesten Wegen in Straßennetzwerkenmit wechselnden Metriken.

Motivation

Speed-Up-Technik, die mit beliebigen Metriken umgehen kannZeit, Fußganger, keine Autobahnen, Hohenbeschrankungen, etc.Vorberechnung pro Metrik soll sehr schnell seinEin paar Sekunden fur den gesamten GraphenExtrem schnelle lokale UpdatesEchtzeit-StaudatenSchnelle Queryzeiten (≤ 10 ms)



Customizable Route PlanningAufgaben

VorberechnungCustomizationDistanzanfragenPfadentpackungVisualisierung SuchraumParallelisierung Customization

Zusatzaufgaben fur 3er-TeamsBerechnung von Partitionen mit Inertial FlowUntersuchung verschiedener Partitionen (+ Visualisierung)Parallelisierung Queries und PfadentpackungTurn Costs

GegebenMulti-Level-Zellenpartition

D. Delling, A. V. Goldberg, T. Pajor, R. F. Werneck:Customizable Route Planning in Road Networks.In: http://research.microsoft.com/apps/pubs/?id=198358



http://research.microsoft.com/apps/pubs/?id=198358

Customizable Route PlanningAufgaben

VorberechnungCustomizationDistanzanfragenPfadentpackungVisualisierung SuchraumParallelisierung Customization

Zusatzaufgaben fur 3er-TeamsBerechnung von Partitionen mit Inertial FlowUntersuchung verschiedener Partitionen (+ Visualisierung)Parallelisierung Queries und PfadentpackungTurn Costs

GegebenMulti-Level-Zellenpartition

D. Delling, A. V. Goldberg, T. Pajor, R. F. Werneck:Customizable Route Planning in Road Networks.In: http://research.microsoft.com/apps/pubs/?id=198358



http://research.microsoft.com/apps/pubs/?id=198358

Customizable Contract. HierarchiesAufgaben

VorberechnungCustomizationDistanzanfragenPfadentpackungVisualisierung SuchraumElimination-Tree-QueryPerfekte Zeugensuche

Zusatzaufgaben fur 3er-TeamsParallelisierungBerechnung von Ordnungen mit Inertial FlowContraction-Graph-Datenstruktur

GegebenNested-Dissection-Ordnung

J. Dibbelt, B. Strasser, D. Wagner:Customizable Contraction Hierarchies.In: http://arxiv.org/abs/1402.0402



http://arxiv.org/abs/1402.0402

Customizable Contract. HierarchiesAufgaben

VorberechnungCustomizationDistanzanfragenPfadentpackungVisualisierung SuchraumElimination-Tree-QueryPerfekte Zeugensuche

Zusatzaufgaben fur 3er-TeamsParallelisierungBerechnung von Ordnungen mit Inertial FlowContraction-Graph-Datenstruktur

GegebenNested-Dissection-Ordnung

J. Dibbelt, B. Strasser, D. Wagner:Customizable Contraction Hierarchies.In: http://arxiv.org/abs/1402.0402



http://arxiv.org/abs/1402.0402

PHAST

ProblemstellungSchnelle Berechnung von one-to-all Kurzeste-Wege-Baumen aufStraßennetzwerken.

MotivationEs gibt n2 viele kurzeste WegeBei n = 18 · 106 dauert dasViele Vorberechnungen nur optimal, wenn alle aufgezahlt werdenPHAST nutzt die Hardware geschickt ausGeht in unter einem Tag



PHASTAufgaben

Basis-PHASTGraphdiameter bestimmenParallelisierungOne-to-many (RPHAST)Parallelisierung mit SSE oder GPU

Zusatzaufgaben fur 3er-TeamsVerschiedene Ordnungen ausprobierenAnwendung: Arc-Flags

Single-Level-Partition mit METISArc-Flags berechnen & visualisierenFlaggenkomprimierung

D. Delling, A. V. Goldberg, A. Nowatzyk, R. F. Werneck:PHAST: Hardware-Accelerated Shortest Path Trees.In: Journal of Parallel and Distributed Computing.



PHASTAufgaben

Basis-PHASTGraphdiameter bestimmenParallelisierungOne-to-many (RPHAST)Parallelisierung mit SSE oder GPU

Zusatzaufgaben fur 3er-TeamsVerschiedene Ordnungen ausprobierenAnwendung: Arc-Flags

Single-Level-Partition mit METISArc-Flags berechnen & visualisierenFlaggenkomprimierung

D. Delling, A. V. Goldberg, A. Nowatzyk, R. F. Werneck:PHAST: Hardware-Accelerated Shortest Path Trees.In: Journal of Parallel and Distributed Computing.



CHArge

ProblemstellungSchnellste Routen fur Elektrofahrzeuge inklusive Ladestopps

Akku darf nicht vollstandig entladenSchnell fahren, oft laden vs.langsam fahren, Energie sparen

? Reachable areaCharging station

st



CHArge

AufgabenBasisalgorithmus: Charging Function PropagationImplementierung Core-CHVisualisierung der RoutenA* mit skalaren PotentialenA* mit stuckweise linearen Funktionen

Zusatzaufgaben fur 3er-TeamsTurn Costs: Energieverbrauch fur GeschwindigkeitswechselModellierung von Ladevorgangen mit Exponentialfunktionen

M. Baum, J. Dibbelt, A. Gemsa, D. Wagner, T. Zundorf:Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles.In: 23rd ACM SIGSPATIAL International Conference on Advances in GeographicInformation Systems (GIS’15), pages 44:1-44:10. ACM Press, 2015.



RAPTOR

ProblemstellungSchnelle Berechnung von multi-kriteriellen (Reisezeit, AnzahlUmstiege, etc.) Anfragen in offentlichen Verkehrsnetzen.

Motivation:Netzwerke sind zeitabhangigBestehen aus Stops, Routen, Trips, . . .Modellierung als Graphen zukompliziert/langsamOptimierung von Ankunftszeit alleinenicht ausreichendDynamische Aspekte:Verspatungen, Ausfalle, . . .



RAPTORGegeben:

Fahrplandaten fur Deutschland, Schweiz

AufgabenImplementierung von RAPTOR fur Ankunftszeit und UmstiegeImplementierung von rRAPTOR fur ProfilanfragenAusgabe der Routen und VisualisierungParallelisierung

Zusatzaufgaben fur 3er-TeamsImplementierung McRAPTOR mit TarifzonenAlle Algorithmen fur unbeschranktes Laufen erweitern

D. Delling, T. Pajor, and R. F. WerneckRound-Based Public Transit Routing.In: Transportation Science volume 49 no. 3, pages 591-604. 2014.



Themenubersicht

Themen

Customizable Route PlanningRoutenplanung in Straßennetzwerken mit beliebigen MetrikenCustomizable Contraction HierachiesRoutenplanung in Straßennetzwerken mit beliebigen MetrikenPHASTSchnelle Berechnung von one-to-all kurzesten WegenCHArgeRoutenplanung fur ElektroautosRAPTORMulti-kriterielle Fahrplanauskunft



Documents

Praktikum Routenplanung - Themenvorstellung ... · INSTITUT F ¨UR THEORETISCHE INFORMATIK ALGORITHMIK PROF. DR. DOROTHEA WAGNER Praktikum Routenplanung Themenvorstellung & Gruppeneinteilung,