基于分层分区的动态路径规划算法研究
|
摘要
路径规划是网络优化中的经典问题,路径规划广泛应用于交通运输、通信工程、计算机工程、电网工程等领域。道路网络中的路径规划问题的本质是图论中的最短路问题,Dijkstra算法是公认的求解该问题最经典的算法。但是随着网络复杂性的提高和网络规模的扩大,Dijkstra算法的计算效率无法满足实际的要求。于是,很多加速策略被提了出来,比如启发式策略、压缩搜索空间策略、层次搜索策略等等。在这些方法中,基于道路等级的分层分区路径规划算法具有优势,该算法考虑了路网特性和路径选择偏好,且通过缩减搜索空间来提高算法效率,得到了广泛的重视和研究。同时,随着浮动车等动态交通信息采集技术的发展,动态交通信息可获得性得到了提高,基于动态交通信息的路径规划成为了近年来研究的热点。
论文以《2008年广东省现代信息服务业发展专项资金扶持项目》为依托,对路径规划算法进行研究,论文主要完成了以下三部分工作的研究:一、通过基于道路等级的分层分区路径规划算法的分析,发现该算法在应用中存在同层路网连通性无法保证、路径绕远和分区不合理等问题,为此,论文对该算法进行改进,引入虚拟边、新分区算法和其他优化方法,实现了改进分层分区路径规划算法;二、路径规划时使用者不仅关心路径长度同时关心行驶时间,而不同道路等级的路段在长度相同的情况下具有不一样的通行时间,因此,单纯考虑基于路段长度路阻函数的静态路径规划算法是不够的,需要对路阻函数进行扩展,论文考虑不同等级道路的路网特性,将动态路网特性静态化,考虑了基于道路等级的路段平均旅程时间的路阻函数,然后基于以上两类路阻函数,对比其他路径规划算法进行改进分层分区算法的计算效率和规划结果的分析;三、随着动态交通信息可获得性的提高,论文基于动态交通数据构建动态路网,提出基于分层分区的动态路径规划算法,实现基于大规模路网的动态路径规划。
通过在广东省路网上进行的大规模测试,结果表明论文提出的改进分层分区路径规划算法不仅计算效率高而且规划的路径更合理;同时通过对基于分层分区的动态路径规划算法的实现,发现本文提出的动态路径规划算法得到的规划结果会随着出发时刻或到达时刻的变化而变化,最后,通过在实际的物流运作中的应用证明该算法具有良好的实际应用价值。
Route planning is a classical problem in network optimization, which is widely used in transportation, communication engineering, computer engineering, electricity grid 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 for large road networks this would be far too slow. Thus, many speedup strategies are proposed, such as heuristic strategy, searching space compression strategy, hierarchical strategy and so on. During which, the hierarchical and partitioned algorithm based on road class has the advantage and which is widely studied, for the algorithm considers the character of road networks and the path selection preference, and which improves the compute efficiency by reducing the search space. 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.
In this context, this thesis studies the route planning algorithm based on the“2008 Guangdong Province modern information service development”project. The main works of this thesis are as follows:
Firstly, analyze the hierarchical and partitioned route planning algorithm, and found out that the algorithm has some problems such as the disconnection of the same road layer, unreasonable planning result and partitioning method and so on. Then virtual link, new partitioning algorithm and some other optimal methods are taken, and the adaptive hierarchical and partitional A-star algorithm is proposed.
Secondly, when use the route planning service the users concern both the length of the path and the travelling time, while different road sections take various passage time of the same road length, which means the static route planning algorithm consider the road length impedance function is not enough, we should extend the impedance function. Therefore, different road networks’character is considered, and average traveling time impedance function is used to evaluate the dynamic road networks. An experiment is taken to check the computation efficiency and planning rationality of the algorithm based on two impedance functions compare to different route planning algorithms.
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 hierarchical and partitioned A-star 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 adaptive hierarchical and partitioned A-star algorithm is more efficient and the planning result is more reasonable, and the planning result vary with different departure time or arrival time when use the dynamic route planning algorithm proposed by the thesis, the application in the logistics operation also proved that the algorithm has good practical value.
论文以《2008年广东省现代信息服务业发展专项资金扶持项目》为依托,对路径规划算法进行研究,论文主要完成了以下三部分工作的研究:一、通过基于道路等级的分层分区路径规划算法的分析,发现该算法在应用中存在同层路网连通性无法保证、路径绕远和分区不合理等问题,为此,论文对该算法进行改进,引入虚拟边、新分区算法和其他优化方法,实现了改进分层分区路径规划算法;二、路径规划时使用者不仅关心路径长度同时关心行驶时间,而不同道路等级的路段在长度相同的情况下具有不一样的通行时间,因此,单纯考虑基于路段长度路阻函数的静态路径规划算法是不够的,需要对路阻函数进行扩展,论文考虑不同等级道路的路网特性,将动态路网特性静态化,考虑了基于道路等级的路段平均旅程时间的路阻函数,然后基于以上两类路阻函数,对比其他路径规划算法进行改进分层分区算法的计算效率和规划结果的分析;三、随着动态交通信息可获得性的提高,论文基于动态交通数据构建动态路网,提出基于分层分区的动态路径规划算法,实现基于大规模路网的动态路径规划。
通过在广东省路网上进行的大规模测试,结果表明论文提出的改进分层分区路径规划算法不仅计算效率高而且规划的路径更合理;同时通过对基于分层分区的动态路径规划算法的实现,发现本文提出的动态路径规划算法得到的规划结果会随着出发时刻或到达时刻的变化而变化,最后,通过在实际的物流运作中的应用证明该算法具有良好的实际应用价值。
Route planning is a classical problem in network optimization, which is widely used in transportation, communication engineering, computer engineering, electricity grid 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 for large road networks this would be far too slow. Thus, many speedup strategies are proposed, such as heuristic strategy, searching space compression strategy, hierarchical strategy and so on. During which, the hierarchical and partitioned algorithm based on road class has the advantage and which is widely studied, for the algorithm considers the character of road networks and the path selection preference, and which improves the compute efficiency by reducing the search space. 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.
In this context, this thesis studies the route planning algorithm based on the“2008 Guangdong Province modern information service development”project. The main works of this thesis are as follows:
Firstly, analyze the hierarchical and partitioned route planning algorithm, and found out that the algorithm has some problems such as the disconnection of the same road layer, unreasonable planning result and partitioning method and so on. Then virtual link, new partitioning algorithm and some other optimal methods are taken, and the adaptive hierarchical and partitional A-star algorithm is proposed.
Secondly, when use the route planning service the users concern both the length of the path and the travelling time, while different road sections take various passage time of the same road length, which means the static route planning algorithm consider the road length impedance function is not enough, we should extend the impedance function. Therefore, different road networks’character is considered, and average traveling time impedance function is used to evaluate the dynamic road networks. An experiment is taken to check the computation efficiency and planning rationality of the algorithm based on two impedance functions compare to different route planning algorithms.
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 hierarchical and partitioned A-star 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 adaptive hierarchical and partitioned A-star algorithm is more efficient and the planning result is more reasonable, and the planning result vary with different departure time or arrival time when use the dynamic route planning algorithm proposed by the thesis, the application in the logistics operation also proved that the algorithm 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] 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
[3]高松,陆峰.一种基于路网等级启发式策略的路径搜索算法[J].地球信息科学学报, 2009, 11(2): 151-156
[4] 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
[5]陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报, 2000, 25(3): 226-232
[6]付梦印,李杰,邓志红.基于分层道路网络的新型路径规划算法[J].计算机辅助设计与图形学学报, 2005, 17(4): 719-722
[7] Floyd R. W. Algorithm97:Shortestpath[J]. Communications of the ACM, 1962, 5(6)
[8] Hart P. E., Nilsson N. J., B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[A]. IEEE TRANSACTIONS ON SYSTEMS SCIENCE AND CYBERNETICS[C]. ,1968: 100-107
[9] Goldberg A. V., Harrelson C. Computing the shortest path: A* meets graph theory[A]. 16th ACM-SIAM Symposium on Discrete Algorithms[C]. ,2005: 156-165
[10] Dantzig G. B. On the Shortest Route Through a Network[J]. Management Science, 1960, 6(2): 187-190
[11] Nicholson T. Finding the shortest route between two points in a network[J]. Computer Journal, 1966, 9(3): 275-280
[12] Hirtle S. C., Jonides J. Evidence of Hierarchies in Cognitive Maps[J]. Memory & Cognition, 1985, 13(3): 208-217
[13] Car A., Frank A. General Principles of Hierarchical Spatial Reasoning the Case of Way finding[A]. Proceedings of the Sixth Int. Symposium on Spatial Data Handling, SDH '94[C]. Edinburgh,Scotland,1994
[14]陆峰.最短路径算法:分类体系与研究进展[J].测绘学报, 2001, 30(3): 269-275
[15] Sanders P., Schultes D. Highway Hierarchies Hasten Exact Shortest Path Queries[A].Lecture Notes in Computer Science[C].2005: 568-579
[16] Lauther U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background[J]. Geoinformation und Mobilit?t - von der Forschung zur praktischen Anwendung, 2004, 22: 219-230
[17] Goldberg A. V. Computing the shortest path: A* search meets graph theory[A]. Proceedings of the 16th annual ACM-SIAM[C]. Vancouver, Canada,2005
[18] Bauer R., Delling D., Sanders P., et al. Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm[J]. Journal of Experimental Algorithmics (JEA), 2010, 15(23)
[19] 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
[20] Orda A., Rom R. Shortest-path and Minimumdelay Algorithms in Networks with Time-dependent Edge-length[J]. Journal of the Association for Computing Machinery, 1990, 37(3): 607-625
[21] Pallottino S., Scutella M. G. Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects[DB/OL]. http://ftp.di.unipi.it/pub/techreports/TR-97-06. ps.Z, 1997-06-25
[22] Chsbini I. A new short paths algorithm for discrete dynamic networks[A]. Proceedings of 8th IFAC symposium on Transport systems[C]. Salford: Elsevier ,1997: 551-556
[23] Chabini I. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time[J]. Transportation Research Records, 1998, 1645: 170-175
[24] 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
[25] Nannicini G., Baptiste P., Barbier G., et al. Fast paths in large-scale dynamic road networks[J]. Computer Optimization Applications , 2010, 45: 143-158
[26] Chabini I., Lan S. Adaptation of the A* algorithm for the computation fastest paths in deterministic discrete-time dynamic networks.[J]. IEEE Transactions on Inteligent Transportation Systems, 2002, 3(1): 60-74
[27] Lefebvre N., Balmer M. Fast shortest path computation in time-dependent traffic networks[A]. Proceedings of the 6th Swiss Transport Research Conference[C]. Ascona,2007
[28]谭国真.时变、随机网络最优路径算法及其应用研究[D].大连:大连理工大学, 2002
[29]谭国真,高文.时间依赖的网络中最小时间路径算法[J].计算机学报, 2002, 25(2): 165-172
[30]何俊.时间依赖的交通网络模型及最短路径算法[J].解放军理工大学, 2005, 6(6): 541-544
[31]田鹏飞,王建英.动态最短路径算法及其仿真[J].计算机仿真, 2007, 24(6): 153-155
[32]何瑞春,李引珍.时间依赖网络路径模型及双层优化智能算法研究[J].铁道学报, 2008, 30(1): 32-37
[33] E.米涅卡.网络和图的最优化算法[M].李宝莹译.北京:中国铁道出版社, 1984
[34]谢政,李建平.网络算法与复杂性理论[M].长沙:国防科技大学出版社, 1995
[35]李清泉,郑年波,徐敬海,等.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报, 2007, 12(7): 1280-1285
[36]杨兆升.智能型车载信息装置的自适应路径规划系统研究[D].吉林:吉林大学, 2006
[37]苏永云,晏克非,杨晓光,等. VNS中动态行程时间与多端动态最短路算法[J].中国公路学报, 2001, 14(1): 97-103
[38]维基百科.中华人民共和国公路等级[EB/OL]. http://zh.wikipedia.org/zh/, 2011
[39] Greenshields B. D. A study in highway capacity[J]. Highway Research Board Proceedings, 1935, 14: 448-477
[40] Homburger W. S., Kell J. H.交通工程基础[M].任福田等译.中国建筑工业出版社, 1990: 24-30
[41]颜波.车载自主导航系统中的动态最优路径规划[D].北京:清华大学, 2004
[42] Fuliping, Rilett L. R. Expected shortest paths in dynamic and stochastic traffic networks [J]. Transportation Research Part B, 1998, 32(7): 499-516
[43] Han Jiawei, Kamber Micheline. Data Mining:Concepts and Techniques[J]. Morgan Kufnamm Publishers, 2000
[44]张可,刘小明,王笑京.车辆自动导航的路线优化系统研究[J].系统工程, 2001, 19(2): 48-53
[45]瞿嵘,刘潇,翁敏.出行路径选择标准及策略研究[J].测绘信息与工程, 2008, 33(2)
[46]蔺淑英.基于交通特性的动态路径诱导研究[D].广州:华南理工大学, 2009
[47]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社, 1997
[48] 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
[49]张砚,苏旭明.车载导航电子地图的关键技术与解决方案[J].测绘科学技术学报, 2008, 25(4): 267-270
[50] Cherkassky B. V., Goldberg A. V., Radzik T. Shortest Paths Algorithms: Theory and Experimental Evaluation[J]. Mathematical Programming, 1996, 73: 129-174
[51] Deo N., Pang C. Shortest-path algorithms: taxonomy and annotation[J]. Networks, 1984, 14: 275-323
[52] Cherkassky B. V. Shortest paths algorithms: theory and experimental evaluation[J]. Mathematical Programming, 1996(11): 129-174
[53]杨素琼,林碧勤,何伟.基于A*算法的地图路径搜索的实现[J].研究与开发, 2000(9): 33-36
[54] 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
[55] Zhan F. B., Noon C. E. Shortest Path Algorithms: An Evaluation Using Real Road Networks [J]. Transportation Science, 1998, 32(1): 65-73
[56] 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
[57] Cherkassky B. V., Goldberg A. V., Radzik T. Shortest Paths Algorithms:Theory and Experimental Evaluation.Computer Science Department[J]. Stanford University Technical Report, 1993
[58]陆峰.基于特征的城市交通网络GIS数据组织与处理方法[D].北京:中国科学院遥感应用研究所, 1999
[59]江滨,黄波,陆峰. GIS环境下的空间分析和地学视觉化[M].北京:高等教育出版社, 2002
[60] Schultes D. Route planning in road networks[D]. Karlsruhe: Universit?t Karlsruhe (TH), 2008
[61]谢仕义,徐兵.基于ITS的加速最短路径搜索算法研究[J].计算机工程与应用, 2006(16): 212-215
[62] Bauer R., Delling D., Wagner D. Experimental Study of Speed Up Techniques forTimetable Information Systems [DB/OL]. http://onlinelibrary.wiley.com/doi/10.1002/ net. 20382/abstract, 2010
[63] Kuipers B., Levitt T. S. Navigation and Mapping in Large-scale Space [J]. AI MAGAZINE , 1988, 9(2)
[64] Demetrescu C., Emiliozzi S., Italiano G. F. Experimental analysis of dynamic all pairs shortest path algorithms[A]. Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms[C]. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics ,2004
[65]武雪玲,李清泉,任福.基于分层分块数据组织的双向A*算法[J].测绘信息与工程, 2006, 31(6): 1-2
[66] Car A. Hierarchical spatial reasoning: theoretical consideration and its application to modeling way finding[D]. Austria: GeoinfoSer1esVienna, 1997
[67] Chou Y., Romeijn E., Smith R L. Approximating shortest paths in large-scale network with an application to ITS[J]. Informs Journal of Computing, 1998, 10(2): 163-179
[68] Luby M., Ragde P. A bidirectional shortest-path algorithm with good average-case behavior[J]. Algorithmica, 1989, 194: 551-567
[69] Lo W., Zwicker M. Bidirectional Search for Interactive Motion Synthesis[J]. Computer Graphics Forum, 2010, 29(2)
[70] Nicholson T. Finding the shortest route between two points in a network[J]. computer journal, , 9(9): 275-280
[71] De Champeaux D. Bidirectional heuristic search again[J]. Journal of Association for Computing Machinery, 1983, 30(1): 22-32
[72] Bs Kwaj. an admissible bi-directional staged heuristic search algorithm[J]. Arti?cial Intelligence, 1989, 42(2): 189-212
[73] H Kaindl, G Kainz. Bidirectional heuristic search reconsidered[J]. Journal of Arti?cial Intelligence Research, 1997, 7(283-317)
[74] Wachs M. Relationships Between Drivers Attitudes Toward Alternate Routes and Driver and Route Characteristics[J]. Highway Research Record, 1967, 197: 70-87
[75] Stern E., Leiser D. Levels of Spatial Knowledge and Urban Travel Modeling[J]. Geographical Analysis, 1988, 20(2): 140-155
[76] Uchida T., Iida Y., Nakahara M. Panel survey on drivers' route choice behavior under travel time information[A]. Proceedings of Vehicle Navigation and Information Systems Conf.[C]. Yokohama-shi,Japan,1994
[77] Golledge R. G. Path Selection and Route Preference in Human Navigation:a Progress Report[A]. SPATIAL INFORMATION THEORY A THEORETICAL BASIS FOR GIS[C]. Heidelberg, Germany : Springer-Verlag,1995: 207-222
[78] Fisher P. F. Developments in Spatial Data Handling[M]. Berlin: Springer, 2005
[79]王媛.智能型车载信息装置的自适应路径规划系统研究[D].吉林:吉林大学, 2006
[80]李楷,钟耳顺,曾志明,等.基于分层网络拓扑结构的最优路径算法[J].中国图象图形学报, 2006, 11(7): 1004-1009
[81] 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
[82] 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
[83] 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
[84] Minsky M. Steps toward artificial intelligence[J]. Computers and Thought, 1963: 406-450
[85]苗洋,陈奇.嵌入式环境中分层路径规划算法的改进[J].计算机工程, 2010, 36(14): 243-245
[86]李晓斌.交通出行信息服务平台及其关键技术应用研究[D].广州:华南理工大学, 2010
[87] Tang Yuxin, Zhang Yunquan, Chen Hu. A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting[A]. Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications [C]. Dalian, China,2008: 155-161
[88]秦旭彦,陆化普,马洪.道路网络图的区块划分算法[J].清华大学学报(自然科学版), 2009, 49(3): 333-336
[89]秦小麟,叶延风,高航.数据结构教程——用C++实现的方法[M].北京:中国宇航出版社, 2003
[90]经济参考网,王莹,新京报. http://jjckb.xinhuanet.com/opinion/2011-01/26/content_ 284764. htm, 2011
[91]孙海鹏,翟传润,战兴群,等.基于实时交通信息的动态路径规划技术[J].微计算机信息, 2007, 23(8-3): 177-178
[92] Chryssi M. Time dependent vehicle routing problems:formulations, properties and computations experiments[D]. Evanston,Illinois: Northwestern University, 1989
[93] Soumia I., Michel M., Jean-Yves P. Vehicle dispatching with time-dependent travel times[J]. Discrete Optimization, 2003, 1(144): 379-396
[94] 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
[95]晏克非,苏永云,黄翔,等.车辆导航系统基于GIS的动态K最短路递推解法[J].西安公路交通大学学报, 2001, 21(1): 64-67
[2] 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
[3]高松,陆峰.一种基于路网等级启发式策略的路径搜索算法[J].地球信息科学学报, 2009, 11(2): 151-156
[4] 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
[5]陆锋,周成虎,万庆.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报, 2000, 25(3): 226-232
[6]付梦印,李杰,邓志红.基于分层道路网络的新型路径规划算法[J].计算机辅助设计与图形学学报, 2005, 17(4): 719-722
[7] Floyd R. W. Algorithm97:Shortestpath[J]. Communications of the ACM, 1962, 5(6)
[8] Hart P. E., Nilsson N. J., B. Raphael. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[A]. IEEE TRANSACTIONS ON SYSTEMS SCIENCE AND CYBERNETICS[C]. ,1968: 100-107
[9] Goldberg A. V., Harrelson C. Computing the shortest path: A* meets graph theory[A]. 16th ACM-SIAM Symposium on Discrete Algorithms[C]. ,2005: 156-165
[10] Dantzig G. B. On the Shortest Route Through a Network[J]. Management Science, 1960, 6(2): 187-190
[11] Nicholson T. Finding the shortest route between two points in a network[J]. Computer Journal, 1966, 9(3): 275-280
[12] Hirtle S. C., Jonides J. Evidence of Hierarchies in Cognitive Maps[J]. Memory & Cognition, 1985, 13(3): 208-217
[13] Car A., Frank A. General Principles of Hierarchical Spatial Reasoning the Case of Way finding[A]. Proceedings of the Sixth Int. Symposium on Spatial Data Handling, SDH '94[C]. Edinburgh,Scotland,1994
[14]陆峰.最短路径算法:分类体系与研究进展[J].测绘学报, 2001, 30(3): 269-275
[15] Sanders P., Schultes D. Highway Hierarchies Hasten Exact Shortest Path Queries[A].Lecture Notes in Computer Science[C].2005: 568-579
[16] Lauther U. An extremely fast, exact algorithm for finding shortest paths in static networks with geographical background[J]. Geoinformation und Mobilit?t - von der Forschung zur praktischen Anwendung, 2004, 22: 219-230
[17] Goldberg A. V. Computing the shortest path: A* search meets graph theory[A]. Proceedings of the 16th annual ACM-SIAM[C]. Vancouver, Canada,2005
[18] Bauer R., Delling D., Sanders P., et al. Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm[J]. Journal of Experimental Algorithmics (JEA), 2010, 15(23)
[19] 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
[20] Orda A., Rom R. Shortest-path and Minimumdelay Algorithms in Networks with Time-dependent Edge-length[J]. Journal of the Association for Computing Machinery, 1990, 37(3): 607-625
[21] Pallottino S., Scutella M. G. Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects[DB/OL]. http://ftp.di.unipi.it/pub/techreports/TR-97-06. ps.Z, 1997-06-25
[22] Chsbini I. A new short paths algorithm for discrete dynamic networks[A]. Proceedings of 8th IFAC symposium on Transport systems[C]. Salford: Elsevier ,1997: 551-556
[23] Chabini I. Discrete dynamic shortest path problems in transportation applications: Complexity and algorithms with optimal run time[J]. Transportation Research Records, 1998, 1645: 170-175
[24] 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
[25] Nannicini G., Baptiste P., Barbier G., et al. Fast paths in large-scale dynamic road networks[J]. Computer Optimization Applications , 2010, 45: 143-158
[26] Chabini I., Lan S. Adaptation of the A* algorithm for the computation fastest paths in deterministic discrete-time dynamic networks.[J]. IEEE Transactions on Inteligent Transportation Systems, 2002, 3(1): 60-74
[27] Lefebvre N., Balmer M. Fast shortest path computation in time-dependent traffic networks[A]. Proceedings of the 6th Swiss Transport Research Conference[C]. Ascona,2007
[28]谭国真.时变、随机网络最优路径算法及其应用研究[D].大连:大连理工大学, 2002
[29]谭国真,高文.时间依赖的网络中最小时间路径算法[J].计算机学报, 2002, 25(2): 165-172
[30]何俊.时间依赖的交通网络模型及最短路径算法[J].解放军理工大学, 2005, 6(6): 541-544
[31]田鹏飞,王建英.动态最短路径算法及其仿真[J].计算机仿真, 2007, 24(6): 153-155
[32]何瑞春,李引珍.时间依赖网络路径模型及双层优化智能算法研究[J].铁道学报, 2008, 30(1): 32-37
[33] E.米涅卡.网络和图的最优化算法[M].李宝莹译.北京:中国铁道出版社, 1984
[34]谢政,李建平.网络算法与复杂性理论[M].长沙:国防科技大学出版社, 1995
[35]李清泉,郑年波,徐敬海,等.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报, 2007, 12(7): 1280-1285
[36]杨兆升.智能型车载信息装置的自适应路径规划系统研究[D].吉林:吉林大学, 2006
[37]苏永云,晏克非,杨晓光,等. VNS中动态行程时间与多端动态最短路算法[J].中国公路学报, 2001, 14(1): 97-103
[38]维基百科.中华人民共和国公路等级[EB/OL]. http://zh.wikipedia.org/zh/, 2011
[39] Greenshields B. D. A study in highway capacity[J]. Highway Research Board Proceedings, 1935, 14: 448-477
[40] Homburger W. S., Kell J. H.交通工程基础[M].任福田等译.中国建筑工业出版社, 1990: 24-30
[41]颜波.车载自主导航系统中的动态最优路径规划[D].北京:清华大学, 2004
[42] Fuliping, Rilett L. R. Expected shortest paths in dynamic and stochastic traffic networks [J]. Transportation Research Part B, 1998, 32(7): 499-516
[43] Han Jiawei, Kamber Micheline. Data Mining:Concepts and Techniques[J]. Morgan Kufnamm Publishers, 2000
[44]张可,刘小明,王笑京.车辆自动导航的路线优化系统研究[J].系统工程, 2001, 19(2): 48-53
[45]瞿嵘,刘潇,翁敏.出行路径选择标准及策略研究[J].测绘信息与工程, 2008, 33(2)
[46]蔺淑英.基于交通特性的动态路径诱导研究[D].广州:华南理工大学, 2009
[47]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社, 1997
[48] 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
[49]张砚,苏旭明.车载导航电子地图的关键技术与解决方案[J].测绘科学技术学报, 2008, 25(4): 267-270
[50] Cherkassky B. V., Goldberg A. V., Radzik T. Shortest Paths Algorithms: Theory and Experimental Evaluation[J]. Mathematical Programming, 1996, 73: 129-174
[51] Deo N., Pang C. Shortest-path algorithms: taxonomy and annotation[J]. Networks, 1984, 14: 275-323
[52] Cherkassky B. V. Shortest paths algorithms: theory and experimental evaluation[J]. Mathematical Programming, 1996(11): 129-174
[53]杨素琼,林碧勤,何伟.基于A*算法的地图路径搜索的实现[J].研究与开发, 2000(9): 33-36
[54] 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
[55] Zhan F. B., Noon C. E. Shortest Path Algorithms: An Evaluation Using Real Road Networks [J]. Transportation Science, 1998, 32(1): 65-73
[56] 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
[57] Cherkassky B. V., Goldberg A. V., Radzik T. Shortest Paths Algorithms:Theory and Experimental Evaluation.Computer Science Department[J]. Stanford University Technical Report, 1993
[58]陆峰.基于特征的城市交通网络GIS数据组织与处理方法[D].北京:中国科学院遥感应用研究所, 1999
[59]江滨,黄波,陆峰. GIS环境下的空间分析和地学视觉化[M].北京:高等教育出版社, 2002
[60] Schultes D. Route planning in road networks[D]. Karlsruhe: Universit?t Karlsruhe (TH), 2008
[61]谢仕义,徐兵.基于ITS的加速最短路径搜索算法研究[J].计算机工程与应用, 2006(16): 212-215
[62] Bauer R., Delling D., Wagner D. Experimental Study of Speed Up Techniques forTimetable Information Systems [DB/OL]. http://onlinelibrary.wiley.com/doi/10.1002/ net. 20382/abstract, 2010
[63] Kuipers B., Levitt T. S. Navigation and Mapping in Large-scale Space [J]. AI MAGAZINE , 1988, 9(2)
[64] Demetrescu C., Emiliozzi S., Italiano G. F. Experimental analysis of dynamic all pairs shortest path algorithms[A]. Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms[C]. Philadelphia, PA, USA: Society for Industrial and Applied Mathematics ,2004
[65]武雪玲,李清泉,任福.基于分层分块数据组织的双向A*算法[J].测绘信息与工程, 2006, 31(6): 1-2
[66] Car A. Hierarchical spatial reasoning: theoretical consideration and its application to modeling way finding[D]. Austria: GeoinfoSer1esVienna, 1997
[67] Chou Y., Romeijn E., Smith R L. Approximating shortest paths in large-scale network with an application to ITS[J]. Informs Journal of Computing, 1998, 10(2): 163-179
[68] Luby M., Ragde P. A bidirectional shortest-path algorithm with good average-case behavior[J]. Algorithmica, 1989, 194: 551-567
[69] Lo W., Zwicker M. Bidirectional Search for Interactive Motion Synthesis[J]. Computer Graphics Forum, 2010, 29(2)
[70] Nicholson T. Finding the shortest route between two points in a network[J]. computer journal, , 9(9): 275-280
[71] De Champeaux D. Bidirectional heuristic search again[J]. Journal of Association for Computing Machinery, 1983, 30(1): 22-32
[72] Bs Kwaj. an admissible bi-directional staged heuristic search algorithm[J]. Arti?cial Intelligence, 1989, 42(2): 189-212
[73] H Kaindl, G Kainz. Bidirectional heuristic search reconsidered[J]. Journal of Arti?cial Intelligence Research, 1997, 7(283-317)
[74] Wachs M. Relationships Between Drivers Attitudes Toward Alternate Routes and Driver and Route Characteristics[J]. Highway Research Record, 1967, 197: 70-87
[75] Stern E., Leiser D. Levels of Spatial Knowledge and Urban Travel Modeling[J]. Geographical Analysis, 1988, 20(2): 140-155
[76] Uchida T., Iida Y., Nakahara M. Panel survey on drivers' route choice behavior under travel time information[A]. Proceedings of Vehicle Navigation and Information Systems Conf.[C]. Yokohama-shi,Japan,1994
[77] Golledge R. G. Path Selection and Route Preference in Human Navigation:a Progress Report[A]. SPATIAL INFORMATION THEORY A THEORETICAL BASIS FOR GIS[C]. Heidelberg, Germany : Springer-Verlag,1995: 207-222
[78] Fisher P. F. Developments in Spatial Data Handling[M]. Berlin: Springer, 2005
[79]王媛.智能型车载信息装置的自适应路径规划系统研究[D].吉林:吉林大学, 2006
[80]李楷,钟耳顺,曾志明,等.基于分层网络拓扑结构的最优路径算法[J].中国图象图形学报, 2006, 11(7): 1004-1009
[81] 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
[82] 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
[83] 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
[84] Minsky M. Steps toward artificial intelligence[J]. Computers and Thought, 1963: 406-450
[85]苗洋,陈奇.嵌入式环境中分层路径规划算法的改进[J].计算机工程, 2010, 36(14): 243-245
[86]李晓斌.交通出行信息服务平台及其关键技术应用研究[D].广州:华南理工大学, 2010
[87] Tang Yuxin, Zhang Yunquan, Chen Hu. A Parallel Shortest Path Algorithm Based on Graph-Partitioning and Iterative Correcting[A]. Proceedings of the 10th IEEE International Conference on High Performance Computing and Communications [C]. Dalian, China,2008: 155-161
[88]秦旭彦,陆化普,马洪.道路网络图的区块划分算法[J].清华大学学报(自然科学版), 2009, 49(3): 333-336
[89]秦小麟,叶延风,高航.数据结构教程——用C++实现的方法[M].北京:中国宇航出版社, 2003
[90]经济参考网,王莹,新京报. http://jjckb.xinhuanet.com/opinion/2011-01/26/content_ 284764. htm, 2011
[91]孙海鹏,翟传润,战兴群,等.基于实时交通信息的动态路径规划技术[J].微计算机信息, 2007, 23(8-3): 177-178
[92] Chryssi M. Time dependent vehicle routing problems:formulations, properties and computations experiments[D]. Evanston,Illinois: Northwestern University, 1989
[93] Soumia I., Michel M., Jean-Yves P. Vehicle dispatching with time-dependent travel times[J]. Discrete Optimization, 2003, 1(144): 379-396
[94] 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
[95]晏克非,苏永云,黄翔,等.车辆导航系统基于GIS的动态K最短路递推解法[J].西安公路交通大学学报, 2001, 21(1): 64-67