基于改进HH算法的路径规划系统设计与实现

张冠湘; 周兴; 蔡文学; 钟慧玲; 许靖

doi:10.3969/j.issn.0258-2724.2013.05.026

基于改进HH算法的路径规划系统设计与实现

doi: 10.3969/j.issn.0258-2724.2013.05.026

基金项目:

中央高校基本科研业务费专项资金资助项目(X2JMD2117950,2013XZD05)

国家社会科学基金资助项目(11CGL088)

教育部人文社会科学研究项目(10YJC630373,12YJAZH209)

计量
- 文章访问数: 990
- HTML全文浏览量: 56
- PDF下载量: 564
- 被引次数: 0
出版历程
- 收稿日期: 2012-06-03
- 刊出日期: 2013-10-25

Design and Implementation of Path Planning System Based on Improved Highway-Hierarchical Algorithm

摘要

摘要: HH (Highway-Hierarchical)算法是近年来一种高效路径规划算法,但存在的路网压缩成环问题、预处理数据存储问题和完整最短路计算问题,采用无环压缩策略、分层存储策略和局部最短路存储策略对算法进行了改进.以改进的算法为核心,在Internet环境下,运用WCF分布式技术,设计与实现了高效路径规划系统.系统测试结果表明,改进HH算法在时间效率上平均是原算法的5.03倍,在空间效率上约是原算法的4倍.在性能上,路径规划系统能满足互联网环境下用户并发访问的高效性需求;在功能上,系统提供了最短路的里程、行程时间、行程费用、主要路段及文字描述等.
- Highway-Hierarchical算法 /
- WCF技术 /
- 路径规划
Abstract: Highway-Hierarchical algorithm is a highly efficient path planning approach in the recent years. In the preliminary data manipulation process, there are problems of compressed ring road in the network, the strategies of multi-layer data storage, and the calculation of the optimal route. To resolve these issues, the paper proposes to use the no-cycle compressing strategy, the tiered storage strategy, and the local shortest path storage strategy to improve the efficiency of the algorithm. Under the internet settings, the paper designs the highly efficient route planning system by improving the Highway-Hierarchical algorithm with the WCF technology. The results show that the improved system is 5.03 and 4 times of temporal and spatial efficiency, respectively, as opposed to the original algorithm. The route planning system can meet the high users' demand and also provides the general information on the travel time, mileage, travel expenses, critical sections, text description, etc.
- Highway-Hierarchical algorithm /
- WCF technology /
- path planning

HTML全文

参考文献(23)

邹亮,徐建闽. 空间数据挖掘在基于GIS的交通诱导系统中的应用[J].华南理工大学学报:自然科学版,2004,32(增刊1): 129-132. ZOU Liang, XU Jianmin. Application of spatial data mining in the transportation guidance system based on GIS[J]. Journal of South China University of Technology: Natural Science, 2004, 32(S1): 129-132.

朱弘戈. 基于交通网络数据集的动态路径诱导系统规划与实现探讨[J]. 交通标准化,2011(7): 196-202. ZHU Hongge. Dynamicroute guidance system planning and realization based on traffic network data set[J].Transport Standardization, 2011(7): 196-202.

章权,温惠英,孙博. 适于配送车辆导航路径规划的遍历模型的改进型粒子群优化算法[J]. 华南理工大学学报:自然科学版,2011,39(8): 109-117. ZHANG Quan, WEN Huiying, SUN Bo. Improved particle swarm optimization algorithm of ergodic model for routing planning of delivery vehicle navigation[J]. Journal of South China University of Technology: Natural Science, 2011, 39(8): 109-117.

温惠英,徐建闽,林正春. 适于物流配送车辆导航路径优化的遗传算法[J]. 华南理工大学学报:自然科学版,2009,37(2): 82-91. WEN Huiying, XU Jianmin, LIN Zhengchun. Genetic algorithm for route optimization of vehicle navigation in logistics distribution[J]. Journal of South China University of Technology: Natural Science, 2009, 37(2): 82-91.

