A Randomized Path Routing Algorithm for Decentralized Route Allocation in Transportation Networks

Abstract

Route planning in current route guidance systems is pri- marily based on the shortest path strategy (e.g., suggesting a path that minimizes the travel distance between source and destination) for an individual driver. A drawback of such an approach is that there is a high probability that many drivers, who share the same source and destination, follow the same route. This can lead to over-saturated road links. We propose a simple yet effective multiple path rout- ing algorithm that addresses this limitation. The proposed algorithm augments the A search algorithm with a ran- domization component, which helps to perturb the order of the searched nodes and to produce diversified routes for dif-..