中心式诱导路径优化计算方法

基于并行计算技术和网络数据存储方法, 考虑了出行者的偏好, 分析了多级网络分解方法和双端队列最短路径计算方法, 提出了一种新的中心式诱导路径优化计算方法。以长沙市和长春市城市路网的实际数据为基础, 在普通PC机群、联想服务器机群及惠普工作站机群3种不同计算性能的并行计算平台上进行试验测试。测试结果表明: 使用网络数据存储方法, 能够直接确定邻接节点与相应弧的存储位置, 节点信息的查询时间明显减小; 使用多级网络分解方法, 主要路段作为被切割弧的概率降低, 最短路径计算过程中处理器的通信量减小; 使用双端队列最短路径计算方法, 最短路径计算速度明显提升; 使用新的计算方法, 长沙市路网中400万条最短路径计算时间为46s, 长春市路网中1 170万条最短路径计算时间为72s, 完全能够满足中心式诱导路径优化时间小于5min的要求。

Calculation method of central guidance path optimization

Based on parallel calculation technology and network data storage method, traveler preferences were considered, the multi-level network decomposing method and the shortest path calculation method of deque were analyzed, and a new central guidance path optimization calculation method was put out. On the basis of the practical data of road networks in Changsha City and Changchun City, and tests on three different parallel calculation platforms including ordinary PC cluster, Lenovo server cluster and HP workstation cluster were carried out. Test result indicates that by using network data storage method, the storage locations of adjacency nodes and corresponding arcs can be determined directly, and the query time of node information obviously decreases. According to multi-level network decomposing method, the probability of main road as cutted arc reduces, and the commutation amounts of processors during the shortest path calculation process reduce. By using the shortest path calculation method of deque, the calculation speed of shortest path obviously increases. Through the new calculation method, the calculation time of 4 million shortest paths in Changsha City is 46 s, the calculation time of 11.7 million shortest paths in Changchun City is 72 s, and both of them satisfy the demand that central guidance path optimization time should be less than 5 rain.