Research On Multi-constrained Optimal Pathalgorithm Of Urban Road Traffic Information

Optimal path algorithm has been the focus and attention of many researchersand scholars, the traditional optimal path algorithm is also the shortest path, mainly ina static network under a single constraint, which is the length of two different nodes.The length among the nodes can be acquired before the algorithm, and is knowable.In the network of smaller, relatively simple cases, the traditional optimal pathalgorithm can solve more satisfactory results. However, now the urban’s road trafficnetwork is complex, time changing with large number of nodes and different nodescontain more information which is no longer single and fixed, and cannot bepredicted in advance. Today, the requirement of traveler’s for the optimal path is nolonger the shortest path, their hope is to consider multiple traffic information on theurban road, which is more in line with the purpose of travel safety and convenience.In this demand, the traditional optimal path problem becomes relatively optimal pathproblem under multiple constraints.Ant colony algorithm is an intelligent algorithm which was inspired by theforaging behavior of ant colony groups, this algorithm can effectively solve thecombinatorial optimization problems. Because of responding to the changes ofoutside in the actual search process dynamically, it is feasible in urban road trafficoptimal path selection. This thesis exploits the advantages of ant colony algorithm,and improves the basic ant colony algorithm. Mainly including the following aspects:(1)This thesis begins with the researching status of the optimal path and antcolony algorithm, analysis the existing problem in study; Then describes the optimalpath problem and the model of multi-constrained optimal path; And also analysis ofthe existing traditional optimal path algorithm’s characteristics and application scope.(2)The thesis studys the parameters of traffic information for urban roads; Thengives their presentation and storage structure. Analysis of the transitnetwork’s representation and storage structure of city’s road network, then proposesthe description of traffic information in the network.(3)The thesis studys basic principle of the ant colony algorithm, process and model, then analyzed influence of the algorithm parameters on the performance of thealgorithm. This thesis proposes a multi-constraint algorithm which called MCACO(Mutil-Constrained Ant Colony Optimization). MCACO used more then one trafficinformation into the improved algorithm, the simulation results proves that theimproved algorithm MCACO can be used to select optimal path problem under multi-constraints.This thesis is supported by Natural Science Foundation of Hubei Province(2012FFB05006), which is named Research on the optimal path selection algorithmof traveler based on the wireless sensor network.