Algorithm Engineering für Routenplanung

路径规划的算法工程

• 批准号: 67847980
• 负责人: Professor Dr. Peter Sanders
• 金额: --
• 依托单位: Lehrstuhl Algorithmik II
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2008
• 资助国家: 德国
• 起止时间: 2007-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/67847980?language=en
• 关键词: Algorithm; Engineering; Routenplanung

Im Mittelpunkt des Projekts stehen Algorithmen zur sehr schnellen Berechnung kürzester Wege in sehr großen Graphen. Dabei wollen wir uns an Szenarien orientieren, die bei der Routenplanung im Straßenverkehr oder der Fahrplanauskunft in öffentlichen Verkehrssystemen auftreten. Die meisten unserer Ziele sind motiviert durch die Vision des „zukünftigen Routenplaners“, d.h. eines komfortablen, mobilen hybriden Routenplaners mit dezentralen und zentralen Komponenten. Routenplaner müssen in der Lage sein, im Bruchteil einer Sekunde eine optimale Route oder Zugverbindung (bezüglich Fahrzeit oder Distanz oder auch anderer Kriterien) zu ermitteln, wobei vorberechnete Information ausgenutzt werden kann. In der Praxis werden heutzutage meist heuristische Verfahren eingesetzt, die zwar schnell eine Route berechnen, deren Optimalität aber nicht garantiert werden kann. Weitergehende Anforderungen wie die schnelle Aktualisierung bei veränderter Verkehrssituation oder Verspätungen, die Berücksichtigung von Zeitabhängigkeit, mehreren Kriterien oder Nebenbedingungen werden kaum oder gar nicht unterstützt. Ausgangspunkt für die schnelle Berechnung kürzester Wege in Graphen ist der klassische Algorithmus von Dijkstra. Ziel des Projekts ist der Entwurf, die theoretische Analyse sowie die Implementierung und experimentelle Bewertung von Algorithmen zur Berechnung kürzester Wege, insbesondere von Beschleunigungstechniken für den Algorithmus von Dijkstra. Dabei soll der Fokus einerseits auf zeitabhängigen und dynamischen Szenarien, andererseits auf der Berücksichtigung von Nebenbedingungen und auf mehreren Optimierungskriterien liegen.

我的项目中的算法是在 Graphen 中进行的。 Die meisten unserer Ziele sind motiviert durch die Vision des 'zukünftigen Routenplaners', d.h.在实践中，我们应该以启发式的方式进行实践，并遵循最佳路线，以确保最佳化韦尔登运河Graphen ist der klassische Algorithmus von Dijkstra 中的 Berechnung kürzester Wege。冯迪杰斯特拉算法。

项目成果

Parallel Bi-objective Shortest Paths Using Weight-Balanced B-trees with Bulk Updates

使用带有批量更新的权重平衡 B 树的并行双目标最短路径

• DOI: 10.1007/978-3-319-07959-2_10
• 发表时间: 2014
• 作者: Stephan Erb;Moritz Kobitzsch;Peter Sanders
• 通讯作者: Peter Sanders

Route Planning in Transportation Networks

• DOI: 10.1007/978-3-319-49487-6_2
• 发表时间: 2016-01-01
• 期刊: ALGORITHM ENGINEERING: SELECTED RESULTS AND SURVEYS
• 作者: Bast, Hannah;Delling, Daniel;Werneck, Renato F.
• 通讯作者: Werneck, Renato F.

Candidate Sets for Alternative Routes in Road Networks

• DOI: 10.1145/2674395
• 发表时间: 2012-06
• 期刊: Journal of Experimental Algorithmics (JEA)
• 作者: Dennis Luxen;D. Schieferdecker

Minimum time-dependent travel times with contraction hierarchies

• DOI: 10.1145/2444016.2444020
• 发表时间: 2013-12
• 期刊: ACM J. Exp. Algorithmics
• 作者: G. V. Batz;R. Geisberger;P. Sanders;C. Vetter

Search-space size in contraction hierarchies

• DOI: 10.1016/j.tcs.2016.07.003
• 发表时间: 2013-07
• 作者: Reinhard Bauer;Tobias Columbus;Ignaz Rutter;D. Wagner