一对一最短路径算法研究及车载导航系统设计
|
摘要
最短路径问题常见于物流运输、车载导航与通讯网络等之中,有许多基于经典Dijkstra算法的求解方法已被一一提出。不论是在物流运输或者是在车载导航中,最常应用到的最短路径问题就是一对一最短路径问题。
本文首先介绍了各种常用的一对一最短路径算法,包括各种经典算法、A*算法、遗传算法和蚁群算法,并对它们各自的优缺点进行了详细的比较。
然后,本文以日益成熟的多核与多线程技术为基础,改良传统的A*算法,设计了一种基于多核多线程的A*算法。经过测试系统验证,该算法结合本文对标准二叉堆的改进——直接插入二叉堆数据结构,能够大幅地提高一对一最短路径搜索的时间效率
接着,针对大规模网络中一对一最短路径搜索的性能需求以及一对一最短路径模型的特征,本文对遗传算法进行了一系列改进,包括种群初始化方法、选择方法、交叉方法和变异方法,并且实现了交叉率和变异率的自适应调整。测试结果证明,该自适应遗传算法快速、灵活,能够有效地避免断路和环路,并且能够满足大规模网络中一对一最短路径搜索的需求。
最后,本文运用上述基于多核多线程的A*算法,在嵌入式平台上以Eclipse为工具设计并实现了一个Android版的动态实时车载导航系统,并在南昌市电子地图真实路网上实际运行该系统,取得了良好的效果。
Shortest path problems are often found in logistics distribution, on-vehicle navigation, communication network and so on, and many efficient algorithms based on classical Dijkstra algorithm have been developed already. No matter in logistics distribution or in on-vehicle navigation, one-to-one shortest path problem is the most common issue among all kinds of shortest path problems.
First, all kinds of often used one-to-one shortest path algorithms are introduced in this paper, including classical algorithms. A*algorithm, Genetic Algorithm and Ant Colony Algorithm. And their advantages and disadvantages are compared with each other in quite detail.
Secondly, based upon the increasingly mature multicore and multithread techniques, traditional A*algorithm is improved and an A*algorithm based upon multicore and multithread is developed. Tests show that this multicore and multithread based A*algorithm incorporating directly inserted binary heap data structure improved from standard binary heap can enhance the searching efficiency of one-to-one shortest path to a great extent.
Thirdly, aiming at the performance requirement of one-to-one shortest path problem in large size network and the characteristics of one-to-one shortest path model. a series of improvements are made upon Genectic Algorithm, including initializing method of population. selection method, crossover method and mutation method, and the crossover ratio and mutation ratio can be adjusted adaptively. It is proved by tests that this adaptive Genetic Algorithm is high-speed and flexible, can effectively avoid broken roads and loop roads, and can satisfy the requirement of one-to-one shortest path problem in large size network.
Finally, by adopting above multicore and multithread based A*algorithm. an on-vehicle navigation system of Android edition is developed on embedded platform using Eclipse. And this on-vehicle navigation system is evaluated on the electronic map of Nanchang city and gets very good results.
本文首先介绍了各种常用的一对一最短路径算法,包括各种经典算法、A*算法、遗传算法和蚁群算法,并对它们各自的优缺点进行了详细的比较。
然后,本文以日益成熟的多核与多线程技术为基础,改良传统的A*算法,设计了一种基于多核多线程的A*算法。经过测试系统验证,该算法结合本文对标准二叉堆的改进——直接插入二叉堆数据结构,能够大幅地提高一对一最短路径搜索的时间效率
接着,针对大规模网络中一对一最短路径搜索的性能需求以及一对一最短路径模型的特征,本文对遗传算法进行了一系列改进,包括种群初始化方法、选择方法、交叉方法和变异方法,并且实现了交叉率和变异率的自适应调整。测试结果证明,该自适应遗传算法快速、灵活,能够有效地避免断路和环路,并且能够满足大规模网络中一对一最短路径搜索的需求。
最后,本文运用上述基于多核多线程的A*算法,在嵌入式平台上以Eclipse为工具设计并实现了一个Android版的动态实时车载导航系统,并在南昌市电子地图真实路网上实际运行该系统,取得了良好的效果。
Shortest path problems are often found in logistics distribution, on-vehicle navigation, communication network and so on, and many efficient algorithms based on classical Dijkstra algorithm have been developed already. No matter in logistics distribution or in on-vehicle navigation, one-to-one shortest path problem is the most common issue among all kinds of shortest path problems.
First, all kinds of often used one-to-one shortest path algorithms are introduced in this paper, including classical algorithms. A*algorithm, Genetic Algorithm and Ant Colony Algorithm. And their advantages and disadvantages are compared with each other in quite detail.
Secondly, based upon the increasingly mature multicore and multithread techniques, traditional A*algorithm is improved and an A*algorithm based upon multicore and multithread is developed. Tests show that this multicore and multithread based A*algorithm incorporating directly inserted binary heap data structure improved from standard binary heap can enhance the searching efficiency of one-to-one shortest path to a great extent.
Thirdly, aiming at the performance requirement of one-to-one shortest path problem in large size network and the characteristics of one-to-one shortest path model. a series of improvements are made upon Genectic Algorithm, including initializing method of population. selection method, crossover method and mutation method, and the crossover ratio and mutation ratio can be adjusted adaptively. It is proved by tests that this adaptive Genetic Algorithm is high-speed and flexible, can effectively avoid broken roads and loop roads, and can satisfy the requirement of one-to-one shortest path problem in large size network.
Finally, by adopting above multicore and multithread based A*algorithm. an on-vehicle navigation system of Android edition is developed on embedded platform using Eclipse. And this on-vehicle navigation system is evaluated on the electronic map of Nanchang city and gets very good results.
引文
[1]杨兆升.智能运输系统概论(第二版)[M].北京：人民交通出版社,2009.
[2]李雨奇.我国公路交通安全状况综述[J].科技创新导报,2011,29：242.
[3]Erkut E. The Road Not Taken[J]. ORMS Today.1996.23:22-28.
[4]Evans J.R., Minieka E. Optimization Algorithms for Networks and Graphs[M]. Marcel Dekker. 1992.
[5]Glover F., Klingman D., Philips N. A New Polynomially Bounded Shortest Paths Algorithm[J]. Operations Research.1985.33:65-73.
[6]Glover F., Klingman D., Phillips N. et al. New polynomial shortest path algorithms and their computational attributes[J]. Management Science,1985.31(9):1106-1128.
[7]Goldberg A. V., Kaplan H., Werneck R. F. Reach for A*:Efficient Point-to-Point Shortest Path Algorithms[C]. Proceedings of the Workshop on Algorithm Engineering and Experiments, 2006:129-143.
[8]Goldberg A. V.. Radzik T. A. Heuristic Improvement of the Bellman-Ford Algorithm[J]. Applied Mathematics Letter,1993.6:3-6.
[9]Han Y.. Pan V., John Reif. Efficient parallel algorithms for computing all pair shortest paths in directed graphs[C]. Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents. San Diego. California. United States.1992:353-362.
[10]Hung M. H.. Divoky J. J. A Computational Study of Efficient Shortest Path Algorithms[J]. Computers & Operations Research.1988.15:567-576.
[11]Mikhail J. Atallah. Efficient Parallel Algorithms for Planar st-Graphs[C]. Proceedings of the 8th International Symposium on Algorithms and Computation,1997:223-232.
[12]Tsung-Ping Yang. Li-Hsing Ho. A Study of Pick-up and Delivery Problem with Time Windows using GIS-Courier Forwarding Industry as an Example[J]. The Business Review. Cambridge.2005.4(2):167-174.
[13]陆锋.最短路径算法：分类体系与研究进展[J].测绘学报,2001.30(3)：269-275.
[14]Pallottino S. Shortest-Path Methods:Complexity. Interrelations and New Propositions[J]. Networks.1984.14:257-267.
[15]钱晓捷,李秀芳.基于多核多线程的排序算法优化和实现[J].微电子学与计算机,2011.28(1)：116-119.
[16]Geisberger R.. Sanders P.. Schultes D. Contraction Hierarchies:Faster and Simpler Hierarchical Routing in Road Networks[C].6th Workshop on Experimental Algorithms, 2008:319-333.
[17]Klunder G. A.. Post H. N. The Shortest Path Problem on Large-Scale Real-Road Networks[J]. NETWORKS.2006.48(4):182-194.
[18]Shang Qian-Ming. Yan Xin-Ping. Optimization analysis about Dijkstra algorithm in ITS[J]. Journal of Wuhan University of Technology,2007,29(4).122-124,143.
[19]Sanders P., Schultes D.,Vetter C. Mobile Route Planning[C]. Proceedings of the 16th annual European symposium on Algorithms,2008:732-743.
[20]Tsung-Ping Yang, Li-Hsing Ho. The Comparison and Study of Shortest Path Algorithm in Heaps-Using a Taiwan Route Map as an Example[J]. The Journal of American Academy of Business, Cambridge,2006,8(1):139-146.
[21]Ji Xiao-yu. Models and algorithm for stochastic shortest path problem[J]. Applied Mathematics and Computation,2005,170:503-514.
[22]Meyer U., Osipov V. Design and Implementation of a Practical I/O-Efficient Shortest Paths Algorithm[C]. Proceedings of the Workshop on Algorithm Engineering and Experiments, 2009:85-96.
[23]Bauer R., Delling D. SHARC:Fast and Robust Unidirectional Routing[C]. Proceedings of the Workshop on Algorithm Engineering and Experiments,2008:13-26.
[24]Soltani A.R., Tawfik H., Goulermas J. Y. Path Planning in Construction Sites:Performance Evaluation of the Dijkstra, A*, and GA Search Algorithms[J]. Advanced Engineering Informatics,2002,16:291-303.
[25]Hao Yue, Chunfu Shao. Study on the Application of A* Shortest Path Search Algorithm in Dynamic Urban Traffic[C]. ICNC,3rd International Conference.2007:463-469.
[26]谭国真,高文.时间依赖网络中最小时间路径算法[J].计算机学报,2002.25(2)：45-49.
[27]万玮,刘哗,李立宏等.采用联合优化方式的最佳路径算法研究[J].计算机工程与应用,200730：97-100.
[28]窦桂琴,杨青,黄祖锋.一种基于城市应急系统的最短路径算法[J].广西师范大学学报(自然科学版),2007,25(4)：92-95.
[29]卢照,师军.并行最短路径搜索算法的设计与实现[J].计算机工程与应用,2010,46(3)：69-71.
[30]付天成,莫橙海,王晖等.基于Agent的动态路网行车最短路径求解[J].计算机工程,2008,34(20)：203-205.
[31]胡耀民,刘伟铭.多约束最短路径模型与求解[J].湖南科技大学学报(自然科学版),2010,25(1)：87-90.
[32]郝振国,王玉玫.双向A*算法在军事路径规划中的应用[J].计算机工程与应用,2011,47(29)：246-248.
[33]王海梅,周献中.直线优化A*算法在最短路径问题中的改进与实现[J].工程图学学报.2009,6：121-126.
[34]李志建等.改进A*算法及其在GIS路径搜索中的应用[J].系统仿真学报,2009.10(2)：3117-3119.
[35]邹亮,徐建闽.基于遗传算法的动态网络中最短路径问题算法[J].计算机应用,2005,25(4)：57-60.
[36]温惠英,徐建闽,林止春.适于物流配送车辆导航路径优化的遗传算法[J].华南理工大学学报(自然科学版),2009.37(2)：82-86.
[37]温惠英,徐建闽,邹亮.基于遗传算法的离散时间动态网络最短路径求解[J].华南理工大学学报(自然科学版).2008.36(2)：14-16.
[38]康晓军,王茂才.基于遗传算法的最短路径问题求解[J].计算机工程与应用,2008.44(23)：22-24.
[39]李擎,谢四江,童新海等.一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A*算法的比较[J].北京科技大学学报,2006,11：1082-1086.
[40]黄贵玲,高西全,靳松杰等.基于蚁群算法的最短路径问题的研究和应用[J].计算机工程与应用.2007,43(13)：233-235.
[41]刘志硕等.基于自适应蚁群算法的车辆路径问题研究[J].控制与决策,2005(5)：562-566.
[42]靳凯文,李春葆,秦前清.基于蚁群算法的最短路径搜索方法研究[J].公路交通科技,2006,23(3)：134-138.
[43]温惠英等.基于改进型蚁群算法的车辆导航路径规划研究[J].公路交通科技,2009,1(26)：126-129.
[44]王海梅,周献中.网络系统中的最短路径分析及其应用研究[J].兵工学报,2006,27(3)：515-518.
[45]付梦印,李杰.基于分层道路网络的新型路径规划算法[J].计算机辅助设计与图形学学报.2005,17(4)：720-721.
[46]步兵.数字地图最短路径的算法研究[D].中国地质大学,2008.
[47]杨柳.车载导航系统中路径规划算法的研究及实现[D].北京交通大学,2008.
[48]鲁慧鑫.基于A-GPS混合定位的车载定位导航系统路径规划研究与应用实现[D].北京邮电大学.2009.
[49]田明星.路径规划在车载导航系统中的应用研究[D].北京交通大学,2009.
[50]杨易.智能车辆组合定位与路径导航技术研究[D].湖南大学,2006.
[51]许永.车载导航系统中最优路径规划方法研究[D].吉林大学,2007.
[52]Dijkstra E. W. A Note on Two Problems in Connection with Graphs[J]. Numeriche Mathematic,1959,6:269-271.
[53]Floyd, Robert W. Algorithm 97:Shortest Path[J]. Communications of the ACM,1962,5(6): 345.
[54]Mondou J. F., Crainic T. G., Nguyen S. Shortest path algorithms:A Computational Study with the C Programming Language[J]. Computers & Operations Research,1991:18,(8):767-786.
[55]Ahuja R. K., Mehlhorn K., Orlin J. B. et al. Faster Algorithms for the Shortest Path problem[J]. Journal of the Association for Computing Machinery,1990,37(2):213-223.
[56]Zhan F. B., Noon C. E. Shortest Path Algorithms:An Evaluation Using Real Road Networks[J]. Transportation Science,1998,32:65-73.
[57]Cherkassky B.V., Goldberg A. V.. Radzik T. Shortest paths algorithms:Theory and experimental evaluation[J]. Mathematical Programming,1996,73:129-174.
[58]Dial R. B., Glover F., Karney D. et al. A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees[J]. Networks.1979.9:215-248.
[59]Pape U. Implementation and Efficiency of Moore Algorithms for the Shortest Root Problem[J]. Mathematical Programming,1974,7:212-222.
[60]Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms[J]. Journal of ACM,1987.34(3):596-615.
[61]杨琮平.多执行绪基础下一对一最短路径搜索系统建立之研究[D].中华大学,2006.
[62]Dantzig. G. B. On the shortest route through a network[J]. Management Science,1960, 6:187-190.
[63]Dial R. B. Algorithm 360:Shortest Path Forest with Topological Ordering[J]. Communications of the ACM,1969,12:632-633.
[64]Han Y., Pan V., John Reif. Efficient parallel algorithms for computing all pair shortest paths in directed graphs[C]. Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents, San Diego, California, United States,1992, 353-362.
[65]Bellman Richard. On a routing problem[J]. Quarterly of Applied Mathematics,1958,16: 87-90.
[66]Cordeau J. F. A guide to vehicle routing heuristics[J]. The Journal of the Operational Research Society,2002.53(5):512-522.
[67]Osman I. H., James P. K. Meta-heuristics:Theory & Applications[M]. Kluwer Academic, 1996.
[68]王鹏程,夏洁.基于特殊双向A*搜索算法的三维航迹规划[J].系统仿真学报,2009,20(8)：229-233.
[69]任波,周焘,于雷.基于改进A*算法的飞行器三维航迹规划算法[J].系统工程与电子技术,2008,30(2)：324-326.
[70]宋建梅,李侃.基于A*算法的远程导弹三维航迹规划算法[J].北京理工大学学报,2007,27(7)：613-614.
[71]武雪玲,李清泉,任福.基于分层分块数据组织的双向A*算法[J].测绘信息与工程,2006,31(6)：1-3.
[72]陈曦,费奇,李炜.基于启发式策略的最短路径算法[J],华中科技大学学报(自然科学版),2006,12：4-6.
[73]Holland J. Adaptation in natural and artificial systems[M]. Ann Arbor:University of Michigan Press,1975:5-15.
[74]吴莲.基于城市道路网的遗传最短路径算法研究[D].南京理工大学,2010.
[75]Dorigo M.蚁群优化[M].北京：清华大学出版社,2005.
[76]Wang Ling. Intelligent Optimization Algorithms with Applications[M]. Tsinghua University Press,2001.
[77]郝伟.蚁群最短路径算法优化及其在GIS中的应用研究[D].西北大学,2009.
[78]陈艳.基于蚁群算法的最优路径选择研究[D].北京交通大学,2007.
[79]于芹.基于蚁群算法的物流车辆路径优化问题的研究[D].上海交通大学,2007.
[80]孙中华.GIS路径寻优中的蚁群算法研究[D].南京理工大学,2009.
[81]严蔚敏,吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,2011.
[82]Thomas H. Cormen. Charles E. Leiserson.算法导论(第2版)[M].潘金贵,顾铁成,李成法等译.北京：机械工业出版社,2006.
[83]Gallo G., S. Pallottino. Shortest Path Methods in Transportation Models[J]. Transportation Planning Models,1984:227-256.
[84]Goldberg. A.V., C. Silverstein. Implementations of Dijkstra's algorithm based on multi-level buckets[R]. NEC Research Institute:Princeton, NJ.1995.
[85]Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths in graphs[J]. IEEE Trans. Syst. Sci. and Cybernetics,1968, 4(2):100-107.
[86]Jim Beveridge, Robert Wiener. Win32多线程程序设计[M].侯捷译.武汉：华中科技大学出版社,2002.
[87]Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows:Theory, Algorithms and Applications[M]. Englewood Cliffs, NJ:Prentice Hall,1993.
[88]龙毅,温永宁,盛业华.电子地图学[M].科学出版社,2009.
[89]吴忻.基于GPS定位和电子地图的最佳路径搜索[D].西安电子科技大学.2006.
[90]姚俊杰.基于嵌入式电子地图的导航路径规划研究[D].浙江工业大学,2007.
[91]宋莺,李清泉,郑年波等.基于GPRS/Web Service的分布式车辆监控与信息服务平台[J].武汉大学学报(信息科学版).2007,12：14-17.
[92]宋雅丽,唐晓晟.基于OSGi家庭网关和Web Service技术的智能家庭系统[J].计算机应用.2007,27(6)：1542-1544.
[93]Tan Zhihua. The application of GPS/GIS Navigation and Positioning System in Cross-country Orienteering[C].2008 International Conference on Computer Science and Software Engineering. TsingHua University. Peking, China,2008:582-584.
[94]Gannan Yuan, Zhi Zhang, Wei Shang Guan. Research and Design of GIS in Vehicle Monitoring System[C].2008 International Conference on Internet Computing in Science and Engineering. School of Automation. Harbin Engineering University, IEEE Computer society, 2008:223-228.
[95]徐洪勇.基于GIS的最短路径算法改进对比研究[D].中国地质大学,2008.
[96]刘洋.基于QTE的GIS车载导航系统的设计与实现[D].重庆大学,2009.
[97]蔡翔陵.嵌入式车用资讯系统平台之开发[D].元智大学,2007.
[98]Raj Kamal.嵌入式系统--体系结构、编程与设计(第2版)[M].贾建斌,李化译.北京：清华大学出版社,2010.
[99]杨丰盛.Android应用开发揭秘[M].机械工业出版社,2011.
[100]农丽萍,干力虎,黄一平.Android在嵌入式车载导航系统的应用研究[J].计算机工程与设计.2010.31(11)：2473-2476.
[101]胡石根.车载终端实时交通导航技术的研究及实现[D].华南理工大学.2010.
[102]吴建洪.车载导航系统的研究与实现[D].湖南大学.2007.
[103]汀春鹏.基于GPS/GPRS勺车载导航系统的设计与实现[D].山东大学,2008.
[104]王莉.嵌入式车载导肮监控系统设计与应用[D].北方工业大学,2009.
[105]田立东.汽车车载定位导航监控系统研究与设计[D].吉林大学,2007年.
[106]李庭贵.嵌入式车载导航终端的设计[J].制造业自动化,2009.31(05)：131-133.
[107]刘岳峰,张德,孙华波等.基于GPRS的组合式车载导航终端硬件设计[J].计算机工程,2009,35(2)：239-241.
[108]Jiang Liu, Bi Zeng, Xiu wen Yin et al. Designation and Realization of Ship Navigation System Embedded Platform Based on ARM[C]. Fifth International Symposium on Embedded Computing. IEEE Computer society,2008,20:227-232.
[2]李雨奇.我国公路交通安全状况综述[J].科技创新导报,2011,29：242.
[3]Erkut E. The Road Not Taken[J]. ORMS Today.1996.23:22-28.
[4]Evans J.R., Minieka E. Optimization Algorithms for Networks and Graphs[M]. Marcel Dekker. 1992.
[5]Glover F., Klingman D., Philips N. A New Polynomially Bounded Shortest Paths Algorithm[J]. Operations Research.1985.33:65-73.
[6]Glover F., Klingman D., Phillips N. et al. New polynomial shortest path algorithms and their computational attributes[J]. Management Science,1985.31(9):1106-1128.
[7]Goldberg A. V., Kaplan H., Werneck R. F. Reach for A*:Efficient Point-to-Point Shortest Path Algorithms[C]. Proceedings of the Workshop on Algorithm Engineering and Experiments, 2006:129-143.
[8]Goldberg A. V.. Radzik T. A. Heuristic Improvement of the Bellman-Ford Algorithm[J]. Applied Mathematics Letter,1993.6:3-6.
[9]Han Y.. Pan V., John Reif. Efficient parallel algorithms for computing all pair shortest paths in directed graphs[C]. Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents. San Diego. California. United States.1992:353-362.
[10]Hung M. H.. Divoky J. J. A Computational Study of Efficient Shortest Path Algorithms[J]. Computers & Operations Research.1988.15:567-576.
[11]Mikhail J. Atallah. Efficient Parallel Algorithms for Planar st-Graphs[C]. Proceedings of the 8th International Symposium on Algorithms and Computation,1997:223-232.
[12]Tsung-Ping Yang. Li-Hsing Ho. A Study of Pick-up and Delivery Problem with Time Windows using GIS-Courier Forwarding Industry as an Example[J]. The Business Review. Cambridge.2005.4(2):167-174.
[13]陆锋.最短路径算法：分类体系与研究进展[J].测绘学报,2001.30(3)：269-275.
[14]Pallottino S. Shortest-Path Methods:Complexity. Interrelations and New Propositions[J]. Networks.1984.14:257-267.
[15]钱晓捷,李秀芳.基于多核多线程的排序算法优化和实现[J].微电子学与计算机,2011.28(1)：116-119.
[16]Geisberger R.. Sanders P.. Schultes D. Contraction Hierarchies:Faster and Simpler Hierarchical Routing in Road Networks[C].6th Workshop on Experimental Algorithms, 2008:319-333.
[17]Klunder G. A.. Post H. N. The Shortest Path Problem on Large-Scale Real-Road Networks[J]. NETWORKS.2006.48(4):182-194.
[18]Shang Qian-Ming. Yan Xin-Ping. Optimization analysis about Dijkstra algorithm in ITS[J]. Journal of Wuhan University of Technology,2007,29(4).122-124,143.
[19]Sanders P., Schultes D.,Vetter C. Mobile Route Planning[C]. Proceedings of the 16th annual European symposium on Algorithms,2008:732-743.
[20]Tsung-Ping Yang, Li-Hsing Ho. The Comparison and Study of Shortest Path Algorithm in Heaps-Using a Taiwan Route Map as an Example[J]. The Journal of American Academy of Business, Cambridge,2006,8(1):139-146.
[21]Ji Xiao-yu. Models and algorithm for stochastic shortest path problem[J]. Applied Mathematics and Computation,2005,170:503-514.
[22]Meyer U., Osipov V. Design and Implementation of a Practical I/O-Efficient Shortest Paths Algorithm[C]. Proceedings of the Workshop on Algorithm Engineering and Experiments, 2009:85-96.
[23]Bauer R., Delling D. SHARC:Fast and Robust Unidirectional Routing[C]. Proceedings of the Workshop on Algorithm Engineering and Experiments,2008:13-26.
[24]Soltani A.R., Tawfik H., Goulermas J. Y. Path Planning in Construction Sites:Performance Evaluation of the Dijkstra, A*, and GA Search Algorithms[J]. Advanced Engineering Informatics,2002,16:291-303.
[25]Hao Yue, Chunfu Shao. Study on the Application of A* Shortest Path Search Algorithm in Dynamic Urban Traffic[C]. ICNC,3rd International Conference.2007:463-469.
[26]谭国真,高文.时间依赖网络中最小时间路径算法[J].计算机学报,2002.25(2)：45-49.
[27]万玮,刘哗,李立宏等.采用联合优化方式的最佳路径算法研究[J].计算机工程与应用,200730：97-100.
[28]窦桂琴,杨青,黄祖锋.一种基于城市应急系统的最短路径算法[J].广西师范大学学报(自然科学版),2007,25(4)：92-95.
[29]卢照,师军.并行最短路径搜索算法的设计与实现[J].计算机工程与应用,2010,46(3)：69-71.
[30]付天成,莫橙海,王晖等.基于Agent的动态路网行车最短路径求解[J].计算机工程,2008,34(20)：203-205.
[31]胡耀民,刘伟铭.多约束最短路径模型与求解[J].湖南科技大学学报(自然科学版),2010,25(1)：87-90.
[32]郝振国,王玉玫.双向A*算法在军事路径规划中的应用[J].计算机工程与应用,2011,47(29)：246-248.
[33]王海梅,周献中.直线优化A*算法在最短路径问题中的改进与实现[J].工程图学学报.2009,6：121-126.
[34]李志建等.改进A*算法及其在GIS路径搜索中的应用[J].系统仿真学报,2009.10(2)：3117-3119.
[35]邹亮,徐建闽.基于遗传算法的动态网络中最短路径问题算法[J].计算机应用,2005,25(4)：57-60.
[36]温惠英,徐建闽,林止春.适于物流配送车辆导航路径优化的遗传算法[J].华南理工大学学报(自然科学版),2009.37(2)：82-86.
[37]温惠英,徐建闽,邹亮.基于遗传算法的离散时间动态网络最短路径求解[J].华南理工大学学报(自然科学版).2008.36(2)：14-16.
[38]康晓军,王茂才.基于遗传算法的最短路径问题求解[J].计算机工程与应用,2008.44(23)：22-24.
[39]李擎,谢四江,童新海等.一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A*算法的比较[J].北京科技大学学报,2006,11：1082-1086.
[40]黄贵玲,高西全,靳松杰等.基于蚁群算法的最短路径问题的研究和应用[J].计算机工程与应用.2007,43(13)：233-235.
[41]刘志硕等.基于自适应蚁群算法的车辆路径问题研究[J].控制与决策,2005(5)：562-566.
[42]靳凯文,李春葆,秦前清.基于蚁群算法的最短路径搜索方法研究[J].公路交通科技,2006,23(3)：134-138.
[43]温惠英等.基于改进型蚁群算法的车辆导航路径规划研究[J].公路交通科技,2009,1(26)：126-129.
[44]王海梅,周献中.网络系统中的最短路径分析及其应用研究[J].兵工学报,2006,27(3)：515-518.
[45]付梦印,李杰.基于分层道路网络的新型路径规划算法[J].计算机辅助设计与图形学学报.2005,17(4)：720-721.
[46]步兵.数字地图最短路径的算法研究[D].中国地质大学,2008.
[47]杨柳.车载导航系统中路径规划算法的研究及实现[D].北京交通大学,2008.
[48]鲁慧鑫.基于A-GPS混合定位的车载定位导航系统路径规划研究与应用实现[D].北京邮电大学.2009.
[49]田明星.路径规划在车载导航系统中的应用研究[D].北京交通大学,2009.
[50]杨易.智能车辆组合定位与路径导航技术研究[D].湖南大学,2006.
[51]许永.车载导航系统中最优路径规划方法研究[D].吉林大学,2007.
[52]Dijkstra E. W. A Note on Two Problems in Connection with Graphs[J]. Numeriche Mathematic,1959,6:269-271.
[53]Floyd, Robert W. Algorithm 97:Shortest Path[J]. Communications of the ACM,1962,5(6): 345.
[54]Mondou J. F., Crainic T. G., Nguyen S. Shortest path algorithms:A Computational Study with the C Programming Language[J]. Computers & Operations Research,1991:18,(8):767-786.
[55]Ahuja R. K., Mehlhorn K., Orlin J. B. et al. Faster Algorithms for the Shortest Path problem[J]. Journal of the Association for Computing Machinery,1990,37(2):213-223.
[56]Zhan F. B., Noon C. E. Shortest Path Algorithms:An Evaluation Using Real Road Networks[J]. Transportation Science,1998,32:65-73.
[57]Cherkassky B.V., Goldberg A. V.. Radzik T. Shortest paths algorithms:Theory and experimental evaluation[J]. Mathematical Programming,1996,73:129-174.
[58]Dial R. B., Glover F., Karney D. et al. A Computational Analysis of Alternative Algorithms and Labeling Techniques for Finding Shortest Path Trees[J]. Networks.1979.9:215-248.
[59]Pape U. Implementation and Efficiency of Moore Algorithms for the Shortest Root Problem[J]. Mathematical Programming,1974,7:212-222.
[60]Fredman M. L., Tarjan R. E. Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms[J]. Journal of ACM,1987.34(3):596-615.
[61]杨琮平.多执行绪基础下一对一最短路径搜索系统建立之研究[D].中华大学,2006.
[62]Dantzig. G. B. On the shortest route through a network[J]. Management Science,1960, 6:187-190.
[63]Dial R. B. Algorithm 360:Shortest Path Forest with Topological Ordering[J]. Communications of the ACM,1969,12:632-633.
[64]Han Y., Pan V., John Reif. Efficient parallel algorithms for computing all pair shortest paths in directed graphs[C]. Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures table of contents, San Diego, California, United States,1992, 353-362.
[65]Bellman Richard. On a routing problem[J]. Quarterly of Applied Mathematics,1958,16: 87-90.
[66]Cordeau J. F. A guide to vehicle routing heuristics[J]. The Journal of the Operational Research Society,2002.53(5):512-522.
[67]Osman I. H., James P. K. Meta-heuristics:Theory & Applications[M]. Kluwer Academic, 1996.
[68]王鹏程,夏洁.基于特殊双向A*搜索算法的三维航迹规划[J].系统仿真学报,2009,20(8)：229-233.
[69]任波,周焘,于雷.基于改进A*算法的飞行器三维航迹规划算法[J].系统工程与电子技术,2008,30(2)：324-326.
[70]宋建梅,李侃.基于A*算法的远程导弹三维航迹规划算法[J].北京理工大学学报,2007,27(7)：613-614.
[71]武雪玲,李清泉,任福.基于分层分块数据组织的双向A*算法[J].测绘信息与工程,2006,31(6)：1-3.
[72]陈曦,费奇,李炜.基于启发式策略的最短路径算法[J],华中科技大学学报(自然科学版),2006,12：4-6.
[73]Holland J. Adaptation in natural and artificial systems[M]. Ann Arbor:University of Michigan Press,1975:5-15.
[74]吴莲.基于城市道路网的遗传最短路径算法研究[D].南京理工大学,2010.
[75]Dorigo M.蚁群优化[M].北京：清华大学出版社,2005.
[76]Wang Ling. Intelligent Optimization Algorithms with Applications[M]. Tsinghua University Press,2001.
[77]郝伟.蚁群最短路径算法优化及其在GIS中的应用研究[D].西北大学,2009.
[78]陈艳.基于蚁群算法的最优路径选择研究[D].北京交通大学,2007.
[79]于芹.基于蚁群算法的物流车辆路径优化问题的研究[D].上海交通大学,2007.
[80]孙中华.GIS路径寻优中的蚁群算法研究[D].南京理工大学,2009.
[81]严蔚敏,吴伟民.数据结构(C语言版)[M].北京：清华大学出版社,2011.
[82]Thomas H. Cormen. Charles E. Leiserson.算法导论(第2版)[M].潘金贵,顾铁成,李成法等译.北京：机械工业出版社,2006.
[83]Gallo G., S. Pallottino. Shortest Path Methods in Transportation Models[J]. Transportation Planning Models,1984:227-256.
[84]Goldberg. A.V., C. Silverstein. Implementations of Dijkstra's algorithm based on multi-level buckets[R]. NEC Research Institute:Princeton, NJ.1995.
[85]Hart P. E., Nilsson N. J., Raphael B. A formal basis for the heuristic determination of minimum cost paths in graphs[J]. IEEE Trans. Syst. Sci. and Cybernetics,1968, 4(2):100-107.
[86]Jim Beveridge, Robert Wiener. Win32多线程程序设计[M].侯捷译.武汉：华中科技大学出版社,2002.
[87]Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows:Theory, Algorithms and Applications[M]. Englewood Cliffs, NJ:Prentice Hall,1993.
[88]龙毅,温永宁,盛业华.电子地图学[M].科学出版社,2009.
[89]吴忻.基于GPS定位和电子地图的最佳路径搜索[D].西安电子科技大学.2006.
[90]姚俊杰.基于嵌入式电子地图的导航路径规划研究[D].浙江工业大学,2007.
[91]宋莺,李清泉,郑年波等.基于GPRS/Web Service的分布式车辆监控与信息服务平台[J].武汉大学学报(信息科学版).2007,12：14-17.
[92]宋雅丽,唐晓晟.基于OSGi家庭网关和Web Service技术的智能家庭系统[J].计算机应用.2007,27(6)：1542-1544.
[93]Tan Zhihua. The application of GPS/GIS Navigation and Positioning System in Cross-country Orienteering[C].2008 International Conference on Computer Science and Software Engineering. TsingHua University. Peking, China,2008:582-584.
[94]Gannan Yuan, Zhi Zhang, Wei Shang Guan. Research and Design of GIS in Vehicle Monitoring System[C].2008 International Conference on Internet Computing in Science and Engineering. School of Automation. Harbin Engineering University, IEEE Computer society, 2008:223-228.
[95]徐洪勇.基于GIS的最短路径算法改进对比研究[D].中国地质大学,2008.
[96]刘洋.基于QTE的GIS车载导航系统的设计与实现[D].重庆大学,2009.
[97]蔡翔陵.嵌入式车用资讯系统平台之开发[D].元智大学,2007.
[98]Raj Kamal.嵌入式系统--体系结构、编程与设计(第2版)[M].贾建斌,李化译.北京：清华大学出版社,2010.
[99]杨丰盛.Android应用开发揭秘[M].机械工业出版社,2011.
[100]农丽萍,干力虎,黄一平.Android在嵌入式车载导航系统的应用研究[J].计算机工程与设计.2010.31(11)：2473-2476.
[101]胡石根.车载终端实时交通导航技术的研究及实现[D].华南理工大学.2010.
[102]吴建洪.车载导航系统的研究与实现[D].湖南大学.2007.
[103]汀春鹏.基于GPS/GPRS勺车载导航系统的设计与实现[D].山东大学,2008.
[104]王莉.嵌入式车载导肮监控系统设计与应用[D].北方工业大学,2009.
[105]田立东.汽车车载定位导航监控系统研究与设计[D].吉林大学,2007年.
[106]李庭贵.嵌入式车载导航终端的设计[J].制造业自动化,2009.31(05)：131-133.
[107]刘岳峰,张德,孙华波等.基于GPRS的组合式车载导航终端硬件设计[J].计算机工程,2009,35(2)：239-241.
[108]Jiang Liu, Bi Zeng, Xiu wen Yin et al. Designation and Realization of Ship Navigation System Embedded Platform Based on ARM[C]. Fifth International Symposium on Embedded Computing. IEEE Computer society,2008,20:227-232.