Research On Vehicle Navigation Route Planning Problem Based On Hierarchical Restricted Searching Area

As important part of Intelligent Transportation Systems (ITS), vehicle navigation systemis aiming to reduce traffic congestion and traffic accidents, but along with the increasing scaleand complexity of the city traffic network, the situation of traffic congestions and trafficaccidents is becoming worse. Especially in the face of growing urban road network, theshortest path algorithm needs large amount of calculation, traffic congestion changes at anytime, and also most navigation system can not help people in time to avoid congested roads.Therefore, considering the traffic congestion in the shortest path planning problem oflarge-scale road network has become a hot research of current study.This paper carries out theresearch from three aspects:(1) The time dependent road network model based on the edge cost analysis is establishedon the disadvantage of the model that it can not fully reflect the information of the roadattribute. The attribute of the road and intersection in the model is expressed as set, the set ofthe road attribute is attached to the edge set of the road network model and the set of theintersection attribute is attached to the node set of the road network model; We defineparameters within the road attribute set and the parameter within the intersection attribute set,and give the formula of the edge cost which is comprehensively influenced by the parameter,and the road congestion state is divided into five levels based on the criteria of the roadaverage speed of the edge attribute.(2) The route planning algorithm with dynamic adjustment mechanism of the hierarchicalrestricted area is established on the disadvantage that each layer of the multi-level roadnetwork is needed to search step by step and could not dynamically avoid the road with poorcapacity. In order to improve the operation efficiency of the algorithm, the restricted rectanglearea is established to lower the number of the network node which participates the pathsearching; The high layer network and low layer network are divided based on road spatialdistribution characteristics and the traffic capacity of the road of different levels, the algorithmfirst search high layer network to ensure the purpose of the shortest path travel time; Thedynamic switching between high layer network and low layer network is based on thereal-time change of the traffic congestion. To achieve the purpose of avoiding trafficinconvenience road, we use the idea that when there comes traffic congestion in the plannedroutes of the high layer, we switch to low layer network timely according to the trafficcongestion degree to avoid congested roads.(3) Finally, the multi-population ant colony routing optimization improvement strategy is presented on the disadvantage that the ant colony of the hierarchical restricted area has longoperation time and local convergence. Through improving the state transition formula basedon the single population ant colony algorithm of the hierarchical restricted area, theinformation share and update strategy of multiple population ant colony is established, and thestrategy combined with the regular interaction within a population、the radio type triggerinteraction between populations and the information exchange of congested road is designed,which makes multiple populations jointly maintain the same road network structure andcomplete a path search, in order to achieve the objective of the global optimal, the pheromoneupdate scheme is determined by gathering all sub-population optimal paths and then thepheromone is passed to the sub-populations to realize information sharing.In this paper, the simulation experiment uses the scheme of random allocation speedvalue by speed fitting function, and the comparation between the Dijkstra algorithm based onhierarchical restricted searching area, the single population ant colony algorithm withouthierarchical restricted searching area, the single population ant colony algorithm based onhierarchical restricted searching area and the multi-population ant colony algorithm based onhierarchical restricted searching area are provided by analyzing the algorithm running timeand the planning path quality.Results show that under the condition of large-scale network,the strategy based on hierarchical restricted searching area has a certain advantage, whileadopting the strategy of hierarchical restricted searching area, the average searching time ofant colony algorithm is much smaller than Dijkstra algorithm. The experiment also shows thatalthough the length of planning path of multi-population ant colony algorithm is longer, thetime is smaller than other algorithms, the reason is that it considers the factor of trafficcongestion, when there have traffic congestion, it timely turns to low layer network andchooses the local road or the collector road near the congestion road, thus saving the waitingtime due to the congestion.