Time Constrained Dynamic Road Network Path Planning Algorithm Design And Implement

Static road networks cannot reflect real-time transportation. Likewise, traditional navigation system, based on static data to plan the shortest path, cannot refer to real-time traffic information either. Nowadays, the development of transportation technology fos-ters easier access to real-time traffic information. Therefore, a dynamic path-planning algorithm based on real-time traffic information is more applicable to modern navi-gation devices. Under certain circumstances, the constantly changing road networks allows of little computation time for working out optimal routine due to users’high real-time demand of dynamic path planning algorithm. On one hand, dynamic path planning algorithm should guarantee the quality of return path within limited computa-tion time. On the other hand, multi-core technology has greatly improved the computing power of navigation devices, making a parallel algorithm possible.This paper mainly works on three aspects.1. Research on the improvement of dynamic path-planning algorithm.This paper aims to improve traditional real-time road networks model. During one trip, a user’s waiting delay at the crossroad accounts for20%-40%of the total time, which cannot be ignored. Traditional road networks model generally calculate the time of passing a road with certain weight. By doing so, on one hand, it cannot help to collect and compute real-time information. On the other hand, the degree of traffic congestion cannot be embodied. In terms of the two drawbacks mentioned above, this paper aims to improve dynamic road networks delivery by introducing crossroad ratio and road resistance ratio, so as to facilitate subsequent algorithm computation.2. Analysis of existing dynamic path-planning algorithms and WD*algorithm proposalExisting dynamic path-planning algorithms will be discussed in terms of their al-gorithm ideas, based on which WD*algorithm shall be proposed. By comparing the experimental navigation results of these algorithms, it is found that AD*algorithm tends to allocate more nodes into the next search session, adding more computation to work out optimal routine. However, WD*algorithm achieves better performance in high real-time demand circumstances.3. APWD*algorithm proposal based on multi-core navigation devices and WD*algorithmThe changing impact factor ε enables algorithm WD*to adjust computation time and path quality so that multi-core navigation devices boast parallel computing power. Therefore, the cases in which WD*algorithm runs in parallel with WD*algorithm with varied impact factor ε, can guarantee the path quality in each search session. Experi-ments show that despite differences in computation time and return path quality under different algorithms, the latter can accommodate varied real-time navigation demands by adjusting impact factors reasonably.