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 traffi c network in which travel time on each link can be modeled as a random vari able and its realization can be estimated in advance and made available to the vehicle's routing system before it enters the link. The underlying prob lem is formulated as the closed-loop adaptive shortest path routing problem (CASPRP) with the objective of identifying only the immediate link, instea d of a whole path, to account for the future availability of travel time in formation on individual links. Having formulated the problem as a dynamic p rogram and identified the associated difficulties, we apply an approximate probabilistic treatment to the recurrent relations and propose a labeling a lgorithm 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. Co mputational experiments on a set of randomly generated networks and a reali stic road network demonstrate the efficiency of the proposed algorithm and the advantage of adaptive routing systems. (C) 2001 Elsevier Science Ltd. A ll rights reserved.