论文部分内容阅读
基于并行计算技术和网络数据存储方法,考虑了出行者的偏好,分析了多级网络分解方法和双端队列最短路径计算方法,提出了一种新的中心式诱导路径优化计算方法。以长沙市和长春市城市路网的实际数据为基础,在普通PC机群、联想服务器机群及惠普工作站机群3种不同计算性能的并行计算平台上进行试验测试。测试结果表明:使用网络数据存储方法,能够直接确定邻接节点与相应弧的存储位置,节点信息的查询时间明显减小;使用多级网络分解方法,主要路段作为被切割弧的概率降低,最短路径计算过程中处理器的通信量减小;使用双端队列最短路径计算方法,最短路径计算速度明显提升;使用新的计算方法,长沙市路网中400万条最短路径计算时间为46s,长春市路网中1 170万条最短路径计算时间为72s,完全能够满足中心式诱导路径优化时间小于5min的要求。
Based on parallel computing techniques and network data storage methods, the preferences of travelers are considered, the multi-level network decomposition method and the shortest path calculation method of double-ended queue are analyzed, and a new method of center-centered guidance path optimization calculation is proposed. Based on the actual data of urban road network in Changsha City and Changchun City, this paper tests and tests on three kinds of parallel computing platforms with different computational performance of common PC cluster, Lenovo server cluster and HP workstation cluster. The test results show that the network data storage method can directly determine the storage location of adjacent nodes and the corresponding arcs, and the query time of node information decreases obviously. With the multi-level network decomposition method, the probability of the main road sections being cut arcs decreases and the shortest path In the process of calculation, the traffic of the processor is reduced. Using the shortest path calculation method of double-ended queue, the calculation speed of the shortest path is obviously improved. Using the new calculation method, the computation time of the 4 million shortest paths in the Changsha road network is 46s. The computation time of the shortest route of 1 1.7 million in the road network is 72s, which can fully meet the requirement of less than 5min in which the center-based guidance path optimization time is optimized.