Research And Implementation Of Dynamic City Network Shortest Path Search Based On Distributed Ant Colony Algorithm

With the social development and progress, the cities are keeping expanding. Traffic networks in large cities become more and more complex and present some new features with large-scale and dynamic characteristics. Traditional shortest path search cannot meet residents’ dynamic service demand on fast travelling. In recent years, floating car technology has been applied widely in the traffic management and control area and a great deal of data are accumulated. This provides foundations for the researchers to obtain the dynamic road network features. Therefore, the research on the dynamic shortest path search has a high theoretical and practical significance. The classic shortest path search algorithms, such as Dijkstra algorithm and Floyd algorithm, are widely used in static network and difficult for parallel computing, which make them difficult to efficiently solve the dynamic shortest path problem. Therefore, this thesis has focused on using distributed ant colony algorithm to solve the dynamic shortest path search problem in large scale network to meet the car travelers’ requirement for the shortest travel time.Firstly, by comparing with other algorithms, ant colony algorithm (i.e. ACO) is selected for dynamic path search and the basic principle and researches on ACO algorithm, as well as parallel computing model are reviewed. Secondly, the research on how to aggregate section average velocity with floating car data is conducted. The travel time and distance weighted aggregation method using samples of floating car records to obtain the time-varying average section speed is proposed, which provides the basis for dynamic path search. Thirdly, according to the characteristics of large-scale network, two improvement strategies of ACO algorithm are put forward to reduce the computing time and avoid the local convergence. One is the optimization of single ant routing and the other is adaptive pheromone update strategy. Then, based on the theory of distributed computing and the characteristics of parallel ACO algorithm, a parallel program of master-slave type regular interaction method combined with radio type trigger interaction method among sub ant colonies is designed. MPI programming model is used to develop parallel ACO algorithm in MPICH2platform. Finally, the method to build the distributed computing platform is introduced and key parameters of ACO algorithm are selected. Experiments on multiple path search are conducted. The experimental results show that the developed algorithm has obvious advantages in both of running time and calculation results, which proves its high performance.