Algorithm of Best Path in Dynamic Route Guidance System

Along with improving conditions of road and increasing vehicles, the variety, the indeterminacy and the complexity of urban road traffic conditions, are even more obvious, it causes the results of Static Route Guidance System (SRGS) to be often far from the real. In order to make up this serious insufficiency in SRGS, Dynamic Route Guidance System (DRGS) arises at the moment. Through providing drivers with the best travel route based on real-time dynamic traffic flow, DRGS guides the vehicle on a journey triumphantly. In DRGS, selection of the best path is its core. Because the model of the best path has the characteristic of non-determination polynomial-hard(NP-hard), its algorithm must have globe optimization and real-time property. Genetic Algorithm (GA) is the first choice, relying on the global optimum and latent parallel characteristic. In the paper, it presents and analyses an efficient solution to the vehicle routing problem based on real-time dynamic information. This approach consists of solving a sequence of optimization problems, where we take into account different scenarios for future travel times. Based on the detailed analyses of characteristic of the best path and real-time limitation of traditional Dijkstra algorithm, it builds a GA for solving the model of the best path in DRGS. Our main work is, according to the concrete characteristic of the model of the best path in DRGS, to improve genetic operator, restraint conditions and fitness function in standard GA; and to carry on the confirmation with an example. The confirmation results indicate that this algorithm can solve the model of the best path in DRGS effectively, increase the convergence rate and has the certain theory reference value and the practical significance.