elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Datenschutz | Kontakt | English
Schriftgröße: [-] Text [+]

An Integrative Approach to Light- and Heavy-Weighted Route Planning Problems

Ebendt, Rüdiger und Wagner, Peter (2010) An Integrative Approach to Light- and Heavy-Weighted Route Planning Problems. 5th IMA Conference on Mathematics in Transport, 12.-14. April 2010, London, Großbritannien.

WarnungEs ist eine neuere Version dieses Eintrags verfügbar.

Dieses Archiv kann nicht den Volltext zur Verfügung stellen.

Kurzfassung

The single-source shortest path problem (SSSP) frequently arises in practical applications of todays Intelligent Transport Systems (ITS). E.g. for route planning or traffic assignment, several variants of Dijkstra’s algorithm or the A* algorithm have been used. Several performance-accelerated extensions of the exact A* approach are known. Interesting examples are approximate algorithms where the used heuristic function is inflated by a weight (often referred to as weighted A*). These methods guarantee a bounded suboptimality. During the last nine years, a couple of prototype ITS applications based on Floating Car Data (FCD) of taxi fleets have been developed at German Aerospace Center (DLR). A core application is a route guidance and dynamic navigation system based on current and historical road segment travel times. Recently, it has been used in the German funded project SmartTruck, run by a consortium consisting of the German logistics key player DHL, DLR and the German Research Center for Artificial Intelligence (DFKI). This project aimed at the use of historical and real-time traffic information for energy-efficient, optimized offline planning and dynamic replanning of the tours of DHL express delivery trucks. The mentioned applications have to tackle the SSSP or multi-source variants of the problem. This paper describes the use of an integrative approach to efficiently compute shortest or almost shortest paths in the prementioned applications. Hereby, the choice of a particular variant of Dijkstra or A* reacts to the respective requirement of solution quality and the different levels of severity of the problem. As a technical result, for epsilon > 0, the (1 + epsilon)-admissibility of a novel variation of the method A_epsilon of Ghallab and Allard is shown. The paper also answers the question whether inflation of the cost function g (instead of the usual inflation of the heuristic h) can be (1 + epsilon)-admissible and whether this is beneficial. An experimental evaluation demonstrates the efficiency of the described integration of algorithms.

elib-URL des Eintrags:https://elib.dlr.de/62447/
Dokumentart:Konferenzbeitrag (Vortrag)
Titel:An Integrative Approach to Light- and Heavy-Weighted Route Planning Problems
Autoren:
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID-iDORCID Put Code
Ebendt, Rüdigerruediger.ebendt (at) dlr.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Wagner, Peterpeter.wagner (at) dlr.deNICHT SPEZIFIZIERTNICHT SPEZIFIZIERT
Datum:2010
Referierte Publikation:Ja
Open Access:Nein
Gold Open Access:Nein
In SCOPUS:Nein
In ISI Web of Science:Nein
Status:akzeptierter Beitrag
Stichwörter:Intelligent Transport Systems, Floating Car Data, route planning, search, heuristic search, Dijkstra’s algorithm, A*, weighted A*
Veranstaltungstitel:5th IMA Conference on Mathematics in Transport
Veranstaltungsort:London, Großbritannien
Veranstaltungsart:internationale Konferenz
Veranstaltungsdatum:12.-14. April 2010
Veranstalter :Institute of mathematics and its applications
HGF - Forschungsbereich:Luftfahrt, Raumfahrt und Verkehr
HGF - Programm:Verkehr
HGF - Programmthema:Verkehrsmanagement (alt)
DLR - Schwerpunkt:Verkehr
DLR - Forschungsgebiet:V VM - Verkehrsmanagement
DLR - Teilgebiet (Projekt, Vorhaben):V - Methodenentwicklung (alt)
Standort: Berlin-Adlershof
Institute & Einrichtungen:Institut für Verkehrssystemtechnik > Verkehrsmanagement
Hinterlegt von: Ebendt, Dr.rer.nat. Rüdiger
Hinterlegt am:13 Jan 2010 10:45
Letzte Änderung:17 Sep 2012 10:51

Verfügbare Versionen dieses Eintrags

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Blättern
Suchen
Hilfe & Kontakt
Informationen
electronic library verwendet EPrints 3.3.12
Gestaltung Webseite und Datenbank: Copyright © Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.