An adaptive routing algorithm for in-vehicle route guidance systems with real-time information

This paper examines the problem of routing a given vehicle through a traffic network in which travel time on each link can be modeled as a random variable and its realization can be estimated in advance and made available to the vehicle's routing system before it enters the link. The underlying problem is formulated as the closed-loop adaptive shortest path routing problem (CASPRP) with the objective of identifying only the immediate link, instead of a whole path, to account for the future availability of travel time information on individual links. Having formulated the problem as a dynamic program and identified the associated difficulties, we apply an approximate probabilistic treatment to the recurrent relations and propose a labeling algorithm to solve the resultant equations. The proposed algorithm is proved theoretically to have the same computational complexity as the traditional label-correcting (LC) algorithm for the classic shortest path problems. Computational experiments on a set of randomly generated networks and a realistic road network demonstrate the efficiency of the proposed algorithm and the advantage of adaptive routing systems. (C) 2001 Elsevier Science Ltd. All rights reserved.