====== Algorithmen für Routenplanung ====== == im Sommersemester 2024 == ===== Allgemeines ===== * **Dozenten:** [[people:thomasblaesius|]], [[people:adrianfeilhauer|]], [[https://ae.iti.kit.edu/4255.php|Moritz Laupichler]], [[people:michaelzuendorf|]] * **Vorlesung:** montags, 4. Block, 14:00--15:30 Uhr, mittwochs, 3. Block, 11:30--13:00 Uhr. * **Raum:** Raum 301, Informatik-Hauptgebäude ([[http://www.uni-karlsruhe.de/fs/Uni/info/campusplan/index.php?id=50.34|Geb. 50.34]]) * **Studiengang:** Master Informatik/Informationswirtschaft. Weitere nach Rücksprache. * **Vertiefungsfächer:** Algorithmentechnik, aber nicht Theoretische Grundlagen * **Modul:** Algorithmen für Routenplanung [M-INFO-100031] * **Credits:** 5 ECTS (3 SWS) \\ Eine Liste von Hochschulgruppen, die gerade aktiv neue Mitglieder suchen findet ihr [[teaching:hochschulgruppenwerbung:start|hier]]. \\ \\ **Die Prüfungstermine stehen fest!**\\ Die möglichen Termine für die mündliche Prüfung sind:\\ * Montag **29.7.24** * Montag **26.8.24** * Mittwoch **18.9.24** **Anmeldung:** Die Anmeldung erfolgt über das [[https://cloud.iti.kit.edu/index.php/apps/appointments/pub/w0twtltNZ3lENqEZ/form | Onlineformular]] nach dem "first come, first served"-Prinzip. Bitte die Matrikelnummer angeben. **Prüfung:** Die Prüfung findet statt in Geb. 50.34. **Die Anmeldung für die Prüfung ist im Campus-System freigeschaltet. Bitte meldet euch rechtzeitig vor eurem Prüfungstermin dort an.** ===== Inhalt ===== [{{ :teaching:2024ss:routenplanung:sharcsearchspace.png?nolink&200|Optimale Route in einem Straßennetzwerk mit //Suchraum// einer Beschleunigungstechnik.}}]Optimale Routen in Verkehrsnetzen zu bestimmen ist ein alltägliches Problem. Wurden früher Reiserouten mit Hilfe von Karten am Küchentisch geplant, ist heute die computergestützte Routenplanung in weiten Teilen der Bevölkerung etabliert: Die beste Eisenbahnverbindung ermittelt man im Internet, für Routenplanung in Straßennetzen benutzt man häufig mobile Endgeräte. Ein Ansatz, um die besten Verbindungen in solchen Netzen computergestützt zu finden, stammt aus der Graphentheorie. Man modelliert das Netzwerk als Graphen und berechnet darin einen kürzesten Weg, eine mögliche Route. Legt man Reisezeiten als Metrik zu Grunde, ist die so berechnete Route die beweisbar schnellste Verbindung. Dijkstras Algorithmus aus dem Jahre 1959 löst dieses Problem zwar beweisbar optimal, allerdings sind Verkehrsnetze so groß (das Straßennetzwerk von West- und Mittel-Europa besteht aus ca. 45 Millionen Abschnitten), dass der klassische Ansatz von Dijkstra zu lange für eine Anfrage braucht. Aus diesem Grund ist die Entwicklung von Beschleunigungstechniken für Dijkstras Algorithmus Gegenstand aktueller Forschung. Dabei handelt es sich um zweistufige Verfahren, die in einem Vorverarbeitungsschritt das Netzwerk mit Zusatzinformationen anreichern, um anschließend die Berechnung von kürzesten Wegen zu beschleunigen. Diese Vorlesung gibt einen Überblick über aktuelle Algorithmen zur effizienten Routenplanung und vertieft einige von diesen. ===== Vorläufige Termine ===== | Mo, 15.04. | | - | | | Mi, 17.04. | Adrian | Einführung, Grundlagen, Modelle, Datenstrukturen, Dijkstras Algorithmus | {{ :teaching:2024ss:routenplanung:chap0-intro_adrian.pdf |Einführung}} | | Mo, 22.04. | Michael | Bidirektionale Suche, Kontraktion, TopoCore | {{ :teaching:2024ss:routenplanung:chap0-topocore.pdf |Bidirektionale Suche, Overlays}} | | Mi, 24.04. | Michael | A*, ALT, CALT | {{ :teaching:2024ss:routenplanung:chap1-astar-alt-calt.pdf |A*}} | | Mo, 29.04. | Adrian | Arc-Flags, SHARC | {{ :teaching:2024ss:routenplanung:chap1-arcflags-sharc.pdf | Arc-Flags, SHARC}} | | Mi, 01.05. | | Tag der Arbeit | | | Mo, 06.05. | Michael | MLO/CRP | {{ :teaching:2024ss:routenplanung:chap1-crp.pdf |CRP}} | | Mi, 08.05. | Michael | CH | {{ :teaching:2024ss:routenplanung:chap1-ch.pdf |CH}} | | Mo, 13.05. | Michael | CCH | {{ :teaching:2024ss:routenplanung:chap1-cch.pdf |CCH}} | | Mi, 15.05. | Michael | FlowCutter, Punch | {{ :teaching:2024ss:routenplanung:chap1-punch-flowcutter.pdf |PUNCH, FlowCutter}} | | Mo, 20.05. | | Pfingstferien | | | Mi, 22.05. | | Pfingstferien | | | Mo, 27.05. | Moritz | HL/HLDB/TNR | {{ :teaching:2024ss:routenplanung:chap1-hl-tnr.pdf |HL/HLDB/TNR}} | | Mi, 29.05. | Moritz | Multikriterielle Optimierung | {{ :teaching:2024ss:routenplanung:chap2-multicriteria.pdf |Multikriterielle Optimierung}} | | Mo, 03.06. | Moritz | Elektromobilität | {{ :teaching:2024ss:routenplanung:chap2-evrouting1.pdf |Elektromobilität 1}} | | Mi, 05.06. | Moritz | Elektromobilität | {{ :teaching:2024ss:routenplanung:chap2-evrouting2.pdf |Elektromobilität 2}} | | Mo, 10.06. | Michael | Abbiegekosten, Alternative Routen | {{ :teaching:2024ss:routenplanung:chap2-alternative.pdf |Abbiegekosten, Alternativ-Routen}} | | Mi, 12.06. | Moritz | Erweiterte Szenarien (one2all, one2many, many2many, POIs) | {{ :teaching:2024ss:routenplanung:chap1-all-many-poi.pdf |Erweiterte Szenarien}} | | Mo, 17.06. | Adrian | Zeitabhängige Routenplanung | {{ :teaching:2024ss:routenplanung:chap2-timedependent-preprocessing.pdf | Time-Dependent 1}} | | Mi, 19.06. | Moritz | Zeitabhängige Routenplanung | {{ :teaching:2024ss:routenplanung:chap2-timedependent-speedup.pdf | Time-Dependent 2}} | | Mo, 24.06. | Moritz | Fahrplanauskunft: Einführung und graphbasierte Techniken | {{ :teaching:2024ss:routenplanung:chap3-timetables.pdf | Fahrplanauskunft Einführung}} | | Mi, 26.06. | Adrian | Fahrplanauskunft: RAPTOR, CSA | {{ :teaching:2024ss:routenplanung:chap3-raptor.pdf | RAPTOR}} {{ :teaching:2024ss:routenplanung:chap3-csa.pdf | CSA}} | | Mo, 01.07. | Adrian | Fahrplanauskunft: CSA, Umlegung | {{ :teaching:2024ss:routenplanung:chap3-csa.pdf | CSA}} {{ :teaching:2024ss:routenplanung:chap3-umlegung.pdf | Umlegung}} | | Mi, 03.07. | Adrian | Multimodale Routenplanung: LCSPP, UCCH, MCR | {{ :teaching:2024ss:routenplanung:chap4-multimodal.pdf | Multimodal}} | | Mo, 08.07. | Adrian | Multimodale Routenplanung: Unbeschränktes Laufen, ULTRA | {{ :teaching:2024ss:routenplanung:chap4-unlimited-walking.pdf | ULTRA}} | | Mi, 10.07. | | - | | | Mo, 15.07. | | - | | | Mi, 17.07. | | - | | | Mo, 22.07. | | - | | | Mi, 24.07. | | - | | ===== Vergangene Veranstaltungen ===== //Hinweis:// Die Inhalte vergangener Vorlesungen können von der aktuellen abweichen. * [[https://i11www.iti.kit.edu/teaching/sommer2023/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2023]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2022/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2022]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2021/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2021]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2020/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2020]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2019/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2019]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2018/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2018]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2017/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2017]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2016/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2016]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2015/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2015]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2014/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2014]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2013/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2013]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2012/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2012]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2011/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2011]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2010/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2010]], ITI Wagner * [[https://i11www.iti.kit.edu/teaching/sommer2009/routenplanung/index|Algorithmen für Routenplanung, Sommersemester 2009]], ITI Wagner ===== Literatur ===== ^ Übersicht über das Themengebiet ^^ | [DSSW09] | Daniel Delling, Peter Sanders, Dominik Schultes, Dorothea Wagner:\\ **Engineering Route Planning Algorithms**.\\ In: //Algorithmics of Large and Complex Networks//, Lecture Notes in Computer Science. Springer, 2009. [ [[https://i11www.iti.kit.edu/extra/publications/dssw-erpa-09.pdf|pdf]] ] | | [BDGMPSW14] | Hannah Bast, Daniel Delling, Andrew Goldberg, Matthias Müller-Hannemann, Thomas Pajor, Peter Sanders, Dorothea Wagner, and Renato Werneck:\\ **Route Planning in Transportation Networks**.\\ Preprint. [ [[https://arxiv.org/pdf/1504.05140.pdf|pdf]] ] | ^ Grundlagen ^^ | [CLRS01] | Cormen, Leiserson, Rivest, Stein: //Introduction to Algorithms// | | [MS08] | Mehlhorn, Sanders: //Algorithms and Data Structures// | ^ A*, ALT, CALT, bidirektionale Suche ^^ |[GH05] | Andrew V. Goldberg and Chris Harrelson:\\ **Computing the Shortest Path: A Search Meets Graph Theory**.\\ In: //Proceedings of the 16th Annual ACM--SIAM Symposium on Discrete Algorithms (SODA'05)//, 2005. [ [[https://portal.acm.org/citation.cfm?id=1070455&CFID=20711573&CFTOKEN=24460449|pdf]] ] | |[GW05] | Andrew V. Goldberg and Renato F. Werneck:\\ **Computing Point-to-Point Shortest Paths from External Memory**.\\ In: //Proceedings of the 7th Workshop on Algorithm Engineering and Experiments (ALENEX'05)//, 2005. [ [[https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/GW05.pdf|pdf]] ] | | [DW07] | Daniel Delling and Dorothea Wagner:\\ **Landmark-Based Routing in Dynamic Graphs**.\\ In: //Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)//, 2007. [ [[https://i11www.iti.kit.edu/extra/publications/dw-lbrdg-07.pdf|pdf]] ] | |[BDS+09] | Reinhard Bauer, Daniel Delling, Peter Sanders, Dennis Schieferdecker, Dominik Schultes, and Dorothea Wagner:\\ **Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra's Algorithm**.\\ In: //ACM Journal of Experimental Algorithmics//, 2010. [ [[https://dl.acm.org/citation.cfm?id=1671976|pdf]] ] | ^ Arc-Flags, SHARC ^^ |[HKMS09] | Moritz Hilger and Ekkehard Köhler and Rolf H. Möhring and Heiko Schilling:\\ **Fast Point-to-Point Shortest Path Computations with Arc-Flags**.\\ In: //Shortest Paths: Ninth DIMACS Implementation Challenge//, 2009. [ [[http://www.dis.uniroma1.it/challenge9/papers/kohler.pdf|pdf]] ] | |[BD09] | Reinhard Bauer and Daniel Delling:\\ **SHARC: Fast and Robust Unidirectional Routing**.\\ In: //ACM Journal of Experimental Algorithmics//, 2009. [ [[https://i11www.iti.kit.edu/extra/publications/bd-sharc-09.pdf|pdf]] ] | |[BBRW13] | Reinhard Bauer, Moritz Baum, Ignaz Rutter, and Dorothea Wagner:\\ **On the Complexity of Partitioning Graphs for Arc-Flags**.\\ In: //Journal of Graph Algorithms and Applications//, 2013. [ [[https://jgaa.info/index.php/jgaa/article/download/paper294/2670|download]] ] | ^ Reach ^^ |[Gut04] | Ronald J. Gutman:\\ **Reach-Based Routing: A New Approach to Shortest Path Algorithms Optimized for Road Networks**\\ In: //Proceedings of the 6th Workshop on Algorithm Engineering and Experiments (ALENEX'04)//, 2004, pages 100--111. [ [[https://www.siam.org/meetings/alenex04/abstacts/rgutman1.pdf|download]] ] | |[GKW09] | Andrew V. Goldberg and Haim Kaplan and Renato F. Werneck:\\ **Reach for A*: Shortest Path Algorithms with Preprocessing**\\ In: //Shortest Paths: Ninth DIMACS Implementation Challenge//, 2009. [ [[https://research.microsoft.com/apps/pubs/default.aspx?id=60764|link]] ] | ^ Multi-Level Overlays ^^ | [SWZ02] | Frank Schulz, Dorothea Wagner, Christos Zaroliagis:\\ **Using Multi-Level Graphs for Timetable Information in Railway Systems**\\ In: //Proceedings of the 4th Workshop on Algorithm Engineering and Experiments (ALENEX'02)//, 2002, pages 43-59. [ [[https://i11www.iti.kit.edu/extra/publications/swz-umlgt-02.pdf|pdf]] ] | | [SS07] | Dominik Schultes, Peter Sanders:\\ **Dynamic Highway-Node Routing**\\ In: //Proceedings of the 6th Workshop on Experimental Algorithms (WEA'07)//, 2007, pages 66-79. [ [[https://ae.iti.kit.edu/documents/research/routeplanning/dynamicHNR.pdf|pdf]] ] | | [DGP11] | Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck:\\ **Customizable Route Planning**\\ In: //Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)//, 2011, pages 376-387. [ [[https://i11www.iti.kit.edu/extra/publications/dgpw-crp-11.pdf|pdf]] ] | ^ Zeitabhängige Routenplanung ^^ |[Del09] | Daniel Delling:\\ **Engineering and Augmenting Route Planning Algorithms**\\ Ph.D. Thesis, Universität Karlsruhe (TH), 2009. [ [[https://i11www.iti.kit.edu/extra/publications/d-earpa-09.pdf|pdf]] ] | |[BDSV09] | Gernot Veit Batz, Daniel Delling, Peter Sanders, Christian Vetter:\\ **Time-Dependent Contraction Hierarchies**\\ In: //Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX'09)//, April 2009. [ [[https://ae.iti.kit.edu/documents/research/routeplanning/tch_alenex09.pdf|pdf]] ]| |[BGNS10] | Gernot Veit Batz, Robert Geisberger, Sabine Neubauer, Peter Sanders:\\ **Time-Dependent Contraction Hierarchies and Approximation**\\ In: //Proceedings of the 9th International Symposium on Experimental Algorithms (SEA'10)//, May 2010. [ [[https://ae.iti.kit.edu/download/sea10_atch.pdf|pdf]] ]| |[KZ14] | Spyros Kontogiannis, Christos Zaroliagis:\\ **Distance Oracles for Time Dependent Networks.**\\ In: //Automata, Languages and Programming (ICALP'14)//, 2014. [ [[https://arxiv.org/abs/1309.4973|arxiv]] ]| ^ Abbiegekosten ^^ |[GS11] | Robert Geisberger, Christian Vetter:\\ **Efficient Routing in Road Networks with Turn Costs**.\\ In: //Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)//, 2011, pages 100-111. [ [[https://ae.iti.kit.edu/download/turn_ch.pdf|pdf]] ] | | [DGP11] | Daniel Delling, Andrew V. Goldberg, Thomas Pajor, Renato F. Werneck:\\ **Customizable Route Planning**\\ In: //Proceedings of the 10th International Symposium on Experimental Algorithms (SEA'11)//, 2011, pages 376-387. [ [[https://i11www.iti.kit.edu/extra/publications/dgpw-crp-11.pdf|pdf]] ] | ^ Multikriterielle Optimierung ^^ |[DW09] | Daniel Delling, Dorothea Wagner:\\ **Pareto Paths with SHARC**.\\ In: //Proceedings of the 8th International Symposium on Experimental Algorithms (SEA'09)//, 2009, pages 125-136. [ [[https://i11www.iti.kit.edu/extra/publications/dw-pps-09.pdf|pdf]] ] | ^ Elektromobilität ^^ |[EFS11] | Jochen Eisner, Stefan Funke, Sabine Storandt:\\ **Optimal Route Planning for Electric Vehicles in Large Networks**\\ In: //Proceedings of the 25th AAAI Conference on Artificial Intelligence//, 2011 [ [[https://ad-publications.informatik.uni-freiburg.de/AAAI_evpaths_EFS_2011.pdf|pdf]] ] | |[BDPW13] | Moritz Baum, Julian Dibbelt, Thomas Pajor, Dorothea Wagner:\\ **Energy-Optimal Routes for Electric Vehicles**\\ In: //Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems//, 2013 [ [[https://dl.acm.org/citation.cfm?id=2525361|link]] ] | |[BDGZW15] | Moritz Baum, Julian Dibbelt, Andreas Gemsa, Tobias Zündorf, Dorothea Wagner:\\ **Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles**\\ In: //Proceedings of the 23rd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems//, 2013 [ [[https://dl.acm.org/citation.cfm?id=2820826|link]] ] | ^ Erweiterte Szenarien (One-to-all, one-to-many, POI, Isochronen) ^^ | [DGNW11] | Daniel Delling, Andrew V. Goldberg, Andreas Nowatzyk, Renato F. Werneck:\\ **PHAST: Hardware-accelerated shortest path trees**\\ In: //Journal of Parallel and Distributed Computing//, pages 940-952, 2013. [ [[https://www.sciencedirect.com/science/article/pii/S074373151200041X|link]] ] | | [EP14] | Alexandros Efentakis, Dieter Pfoser:\\ **GRASP. Extending Graph Separators for the Single-Source Shortest-Path Problem**\\ In: //Proceedings of the 22nd European Symposium on Algorithms (ESA'14)//, pages 358-370, 2014. [ [[https://link.springer.com/chapter/10.1007%2F978-3-662-44777-2_30|link]] ] | | [KSSSW07] | Sebastian Knopp, Peter Sanders, Dominik Schultes, Frank Schulz, Dorothea Wagner:\\ **Computing Many-to-Many Shortest Paths Using Highway Hierarchies**\\ In: //Proceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX'07)//, pages 36-45, 2007. [ [[https://ae.iti.kit.edu/documents/research/routeplanning/distTable.pdf|pdf]] ] | | [DGW11] | Daniel Delling, Andrew V. Goldberg, Renato F. Werneck:\\ **Faster Batched Shortest Paths in Road Networks**\\ In: //Proceedings of the 11th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'11)//, pages 52-63, 2011. [ [[https://drops.dagstuhl.de/opus/volltexte/2011/3266/pdf/6.pdf|pdf]] ] | | [ADFGW12] | Ittai Abaraham, Daniel Delling, Amos Fiat, Andrew V. Goldberg, Renato F. Werneck:\\ **HLDB: Location-Based Services in Databases**\\ MSR-TR-2012-59, 2012. [ [[https://dl.acm.org/doi/pdf/10.1145/2424321.2424365|pdf]] ] | | [BBDW16] | Moritz Baum, Valentin Buchhold, Julian Dibbelt, Dorothea Wagner:\\ **Fast Exact Computation of Isochrones in Road Networks**\\ In: //Proceedings of the 15th International Symposium on Experimental Algorithms (SEA'16)//, pages 17-32, 2016. [ [[https://link.springer.com/chapter/10.1007%2F978-3-319-38851-9_2|link]] ] | ^ Fahrplanauskunft ^^ |[PSWZ08] | Evangelia Pyrga, Frank Schulz, Dorothea Wagner, Christos Zaroliagis:\\ **Efficient Models for Timetable Information in Public Transportation Systems**\\ In: //ACM Journal of Experimental Algorithmics//, 2008 [ [[https://dl.acm.org/doi/pdf/10.1145/1227161.1227166|pdf]] ] | |[DPW09] | Daniel Delling, Thomas Pajor, Dorothea Wagner:\\ **Engineering Time-Expanded Graphs for Faster Timetable Information**\\ In: //Robust and Online Large-Scale Optimization//, 2009 [ [[https://i11www.iti.kit.edu/extra/publications/dpw-etegf-09.pdf|pdf]] ] | |[DKP10] | Daniel Delling, Bastian Katz, Thomas Pajor:\\ **Parallel Computation of Best Connections in Public Transportation Networks**\\ In: //24th International Parallel and Distributed Processing Symposium (IPDPS'10)//, 2010 [ [[https://i11www.iti.kit.edu/extra/publications/dkp-pcbcp-10.pdf|pdf]] ] | |[DMS08] | Yann Disser, Matthias Müller-Hannemann, Mathias Schnee:\\ **Multi-Criteria Shortest Paths in Time-Dependent Train Networks**\\ In: //Proceedings of the 7th Workshop on Experimental Algorithms (WEA’08)//, 2008 [ [[https://www2.mathematik.tu-darmstadt.de/~disser/pdfs/DisserMullerHannemannSchnee08.pdf|pdf]] ] | |[DPW12] | Daniel Delling, Thomas Pajor, Renato Werneck:\\ **Round-Based Public Transit Routing**\\ In: //Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12)//, 2012 [ [[https://i11www.iti.kit.edu/extra/publications/dpw-rbptr-12.pdf|pdf]] ] | |[DPSW13] | Julian Dibbelt, Thomas Pajor, Ben Strasser, Dorothea Wagner:\\ **Intriguingly Simple and Fast Transit Routing**\\ In: //Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13)//, 2013 [ [[https://i11www.iti.kit.edu/extra/publications/dpsw-isftr-13.pdf|pdf]] ] | |[SW14] | Ben Strasser, Dorothea Wagner:\\ **Connection scan accelerated**\\ In: //Proceedings of the 16th Meeting on Algorithm Engineering and Experiments (ALENEX’14)//, 2014 [ [[https://delivery.acm.org/10.1145/2800000/2790186/p125-strasser.pdf|pdf]] ] | |[BBE+17] | Lars Briem, H. Sebastian Buck, Holger Ebhart, Nicolai Mallig, Ben Strasser, Peter Vortisch, Dorothea Wagner, Tobias Zündorf:\\ **Efficient Traffic Assignment for Public Transit Networks**\\ In: //Proceedings of the 16th International Symposium on Experimental Algorithms (SEA'17)//, 2017 [ [[https://drops.dagstuhl.de/opus/volltexte/2017/7610/pdf/LIPIcs-SEA-2017-20.pdf|pdf]] ] | ^ Multimodale Routenplanung ^^ | [DPW09] | Daniel Delling, Thomas Pajor, Dorothea Wagner:\\ **Accelerating Multi-Modal Route Planning by Access-Nodes**.\\ In: //Proceedings of the 17th Annual European Symposium on Algorithms (ESA'09).// [ [[https://i11www.iti.kit.edu/extra/publications/dpw-ammrp-09.pdf|pdf]] ] | | [DPW12] | Julian Dibbelt, Thomas Pajor, Dorothea Wagner:\\ **User-Constrained Multi-Modal Route Planning**\\ In: //Proceedings of the 14th Meeting on Algorithm Engineering and Experiments (ALENEX'12).// [ [[https://i11www.iti.kit.edu/extra/publications/dpw-ucmmr-12.pdf|pdf]] ] | | [DDP+13] | Daniel Delling, Julian Dibbelt, Thomas Pajor, Dorothea Wagner, Renato F. Werneck:\\ **Computing Multimodal Journeys in Practice**\\ In: //Proceedings of the 12th International Symposium on Experimental Algorithms (SEA'13).// [ [[https://i11www.iti.kit.edu/extra/publications/ddpww-cmjp-13.pdf|pdf]] ] | | [WZ17] | Dorothea Wagner, Tobias Zündorf:\\ **Public Transit Routing with Unrestricted Walking**\\ In: //Proceedings of the 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'17)//, 2017 [ [[https://drops.dagstuhl.de/opus/volltexte/2017/7891/pdf/OASIcs-ATMOS-2017-7.pdf|pdf]] ] | | [BBS+19] | Moritz Baum, Valentin Buchhold, Jonas Sauer, Dorothea Wagner, Tobias Zündorf:\\ **UnLimited TRAnsfers for Multi-Modal Route Planning: An Efficient Solution**\\ In: //Proceedings of the 27th Annual European Symposium on Algorithms (ESA'19)//, 2019 [ [[https://i11www.iti.kit.edu/extra/publications/bbswz-ultra-19.pdf|pdf]] ] [ [[https://arxiv.org/abs/1906.04832|arXiv]] ] |