Optimal Route Based on Dynamic Programming for Road Networks

Abstract

One of the main functions of the traffic navigation systems is to find the optimal route to the destination. In this paper, we propose an iterative Q value updating algorithm, Q method, based on dynamic programming to search the optimal route and its optimal traveling time for a given Origin-Destination (OD) pair of road networks. The Q method uses the traveling time information available at adjacent intersections to search for the optimal route. The Q value is defined as the minimum traveling time to the destination when a vehicle takes the next intersection. When the Q values converge, the optimal route to the destination can be determined by choosing the minimum Q value at each intersection. The Q method gives us the solutions from multiple origins to a single destination. The proposed method is not restricted to find a single solution, but, if there exist multiple optimal routes with the identical traveling time to the destination, the proposed method can find all of it. In addition to that, when the traveling time of the road sections changes, an alternative optimal route can be found easily starting with the already obtained Q values. We compared the Q method with Dijkstra algorithm and the simulation results showed that the Q method can give better performances, depending on the situations, when the traveling time of the road sections changes.