面向Internet的动态路径规划算法研究与应用系统设计
|
摘要
路径规划问题网络优化问题中典型问题,它广泛应用于物流运输、交通导航、通信工程、计算机工程等领域。交通路网中的路径规划问题的本质是图论中的最短路问题,Dijkstra算法是公认的计算最短路的经典算法。但是随着交通的发展,道路网络复杂性不断提高,路网规模也不断扩大;Dijkstra算法的计算效率已无法满足实际的要求。于是,很多加速策略被提了出来,比如启发式策略、双向搜索策略、分层搜索策略等。在些改进策略中,基于路网分层压缩策略的Highway Hierarchical算法具有优势,该算法对路网进行预处理,按一定比例进行压缩,通过缩减搜索空间和搜索量来提高算法效率,得到了广泛的重视和研究。随着浮动车等动态交通信息采集技术的发展,动态交通信息可获得性得到了提高,基于动态交通信息的路径规划成为了近年来研究的热点。同时,随着物流运输系统、公众出行交通信息服务系统对路径规划需求的上升,在Internet环境下,如何构建高效合理的动态路径规划系统成为大家研究的重点。
论文依托《2008年广东省现代信息服务业发展专项资金扶持项目》和《广东省公众出行服务项目》,对路径规划算法进行研究以及在Internet环境下对路径规划应用系统进行设计,论文主要完成了以下三部分工作的研究:一、通过对基于路网分层压缩策略的Highway Hierarchical算法的分析,发现该算法在应用中存在路网压缩成环问题、预处理数据存储问题和完整最短路计算问题;采用无环压缩策略、分层存储策略和局部最短路存储策略,对算法进行了改进,并实现了改进的Highway Hierarchial算法;二、在Internet环境下,设计和实现了路径规划系统,通过分析系统实现中存在的网络数据传输和多用户并发请求的问题,运用WCF技术,构建分布式系统,实现高效合理的路径规划系统;三、随着动态交通信息可获得性的提高,论文基于动态交通数据构建时间依赖路网,提出基于Highway Hierarchical算法的动态路径规划算法,实现动态路径规划系统。
通过在广东省路网上进行的大规模测试,结果表明论文提出的改进Highway Hierarchical算法在大规模路网中仍具有高效性;同时保证了Internet环境下路径规划系统服务的高效性,最后,通过在物流运输和公众出行中的应用证明该系统具有良好的实际应用价值。
Route planning is a classical problem in network optimization, which is widely used in logistics transportation, traffic navigation, communication engineering, computer engineering and other fields. The essence of route planning in road networks is the shortest path problem in graph theory, and Dijkstra algorithm is recognized as the most classical algorithm to solve this problem.But with the development of transportation, the complexity of the road network increased and the scale of network expanded such as Dijkstra algorithm would be far too slow in large road networks. Thus, many speedup strategies are proposed, such as heuristic strategy, bidirectional searching strategy, hierarchical compression strategy and so on. During which, the highway hierarchical algorithm based on hierarchical compression strategy has the advantage and which is widely studied, for the algorithm preprocess road network according to a certain percentage of compression, and which improves the compute efficiency by reducing the search space and search volume. Meanwhile, with the development of dynamic traffic information collection technology such as floating cars technique, the availability of dynamic traffic information has been improved, the dynamic route planning has become a study hotspot in recent years. As the demand of planning path rising in logistics and transport systems and public transportation information service, how to build effective and rational dynamic path planning system in the Internet environment becomes a focus of the study. In this context, this thesis studies the route planning algorithm and system based on the―2008 Guangdong Province modern information service development‖project. The main works of this thesis are as follows:
Firstly, through the analysis of the Highway Hierarchical algorithm based on road network compression strategy, find that the algorithm has problems such as compression into the ring in road network, the storage of pretreatment data problem and the calculate of the shortest path problem. Improve and implement the algorithm with no-ring compression strategy, tiered storage strategy and local shortest path storage strategy. Secondly, design and implement the path planning system in the internet environment. After analyzing the data transmission problem and multi-user concurrency of the request problem of system, use WCF technology and build up a distributed system, to achieve a reasonable and efficient path planning system.
Thirdly, with the availability of dynamic traffic information being improved, this thesis builds dynamic road networks based on the available dynamic traffic data, and the dynamic route planning based on highway hierarchical algorithm is proposed. Dynamic route planning based on large-scale road networks is carried out.
A large scale experiment is taken in the road networks of Guangdong Province. The experiment results show that the improved highway hierarchical also is more efficient in the large-scale road network. It ensures the efficiency of path planning system in the internet. The application in the logistics transportation and public travel service also proved that the system has good practical value.
论文依托《2008年广东省现代信息服务业发展专项资金扶持项目》和《广东省公众出行服务项目》,对路径规划算法进行研究以及在Internet环境下对路径规划应用系统进行设计,论文主要完成了以下三部分工作的研究:一、通过对基于路网分层压缩策略的Highway Hierarchical算法的分析,发现该算法在应用中存在路网压缩成环问题、预处理数据存储问题和完整最短路计算问题;采用无环压缩策略、分层存储策略和局部最短路存储策略,对算法进行了改进,并实现了改进的Highway Hierarchial算法;二、在Internet环境下,设计和实现了路径规划系统,通过分析系统实现中存在的网络数据传输和多用户并发请求的问题,运用WCF技术,构建分布式系统,实现高效合理的路径规划系统;三、随着动态交通信息可获得性的提高,论文基于动态交通数据构建时间依赖路网,提出基于Highway Hierarchical算法的动态路径规划算法,实现动态路径规划系统。
通过在广东省路网上进行的大规模测试,结果表明论文提出的改进Highway Hierarchical算法在大规模路网中仍具有高效性;同时保证了Internet环境下路径规划系统服务的高效性,最后,通过在物流运输和公众出行中的应用证明该系统具有良好的实际应用价值。
Route planning is a classical problem in network optimization, which is widely used in logistics transportation, traffic navigation, communication engineering, computer engineering and other fields. The essence of route planning in road networks is the shortest path problem in graph theory, and Dijkstra algorithm is recognized as the most classical algorithm to solve this problem.But with the development of transportation, the complexity of the road network increased and the scale of network expanded such as Dijkstra algorithm would be far too slow in large road networks. Thus, many speedup strategies are proposed, such as heuristic strategy, bidirectional searching strategy, hierarchical compression strategy and so on. During which, the highway hierarchical algorithm based on hierarchical compression strategy has the advantage and which is widely studied, for the algorithm preprocess road network according to a certain percentage of compression, and which improves the compute efficiency by reducing the search space and search volume. Meanwhile, with the development of dynamic traffic information collection technology such as floating cars technique, the availability of dynamic traffic information has been improved, the dynamic route planning has become a study hotspot in recent years. As the demand of planning path rising in logistics and transport systems and public transportation information service, how to build effective and rational dynamic path planning system in the Internet environment becomes a focus of the study. In this context, this thesis studies the route planning algorithm and system based on the―2008 Guangdong Province modern information service development‖project. The main works of this thesis are as follows:
Firstly, through the analysis of the Highway Hierarchical algorithm based on road network compression strategy, find that the algorithm has problems such as compression into the ring in road network, the storage of pretreatment data problem and the calculate of the shortest path problem. Improve and implement the algorithm with no-ring compression strategy, tiered storage strategy and local shortest path storage strategy. Secondly, design and implement the path planning system in the internet environment. After analyzing the data transmission problem and multi-user concurrency of the request problem of system, use WCF technology and build up a distributed system, to achieve a reasonable and efficient path planning system.
Thirdly, with the availability of dynamic traffic information being improved, this thesis builds dynamic road networks based on the available dynamic traffic data, and the dynamic route planning based on highway hierarchical algorithm is proposed. Dynamic route planning based on large-scale road networks is carried out.
A large scale experiment is taken in the road networks of Guangdong Province. The experiment results show that the improved highway hierarchical also is more efficient in the large-scale road network. It ensures the efficiency of path planning system in the internet. The application in the logistics transportation and public travel service also proved that the system has good practical value.
引文
[1] Dijkstra E. W. A note on two problems in connexion with graphs [J]. Numerische Mathematik, 1959, 1(1): 269-271
[2]G.B.Dantzig. Linear Programming and Extensions[J]. Princeton University Press,1962.:361-365
[3]Delling D., Sanders P., Schultes P.,et al. Engineering route planning algorithms, Algorithmics of large and complex networks[A]. Algorithmics of Large and Complex Networks[C]. Heidelberg, Germany: Springer-Verlag,2009: 117-139
[4] P.E.Hart, N.J.Nilsson,and B.Raphael. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on System Science and Cybernetics, 1968, 4(2) :100-107.
[5] JENS MAUE, PETER SANDERS, DOMAGOJ MATIJEVIC. Goal Directed Shortest Path Queries Using Precomputed Cluster Distances[J]. ACM Journal,2009,V(N).1-27.
[6] LO-W,M-ZWICKER. Bidirectional Search for Interactive Motion Synthesis[J].Computer Graphics Forum, 2010,29(2).563-573.
[7] Buriol, L., Resende, M., Thorup, M. Speeding Up Dynamic Shortest-Path Algorithms[J]. Informs Journal on Computing,2008,2(20). 191-204.
[8] Christian Sommer. Approximate Shortest Path and Distance Queries in Networks[D]. Dissertation. Tokyo :The University of Tokyo,2010
[9] SANDERS-P, SCHULTES-D. Highway Hierarchies Hasten Exact Shortest Path Queries[A]. In:Gerth-S,Brodal.13th European Symposium on Algorithms [C]. Palma de Mallorca,Spain: Springer Verlag,2005.568–579.
[10] D.Schultes. Fast and exact shortest path queries using highway hierarchies[D]. Master’s thesis,Universitat des Saarlandes,2005.
[11]李引珍.交叉口有延误的交通网络最短路算法研究[J].兰州交通大学学报,2004,23(3):1-3
[12]杜牧青,程琳.考虑交叉口转向延误的最短路径拍卖算法[J].西南交通大学学报,2010,45(2):249-254.
[13]GAETANIF, MINCIDARDI R. Dynamic models and optimal control methods for route guidance in urban traffic networks [A].Proceedings of IEEE 5thinternational conference on intelligent transportation systems[C]. Singapore: IEEE, 2002: 454 -459.
[14]杨兆升.城市交通流诱导系统[M].北京:中国铁道出版社, 2004:179-185
[15]邹亮,徐建闽,朱玲湘. A*算法在基于电子地图的动态路径诱导中的应用[J].武汉理工大学学报(交通科学与工程版), 2006, 30(5):885-888[16]于加晴,查建中,陆一平等.基于SOA的分布式并行协同设计架构[J].北京交通大学学报, 2009, 33(5):69-72
[17]周劲,刘洋,蔺永政.一种基于Web Service的分布式应用系统的设计[J].计算机应用研究, 2007, (2):238-239
[18] Dantzig G. B. On the Shortest Route Through a Network[J]. Management Science, 1960, 6(2): 187-190
[19] Nicholson T. Finding the shortest route between two points in a network[J]. Computer Journal, 1966, 9(3): 275-280
[20] A.V.Goldberg and C.Harrelson. Computing the shortest path: A* meets graph theory[C]. In 16th ACM-SIAM Symposium on Discrete Algorithms,2005.156-165.
[21] F. Schulz, D. Wagner, and K. Weihe. Dijkstra’s algorithm on-line: An empirical case study from public railroad transport[A]. In 3rd Workshop on Algorithm Engineering (WAE) [C]. volume 1668 of LNCS, pages 110–123. Springer, 1999.
[22] E. K?hler, R. H. M?hring, and H. Schilling. Fast point-to-point shortest path computations with arc-flags[A]. In 9th DIMACS Implementation Challenge [C].2006.
[23] U. Lauther. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background[A]. In Geoinformation und Mobilit?t– von der Forschung zur praktischen Anwendung[C]. volume 22, pages 219–230. IfGI prints, Institut für Geoinformatik, Münster, 2004.
[24] A. V. Goldberg and C. Harrelson. Computing the shortest path: A* meets graph theory[A]. In 16th ACM-SIAM Symposium on Discrete Algorithms[C],pages 156–165, 2005.
[25] A. V. Goldberg, H. Kaplan, and R. F. Werneck. Better landmarks within reach[A]. In 9th DIMACS Implementation Challenge [C], 2006.
[26] H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. In transit to constant time shortest-path queries in road networks[A]. In Workshop on Algorithm Engineering and Experiments (ALENEX)[C]. pages 46–59,2007.
[27] H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast routing in road networks with transit nodes[J]. Science, 316(5824):566, 2007.
[28] D. Delling, P. Sanders, D. Schultes, and D. Wagner. Highway hierarchies star[A]. In 9th DIMACS Implementation Challenge [C], 2006.
[29] P. Sanders and D. Schultes. Engineering highway hierarchies[A]. In 14th European Symposium on Algorithms (ESA)[C]. volume 4168 of LNCS,pages 804–816. Springer, 2006.
[30] P. Sanders and D. Schultes. Robust, almost constant time shortest-path queries in road networks[A]. In 9th DIMACS Implementation Challenge[C], 2006.
[31] P. Sanders and D. Schultes. Engineering fast route planning algorithms[A].In 6th Workshop on Experimental Algorithms (WEA)[C]. volume 4525 of LNCS, pages 23–36. Springer, 2007.
[32] R. Bauer and D. Delling. SHARC: Fast and robust unidirectional routing[A]. In Workshop on Algorithm Engineering and Experiments (ALENEX)[C]. 2008. To appear.
[33] R. Bauer, D. Delling, and D. Wagner. Experimental Study on Speed-Up Techniques for Timetable Information Systems[A]. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization,and Systems (ATMOS’07)[C]. Schloss Dagstuhl, Germany, 2007.
[34] Chsbinii. A new short paths algorithm for discrete dynamic networks[A]. Proceedings of 8th IFAC symposium on Transport systems[C]. Salford: Elsevier ,1997: 551-556
[35] Chabinii. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time[J]. Transportation Research Records, 1998, 1645: 170-175
[36]Ziliaskopoulos A., Kotzinos D. A massively parallel time-dependent least-time-path algorithmfor intelligent transportation systems applications [J]. Computer-Aided Civil and Infrastructure Engineering, 2001, 16(5): 337-346
[37] Nannicini G., Baptiste P., Barbier G., et al. Fast paths in large-scale dynamic road networks[J]. Computer Optimization Applications , 2010, 45: 143-158
[38]LAM, T. and C.O. TONG. A Dynamic route guidance system based on historical and current traffic pattern[J]. in Proceedings of 1992 IEEE Intelligent Vehicles Symposium. 1992:365-369.
[39] Fuliping, Rilett L. R. Expected shortest paths in dynamic and stochastic traffic networks[J]. Transportation Research Part B, 1998, 32(7): 499-516
[40] Soumia I., Michel M., Jean-Yves P. Vehicle dispatching with time-dependent travel times[J]. Discrete Optimization, 2003, 1(144): 379-396
[41]Hall, R., The fastest path through a network with random time-dependent travel times[J]. Transportation Seience, 1986,20: 182-188.
[42] Cooke K. L. The shortest route through a network with time-dependent internodal transit times[J]. Journal of Mathematical Analysis and Application, 1966, 14(3): 493-498
[43]DEO, N. and Y. PANGC, Shortest path algorithms: taxonomy and annotation. Networks[J]. 1984,14: 175-323.
[44]FU, L.P. and L. RILETTR, Expected shortest paths in dynamic abd stochastic traffic networks[J]. Transportation research B, 1998. 32(7): p. 499-516.
[45]NLAM, T. and C.O. TONG, A Dynamic route guidance system based on historical and current traffic pattern[A], in Proceedings of 1992 IEEE Intelligent Vehicles Symposium[C]. 1992: 365-369.
[46]Orda, A. and R. Rom, Shortest-path and minimum delay algorithms in networks with time-dependent edge-length[J]. Journal of the ACM, 1990. 37(3): 607–625.
[47] E.米涅卡.网络和图的最优化算法[M].李宝莹译.北京:中国铁道出版社, 1984
[48]谢政,李建平.网络算法与复杂性理论[M].长沙:国防科技大学出版社, 1995
[49] J.邦詹森, G.古廷.有向图的理论、算法及其应用[M].姚兵,张忠辅译.北京:科学出版社, 2009
[50]杨兆升.智能型车载信息装置的自适应路径规划系统研究[D].吉林:吉林大学, 2006
[51]苏永云,晏克非,杨晓光,等. VNS中动态行程时间与多端动态最短路算法[J].中国公路学报, 2001, 14(1): 97-103
[52]维基百科.中华人民共和国公路等级[EB/OL]. http://zh.wikipedia.org/zh/, 2011
[53] Greenshields B. D. A study in highway capacity[J]. Highway Research Board Proceedings, 1935, 14: 448-477
[54] Fuliping, Rilett L. R. Expected shortest paths in dynamic and stochastic traffic networks[J]. Transportation Research Part B, 1998, 32(7): 499-516
[55] Han Jiawei, Kamber Micheline. Data Mining:Concepts and Techniques[J]. Morgan Kufnamm Publishers, 2000
[56]张可,刘小明,王笑京.车辆自动导航的路线优化系统研究[J].系统工程, 2001, 19(2): 48-53
[57]瞿嵘,刘潇,翁敏.出行路径选择标准及策略研究[J].测绘信息与工程, 2008, 33(2)
[58]蔺淑英.基于交通特性的动态路径诱导研究[D].广州:华南理工大学, 2009
[59]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社, 1997
[60] Van Eck J R, De Jong T. Adapting data structures and algorithms for faster transport network computations[A]. Proceedings of the 4th int. symposium on spatial data handling[C]. ,1990: 295-304
[61]张砚,苏旭明.车载导航电子地图的关键技术与解决方案[J].测绘科学技术学报, 2008, 25(4): 267-270
[62] Deo N., Pang C. Shortest-path algorithms: taxonomy and annotation[J]. Networks, 1984, 14: 275-323
[63] Cherkassky B. V. Shortest paths algorithms: theory and experimental evaluation[J]. Mathematical Programming, 1996(11): 129-174
[64]杨素琼,林碧勤,何伟.基于A*算法的地图路径搜索的实现[J].研究与开发, 2000(9): 33-36
[65] Tang Ping, Yang Yinmin. Study on algorithm A* of intelligent path planning based on method of represention environment with both quad tree and binary tree[J]. Control Theory and Application, 2003(20): 10-12
[66]傅家良.运筹学方法与模型[M].上海:复旦大学出版社, 2005
[67] Zhan F. B., Noon C. E. Shortest Path Algorithms: An Evaluation Using Real Road Networks [J]. Transportation Science, 1998, 32(1): 65-73
[68] Zhan F. B., Noon C. E. A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Path[J]. Journal of Geographic Information and Decision Analysis, 2000, 4: 1-13
[69] Cherkassky B. V., Goldberg A. V., Radzik T. Shortest Paths Algorithms:Theory and Experimental Evaluation.Computer Science Department[J]. Stanford University Technical Report, 1993
[70]颜波.车载自主导航系统中的动态最优路径规划[D].北京:清华大学, 2004
[71]高松,陆峰.一种基于路网等级启发式策略的路径搜索算法[J].地球信息科学学报, 2009, 11(2): 151-156
[72] Luby M., Ragde P. A bidirectional shortest-path algorithm with good average-case behavior[J]. Algorithmica, 1989, 194: 551-567
[73] Lo W., Zwicker M. Bidirectional Search for Interactive Motion Synthesis[J]. Computer Graphics Forum, 2010, 29(2)
[74] Nicholson T. Finding the shortest route between two points in a network[J]. computer journal, , 9(9): 275-280
[75] De Champeaux D. Bidirectional heuristic search again[J]. Journal of Association for Computing Machinery, 1983, 30(1): 22-32
[76] Bs Kwaj. an admissible bi-directional staged heuristic search algorithm[J]. Artificial Intelligence, 1989, 42(2): 189-212
[77] H Kaindl, G Kainz. Bidirectional heuristic search reconsidered[J]. Journal of Artificial Intelligence Research, 1997, 7(283-317)
[78]陆峰.最短路径算法:分类体系与研究进展[J].测绘学报, 2001, 30(3): 269-275
[79]李楷,钟耳顺,曾志明,等.基于分层网络拓扑结构的最优路径算法[J].中国图象图形学报, 2006, 11(7): 1004-1009
[80] Jing N., Huang Y. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation[J]. IEEE Transaction Knowledge and Data Engineering, 1998, 10(3): 409-432
[81] Jung Sungwon. An efficient path computation model for hierarchically structured topographical road maps[J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5): 1029-1046
[82]陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报, 2000, 25(3): 226-232
[83] Car A. Hierarchical spatial reasoning: theoretical consideration and its application to modeling way finding[D]. Austria: GeoinfoSer1esVienna, 1997
[84] Hector Gonzalez, Jiawei Han, Li Xiaolei. Adaptive Fastest Path Computation on a Road Network:A Traffic Mining Approach[A]. Proceedings of the 33rd international conference on Very large data bases[C]. Vienna Austria,2007: 794-805
[85]郑烟武.基于分层分区的动态路径规划算法研究[D].广州:华南理工大学,2011
[86]张东,钱德沛,刘爱龙等.车辆导航中基于约束条件的地图引擎和路径规划[J].计算机工程, 2007, 33(1):236-238
[87]王元彪.智能交通系统中Dijkstra算法的高效实现[J].计算机工程, 2007, 33(6):256-261
[88]陈宇飞,智明,秦国锋.基于GIS的最优路径自适应规划算法[J].计算机工程, 2007, 33(1):53-58
[89]严商.基于WCF的分布式程序的研究与实现[D].武汉:武汉理工大学,2008
[90]于加晴,查建中,陆一平等.基于SOA的分布式并行协同设计架构[J].北京交通大学学报, 2009, 33(5):69-72
[91]周劲,刘洋,蔺永政.一种基于Web Service的分布式应用系统的设计[J].计算机应用研究, 2007, (2):238-239
[92] Juval Lowy. Programming WCF Services. US,O’ReillyPress,2007:120-200;
[93]孙海鹏,翟传润,战兴群,等.基于实时交通信息的动态路径规划技术[J].微计算机信息, 2007, 23(8-3): 177-178
[94] Chryssi M. Time dependent vehicle routing problems:formulations, properties and computations experiments[D]. Evanston,Illinois: Northwestern University, 1989
[95] Soumia I., Michel M., Jean-Yves P. Vehicle dispatching with time-dependent travel times[J]. Discrete Optimization, 2003, 1(144): 379-396
[96] Albert V. D., Roberto M., Norman C., et al. Time dependent vehicle routing problem with a multi ant colony system [J]. European Journal of Operational Research, 2008, 185: 1174-1191
[97]晏克非,苏永云,黄翔等.车辆导航系统基于GIS的动态K最短路递推解法[J].西安公路交通大学学报, 2001, 21(1): 64-67
[98]朱弘戈.基于交通网络数据集的动态路径诱导系统规划与实现探讨[J].智能交通与应用, 2011,07:196-202
[2]G.B.Dantzig. Linear Programming and Extensions[J]. Princeton University Press,1962.:361-365
[3]Delling D., Sanders P., Schultes P.,et al. Engineering route planning algorithms, Algorithmics of large and complex networks[A]. Algorithmics of Large and Complex Networks[C]. Heidelberg, Germany: Springer-Verlag,2009: 117-139
[4] P.E.Hart, N.J.Nilsson,and B.Raphael. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transactions on System Science and Cybernetics, 1968, 4(2) :100-107.
[5] JENS MAUE, PETER SANDERS, DOMAGOJ MATIJEVIC. Goal Directed Shortest Path Queries Using Precomputed Cluster Distances[J]. ACM Journal,2009,V(N).1-27.
[6] LO-W,M-ZWICKER. Bidirectional Search for Interactive Motion Synthesis[J].Computer Graphics Forum, 2010,29(2).563-573.
[7] Buriol, L., Resende, M., Thorup, M. Speeding Up Dynamic Shortest-Path Algorithms[J]. Informs Journal on Computing,2008,2(20). 191-204.
[8] Christian Sommer. Approximate Shortest Path and Distance Queries in Networks[D]. Dissertation. Tokyo :The University of Tokyo,2010
[9] SANDERS-P, SCHULTES-D. Highway Hierarchies Hasten Exact Shortest Path Queries[A]. In:Gerth-S,Brodal.13th European Symposium on Algorithms [C]. Palma de Mallorca,Spain: Springer Verlag,2005.568–579.
[10] D.Schultes. Fast and exact shortest path queries using highway hierarchies[D]. Master’s thesis,Universitat des Saarlandes,2005.
[11]李引珍.交叉口有延误的交通网络最短路算法研究[J].兰州交通大学学报,2004,23(3):1-3
[12]杜牧青,程琳.考虑交叉口转向延误的最短路径拍卖算法[J].西南交通大学学报,2010,45(2):249-254.
[13]GAETANIF, MINCIDARDI R. Dynamic models and optimal control methods for route guidance in urban traffic networks [A].Proceedings of IEEE 5thinternational conference on intelligent transportation systems[C]. Singapore: IEEE, 2002: 454 -459.
[14]杨兆升.城市交通流诱导系统[M].北京:中国铁道出版社, 2004:179-185
[15]邹亮,徐建闽,朱玲湘. A*算法在基于电子地图的动态路径诱导中的应用[J].武汉理工大学学报(交通科学与工程版), 2006, 30(5):885-888[16]于加晴,查建中,陆一平等.基于SOA的分布式并行协同设计架构[J].北京交通大学学报, 2009, 33(5):69-72
[17]周劲,刘洋,蔺永政.一种基于Web Service的分布式应用系统的设计[J].计算机应用研究, 2007, (2):238-239
[18] Dantzig G. B. On the Shortest Route Through a Network[J]. Management Science, 1960, 6(2): 187-190
[19] Nicholson T. Finding the shortest route between two points in a network[J]. Computer Journal, 1966, 9(3): 275-280
[20] A.V.Goldberg and C.Harrelson. Computing the shortest path: A* meets graph theory[C]. In 16th ACM-SIAM Symposium on Discrete Algorithms,2005.156-165.
[21] F. Schulz, D. Wagner, and K. Weihe. Dijkstra’s algorithm on-line: An empirical case study from public railroad transport[A]. In 3rd Workshop on Algorithm Engineering (WAE) [C]. volume 1668 of LNCS, pages 110–123. Springer, 1999.
[22] E. K?hler, R. H. M?hring, and H. Schilling. Fast point-to-point shortest path computations with arc-flags[A]. In 9th DIMACS Implementation Challenge [C].2006.
[23] U. Lauther. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background[A]. In Geoinformation und Mobilit?t– von der Forschung zur praktischen Anwendung[C]. volume 22, pages 219–230. IfGI prints, Institut für Geoinformatik, Münster, 2004.
[24] A. V. Goldberg and C. Harrelson. Computing the shortest path: A* meets graph theory[A]. In 16th ACM-SIAM Symposium on Discrete Algorithms[C],pages 156–165, 2005.
[25] A. V. Goldberg, H. Kaplan, and R. F. Werneck. Better landmarks within reach[A]. In 9th DIMACS Implementation Challenge [C], 2006.
[26] H. Bast, S. Funke, D. Matijevic, P. Sanders, and D. Schultes. In transit to constant time shortest-path queries in road networks[A]. In Workshop on Algorithm Engineering and Experiments (ALENEX)[C]. pages 46–59,2007.
[27] H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast routing in road networks with transit nodes[J]. Science, 316(5824):566, 2007.
[28] D. Delling, P. Sanders, D. Schultes, and D. Wagner. Highway hierarchies star[A]. In 9th DIMACS Implementation Challenge [C], 2006.
[29] P. Sanders and D. Schultes. Engineering highway hierarchies[A]. In 14th European Symposium on Algorithms (ESA)[C]. volume 4168 of LNCS,pages 804–816. Springer, 2006.
[30] P. Sanders and D. Schultes. Robust, almost constant time shortest-path queries in road networks[A]. In 9th DIMACS Implementation Challenge[C], 2006.
[31] P. Sanders and D. Schultes. Engineering fast route planning algorithms[A].In 6th Workshop on Experimental Algorithms (WEA)[C]. volume 4525 of LNCS, pages 23–36. Springer, 2007.
[32] R. Bauer and D. Delling. SHARC: Fast and robust unidirectional routing[A]. In Workshop on Algorithm Engineering and Experiments (ALENEX)[C]. 2008. To appear.
[33] R. Bauer, D. Delling, and D. Wagner. Experimental Study on Speed-Up Techniques for Timetable Information Systems[A]. In 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization,and Systems (ATMOS’07)[C]. Schloss Dagstuhl, Germany, 2007.
[34] Chsbinii. A new short paths algorithm for discrete dynamic networks[A]. Proceedings of 8th IFAC symposium on Transport systems[C]. Salford: Elsevier ,1997: 551-556
[35] Chabinii. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time[J]. Transportation Research Records, 1998, 1645: 170-175
[36]Ziliaskopoulos A., Kotzinos D. A massively parallel time-dependent least-time-path algorithmfor intelligent transportation systems applications [J]. Computer-Aided Civil and Infrastructure Engineering, 2001, 16(5): 337-346
[37] Nannicini G., Baptiste P., Barbier G., et al. Fast paths in large-scale dynamic road networks[J]. Computer Optimization Applications , 2010, 45: 143-158
[38]LAM, T. and C.O. TONG. A Dynamic route guidance system based on historical and current traffic pattern[J]. in Proceedings of 1992 IEEE Intelligent Vehicles Symposium. 1992:365-369.
[39] Fuliping, Rilett L. R. Expected shortest paths in dynamic and stochastic traffic networks[J]. Transportation Research Part B, 1998, 32(7): 499-516
[40] Soumia I., Michel M., Jean-Yves P. Vehicle dispatching with time-dependent travel times[J]. Discrete Optimization, 2003, 1(144): 379-396
[41]Hall, R., The fastest path through a network with random time-dependent travel times[J]. Transportation Seience, 1986,20: 182-188.
[42] Cooke K. L. The shortest route through a network with time-dependent internodal transit times[J]. Journal of Mathematical Analysis and Application, 1966, 14(3): 493-498
[43]DEO, N. and Y. PANGC, Shortest path algorithms: taxonomy and annotation. Networks[J]. 1984,14: 175-323.
[44]FU, L.P. and L. RILETTR, Expected shortest paths in dynamic abd stochastic traffic networks[J]. Transportation research B, 1998. 32(7): p. 499-516.
[45]NLAM, T. and C.O. TONG, A Dynamic route guidance system based on historical and current traffic pattern[A], in Proceedings of 1992 IEEE Intelligent Vehicles Symposium[C]. 1992: 365-369.
[46]Orda, A. and R. Rom, Shortest-path and minimum delay algorithms in networks with time-dependent edge-length[J]. Journal of the ACM, 1990. 37(3): 607–625.
[47] E.米涅卡.网络和图的最优化算法[M].李宝莹译.北京:中国铁道出版社, 1984
[48]谢政,李建平.网络算法与复杂性理论[M].长沙:国防科技大学出版社, 1995
[49] J.邦詹森, G.古廷.有向图的理论、算法及其应用[M].姚兵,张忠辅译.北京:科学出版社, 2009
[50]杨兆升.智能型车载信息装置的自适应路径规划系统研究[D].吉林:吉林大学, 2006
[51]苏永云,晏克非,杨晓光,等. VNS中动态行程时间与多端动态最短路算法[J].中国公路学报, 2001, 14(1): 97-103
[52]维基百科.中华人民共和国公路等级[EB/OL]. http://zh.wikipedia.org/zh/, 2011
[53] Greenshields B. D. A study in highway capacity[J]. Highway Research Board Proceedings, 1935, 14: 448-477
[54] Fuliping, Rilett L. R. Expected shortest paths in dynamic and stochastic traffic networks[J]. Transportation Research Part B, 1998, 32(7): 499-516
[55] Han Jiawei, Kamber Micheline. Data Mining:Concepts and Techniques[J]. Morgan Kufnamm Publishers, 2000
[56]张可,刘小明,王笑京.车辆自动导航的路线优化系统研究[J].系统工程, 2001, 19(2): 48-53
[57]瞿嵘,刘潇,翁敏.出行路径选择标准及策略研究[J].测绘信息与工程, 2008, 33(2)
[58]蔺淑英.基于交通特性的动态路径诱导研究[D].广州:华南理工大学, 2009
[59]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社, 1997
[60] Van Eck J R, De Jong T. Adapting data structures and algorithms for faster transport network computations[A]. Proceedings of the 4th int. symposium on spatial data handling[C]. ,1990: 295-304
[61]张砚,苏旭明.车载导航电子地图的关键技术与解决方案[J].测绘科学技术学报, 2008, 25(4): 267-270
[62] Deo N., Pang C. Shortest-path algorithms: taxonomy and annotation[J]. Networks, 1984, 14: 275-323
[63] Cherkassky B. V. Shortest paths algorithms: theory and experimental evaluation[J]. Mathematical Programming, 1996(11): 129-174
[64]杨素琼,林碧勤,何伟.基于A*算法的地图路径搜索的实现[J].研究与开发, 2000(9): 33-36
[65] Tang Ping, Yang Yinmin. Study on algorithm A* of intelligent path planning based on method of represention environment with both quad tree and binary tree[J]. Control Theory and Application, 2003(20): 10-12
[66]傅家良.运筹学方法与模型[M].上海:复旦大学出版社, 2005
[67] Zhan F. B., Noon C. E. Shortest Path Algorithms: An Evaluation Using Real Road Networks [J]. Transportation Science, 1998, 32(1): 65-73
[68] Zhan F. B., Noon C. E. A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Path[J]. Journal of Geographic Information and Decision Analysis, 2000, 4: 1-13
[69] Cherkassky B. V., Goldberg A. V., Radzik T. Shortest Paths Algorithms:Theory and Experimental Evaluation.Computer Science Department[J]. Stanford University Technical Report, 1993
[70]颜波.车载自主导航系统中的动态最优路径规划[D].北京:清华大学, 2004
[71]高松,陆峰.一种基于路网等级启发式策略的路径搜索算法[J].地球信息科学学报, 2009, 11(2): 151-156
[72] Luby M., Ragde P. A bidirectional shortest-path algorithm with good average-case behavior[J]. Algorithmica, 1989, 194: 551-567
[73] Lo W., Zwicker M. Bidirectional Search for Interactive Motion Synthesis[J]. Computer Graphics Forum, 2010, 29(2)
[74] Nicholson T. Finding the shortest route between two points in a network[J]. computer journal, , 9(9): 275-280
[75] De Champeaux D. Bidirectional heuristic search again[J]. Journal of Association for Computing Machinery, 1983, 30(1): 22-32
[76] Bs Kwaj. an admissible bi-directional staged heuristic search algorithm[J]. Artificial Intelligence, 1989, 42(2): 189-212
[77] H Kaindl, G Kainz. Bidirectional heuristic search reconsidered[J]. Journal of Artificial Intelligence Research, 1997, 7(283-317)
[78]陆峰.最短路径算法:分类体系与研究进展[J].测绘学报, 2001, 30(3): 269-275
[79]李楷,钟耳顺,曾志明,等.基于分层网络拓扑结构的最优路径算法[J].中国图象图形学报, 2006, 11(7): 1004-1009
[80] Jing N., Huang Y. Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation[J]. IEEE Transaction Knowledge and Data Engineering, 1998, 10(3): 409-432
[81] Jung Sungwon. An efficient path computation model for hierarchically structured topographical road maps[J]. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(5): 1029-1046
[82]陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报, 2000, 25(3): 226-232
[83] Car A. Hierarchical spatial reasoning: theoretical consideration and its application to modeling way finding[D]. Austria: GeoinfoSer1esVienna, 1997
[84] Hector Gonzalez, Jiawei Han, Li Xiaolei. Adaptive Fastest Path Computation on a Road Network:A Traffic Mining Approach[A]. Proceedings of the 33rd international conference on Very large data bases[C]. Vienna Austria,2007: 794-805
[85]郑烟武.基于分层分区的动态路径规划算法研究[D].广州:华南理工大学,2011
[86]张东,钱德沛,刘爱龙等.车辆导航中基于约束条件的地图引擎和路径规划[J].计算机工程, 2007, 33(1):236-238
[87]王元彪.智能交通系统中Dijkstra算法的高效实现[J].计算机工程, 2007, 33(6):256-261
[88]陈宇飞,智明,秦国锋.基于GIS的最优路径自适应规划算法[J].计算机工程, 2007, 33(1):53-58
[89]严商.基于WCF的分布式程序的研究与实现[D].武汉:武汉理工大学,2008
[90]于加晴,查建中,陆一平等.基于SOA的分布式并行协同设计架构[J].北京交通大学学报, 2009, 33(5):69-72
[91]周劲,刘洋,蔺永政.一种基于Web Service的分布式应用系统的设计[J].计算机应用研究, 2007, (2):238-239
[92] Juval Lowy. Programming WCF Services. US,O’ReillyPress,2007:120-200;
[93]孙海鹏,翟传润,战兴群,等.基于实时交通信息的动态路径规划技术[J].微计算机信息, 2007, 23(8-3): 177-178
[94] Chryssi M. Time dependent vehicle routing problems:formulations, properties and computations experiments[D]. Evanston,Illinois: Northwestern University, 1989
[95] Soumia I., Michel M., Jean-Yves P. Vehicle dispatching with time-dependent travel times[J]. Discrete Optimization, 2003, 1(144): 379-396
[96] Albert V. D., Roberto M., Norman C., et al. Time dependent vehicle routing problem with a multi ant colony system [J]. European Journal of Operational Research, 2008, 185: 1174-1191
[97]晏克非,苏永云,黄翔等.车辆导航系统基于GIS的动态K最短路递推解法[J].西安公路交通大学学报, 2001, 21(1): 64-67
[98]朱弘戈.基于交通网络数据集的动态路径诱导系统规划与实现探讨[J].智能交通与应用, 2011,07:196-202