基于网络分割技术的交通最短路径应用

Traffic Shortest Path Application Based on the Network Segmentation Technology

为了提高城市大规模路网实时算法的效率,在分析各种算法复杂度基础上,阐述并行算法原理及相关参数设计。基于对最短路问题各种算法复杂度的深入分析,采用标号算法中的网络分割技术,将昆明市道路网络简化处理,分割为若干小的子网络。在此基础上对最短路径问题的并行算法进行了探讨。通过仿真实验模拟,数据证实了基于并行算法的最短路径优化算法,即使面向网格粗分、细分的情形,仍然能够保证强劲的加速比和较高的运行效率,且具有良好的可移植性。

On the basis of analyzing the complexity of various algorithms,this paper expounds the princi-ple of parallel algorithms and the design of related parameters to improve the efficiency of real -time algo-rithms of large -scale urban road network.Based on the deep analysis of the complexity of the algorithm for the shortest path problem,the network segmentation technology of the label algorithm is used to sim-plify the processing of the road network in Kunming.Parallel algorithm for the shortest path problem is discussed.Through simulation modeling,data confirmed that the parallel optimization algorithm based on the shortest path,even for coarse grid points,the situation subdivision,still be able to ensure a strong speedup and higher operating efficiency and has good portability.