HART P E, NILSSON N J, RAPHAEL B. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on System Science and Cybernetics, 1968, 4(2): 100-107.

LO W, ZWICKER M. Bidirectional search for interactive motion synthesis[J]. Computer Graphics Forum, 2010, 29(2): 563-573.

GOLDBERG A V,HARRELSON C. Computing the shortest path:A* meets graph theory.Technical Report MSR-TR-2004-24, Microsoft Research, 2004.

GOLDBERG A V, HARRELSON C. Computing the shortest path: A* meets graph theory[C]//16th ACM-SIAM Symposium on Discrete Algorithms. Vancouver:[s.n.], 2005: 156-165.

GOLDBERG A V, WERNECK R F. Computing point-to-point shortest paths from external memory[C]//Workshop on Algorithm Engineering and Experiments (ALENEX). Vancouver:[s.n.], 2005: 26-40.

SCHULZ F, WAGNER D, ZAROLIAGIS C D. Using multi-level graphs for timetable information in railway systems[C]//Workshop on Algorithm Engineering and Experiments(ALENEX).[S.l.]: Springer Berlin Heidelberg, 2002: 43-59.

MULLER K. Design and implementation of an efficient hierarchical speed-up technique for computation of exact shortest paths in graphs[D]. Karlsruhe: Universität Karlsruhe(TH), 2006.

SCHULTES D. Fast and exact shortest path queries using highway hierarchies[D]. Saarbrücken: Universität des Saarlandes, 2005.

SCHULTES D, Route planning in road networks[D]. Karlsruhe: Universität Karlsruhe(TH), 2008.

BAST H, FUNKE S, SANDERS P, et al. Fast routing in road networks with transit nodes[J]. Sience, 2007, 316: 566-566.

SOMMER C. Approximate shortest path and distance queries in networks[D]. Tokyo: The University of Tokyo, 2010.

郑烟武. 基于分层分区的动态路径规划算法研究[D]. 广州: 华南理工大学,2011.

HOLZER M, SCHULZ F, WILLHALM T. Combining speed-up techniques for shortest-path computations[C]//3rd International Workshop on Experimental and Efficient Algorithms(WEA).[S.l.]: Springer-Verlag, 2004: 269-284.

DELLING D, SANDERS P, SCHULTES D, et al. Highway hierarchies star[DB/OL].[2012-04-12] http:[C]//arrival.cti.gr/index.php/Documents/0011.

严商. 基于WCF的分布式程序的研究与实现[D].武汉:武汉理工大学,2008.

周兴. 面向Internet的动态路径规划算法研究与应用系统设计[D].广州:华南理工大学经济与贸易学院,2011.

于加晴,查建中,陆一平,等. 基于SOA 的分布式并行协同设计架构[J]. 北京交通大学学报,2009,33(5): 69-72. YU Jiaqing, CHA Jianzhong, LU Yiping, et al. Research on the distributed concurrent and collaborative design architecture based on SOA[J]. Journal of Beijing Jiaotong University, 2009, 33(5): 69-72.

周劲,刘洋,蔺永政. 一种基于Web Service的分布式应用系统的设计[J]. 计算机应用研究,2007(2): 238-239. ZHOU Jing, LIU Yang, LIN Yongzheng. Design of distributed application system based on Web service[J]. Application Research of Computers,2007(2): 238-239.

LOWY J. Programming WCF services[M]. Sebastopol: O'Reilly Press, 2007: 120-200.

施引文献

附加材料(0)

访问统计

点击查看大图

计量

文章访问数: 990
HTML全文浏览量: 56
PDF下载量: 564
被引次数: 0

基于改进HH算法的路径规划系统设计与实现

doi: 10.3969/j.issn.0258-2724.2013.05.026

计量

出版历程

Design and Implementation of Path Planning System Based on Improved Highway-Hierarchical Algorithm

计量

出版历程

目录