DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

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

Ebendt, Rüdiger and 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.

WarningThere is a more recent version of this item available.

Full text not available from this repository.


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.

Item URL in elib:https://elib.dlr.de/62447/
Document Type:Conference or Workshop Item (Speech)
Title:An Integrative Approach to Light- and Heavy-Weighted Route Planning Problems
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Ebendt, Rüdigerruediger.ebendt (at) dlr.deUNSPECIFIED
Wagner, Peterpeter.wagner (at) dlr.deUNSPECIFIED
Refereed publication:Yes
Open Access:No
Gold Open Access:No
In ISI Web of Science:No
Keywords:Intelligent Transport Systems, Floating Car Data, route planning, search, heuristic search, Dijkstra’s algorithm, A*, weighted A*
Event Title:5th IMA Conference on Mathematics in Transport
Event Location:London, Großbritannien
Event Type:international Conference
Event Dates:12.-14. April 2010
Organizer:Institute of mathematics and its applications
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Transport
HGF - Program Themes:Traffic Management (old)
DLR - Research area:Transport
DLR - Program:V VM - Verkehrsmanagement
DLR - Research theme (Project):V - Methodenentwicklung (old)
Location: Berlin-Adlershof
Institutes and Institutions:Institute of Transportation Systems > Traffic Management
Deposited By: Ebendt, Dr.rer.nat. Rüdiger
Deposited On:13 Jan 2010 10:45
Last Modified:17 Sep 2012 10:51

Available Versions of this Item

Repository Staff Only: item control page

Help & Contact
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.