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

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.