C. Wang, Z.D. Huang, H.J. He

Pages: 51-58

Abstract
With the development of China's social economy and science and technology, the scale of urban traffic network has become bigger and bigger. How to quickly find the shortest path in the regional traffic network with dense roads and complex traffic nodes has become an urgent concern for current traffic travelers. In order to overcome the shortcomings of traditional shortest path algorithms such as Dijkstra in its long solution time and low accuracy when solving large-scale urban traffic networks, based on the constructed traffic network topology, this paper proposes a shortest path model based on Petri net and traffic network weighted S-graph, taking the characteristics of urban traffic network into consideration, this paper establishes an improved shortest path Genetic Algorithm (GA) based on the traditional GA. The research results show that the improved GA has the advantages of high speed and accuracy when solving the shortest path of the regional traffic network, and can quickly find the shortest path with smaller error compared with the actual value. Once again, it’s proved that constructing an efficient and accurate shortest path search algorithm is very important. The research results can provide a theoretical basis for the shortest path search of regional traffic network.
Keywords: petri net; shortest path; weighted s-graph; improved genetic algorithm (GA)