面向导航路径选择的道路网络经验层级模型研究
|
摘要
道路网络中的路径规划已经成为在各种移动设备以及地图网站上运行的导航服务的一个基本应用。传统的路径规划算法主要是在从道路网络中抽象出的图中计算源与目标节点之间的最短路径。然而,由这种传统的算法得到的最短路径往往与一个对道路网络非常熟悉的有经验的大脑算计出来的结果不一样。这些有经验的人脑计算出来的路径往往比机器得到的结果要更加合理。因而,我们从一种经验知识的角度出发提出了一种面向导航路径规划的道路网络层级模型。本文就该模型作了广泛深入地研究工作,其主要内容包括下面四个部分。
1.我们总结了导航中主要的最短路径算法、基于预处理的最短路径算法以及动态最短路径算法。通过文献的总结工作,我们注意到预处理方法的重要性。从学术研究和产业应用上来看,基于预处理的路径算法已经成为大规模路网路径计算的一种标准处理方法。不过,从我们查阅的文献来看,人脑的经验知识被所有这些计算路径的方法忽略了。
2.我们分析了路网的一种拓扑指标(即中介中心性)和其层级性能。这种关于路段的拓扑指标的计算是建立在最短路径的基础上的。因此,我们用它来评估道路在路网中的一种拓扑重要性。我们采用了六个城市道路网络来做这种中介中心性分析。从我们实验结果来看,这些城市道路网络弧段的BC值的分布呈现一致的规律分布,具有层级性。从总体上来看城市道路网络中大部分等级高的道路具有较高的BC值,大部分等级低的道路具有较低的BC值。
3.我们提出了一种面向路径规划的构建经验层级路网的方法。这种层级路网主要是依据从大量GPS轨迹中挖掘出的出租车经验知识来构建的。构建方法主要分为下面三步。①从原始轨迹中恢复出出租车的经验路径。②根据路段的中介中心性以及经验路径通过该路段的频次和速度,我们分类出经验道路。③从这些分过类的道路中构建出强连通的层级道路网络,这样才能保证路径规划方法的正确应用。我们以武汉市为例,采用该方法构建层级路网,试验结果表明,根据这种经验层级路网可以在不同时间段动态地获得经验上的最优路径。并且,这些路径的通行时间更短,其较传统方法的结果更加合理。
4.我们给出了一个面向路径规划的用Vorono图关联的层级路网模型。在已有的层级模型基础上,其利用Voronoi图来关联层级路网中的相邻层。通过这种方法来确定出上下层之间的出入口的思路与人的大脑在做高速路的路径规划时寻找最近相邻的一个出入口的思考方式是一致的。采用Voronoi图的方法,可以使层级路径搜索更加简单和高效。其搜索的范围更小,时间开销更少。
Finding optimal paths in road networks was a fundamental application in various navigation services which ran on mobile equipments or map websites. Conventional path planning algorithms computed shortest paths between source nodes and target nodes in a graph abstracted from real-world road networks. However, optimal paths produced by conventional methods were usually different from paths adopted by experienced brains who were familiar with local road networks. The paths by human beings were always more reasonable than those computed by machines. Therefore, we proposed a novel hierarchy model of road network for route planning from the perspective of empirical knowledge. The model was extensively studied by the paper and its main contents consists of four parts.
1. We reviewed shortest path algorithms, its variants for preprocessing methods and its dynamic variants. We noted the importance of its preprocessing methods for road network. For both academic research and industrial applications, the preprocess-ing methods was widely adopted as a part of standard optimal path computation procedure. Nevertheless, these methods ignore the empirical knowledge owned by brains in the literatures.
2. We studied on a topological index and hierarchy traits of road network. The com-putation of the topological index,Betweenness Centrality, was based on the shortest path algorithm. Therefore, it was used to evaluate the topological importance of seg-ments in road networks. Six typical urban road networks were selected for Between-ness Centrality analysis. The experimental results showed that the distribution of Betweenness Centrality presented consistency and had a hierarchical property. The statistical results of Betweenness Centrality illustrated that the majority of road segments in high administrative levels characterized high value while the majority of road segments in low administrative levels had low value in urban road networks.
3. We proposed an experienced methodology that constructed hierarchical road net-works for route planning. It depended on taxi drivers' experience mining from massive GPS trajectories. The method mainly consisted of three steps. First, expe-rience routes of taxi drivers were recovered from original trajectories. Second, the experience roads were recognized and classified using travel frequency, speed infor- mation of experience routes and Betweenness Centrality of road segments. Third, strongly connected network of hierarchy were constructed from the classified roads so that hierarchical route planning can be implemented. A case study of a metropoli-tan area, Wuhan city, showed that experiential optimal paths can be dynamically obtained during different time intervals, particularly in rush hours. Experiments demonstrated that travel time of the experiential paths was less than that of the paths planned by conventional methods.
4. We proposed a Voronoi-based hierarchical graph model of road network for route planning. It constructed the hierarchical graph and utilized graph Voronoi diagram to associate adjacent levels in hierarchical graph of road network. The method, by which this hierarchical model determined the nearest neighbor of entry or exit node of upper level road network, coincided with the way of thinking in which human would find entrance, which was nearest to him, to highway when he drove to somewhere faraway. Because of using graph Voronoi diagram, the hierarchical graph model can make the hierarchical searching process simpler and more efficient. The searching range was shrinked and the running time was decreased in the hierarchical route planning.
1.我们总结了导航中主要的最短路径算法、基于预处理的最短路径算法以及动态最短路径算法。通过文献的总结工作,我们注意到预处理方法的重要性。从学术研究和产业应用上来看,基于预处理的路径算法已经成为大规模路网路径计算的一种标准处理方法。不过,从我们查阅的文献来看,人脑的经验知识被所有这些计算路径的方法忽略了。
2.我们分析了路网的一种拓扑指标(即中介中心性)和其层级性能。这种关于路段的拓扑指标的计算是建立在最短路径的基础上的。因此,我们用它来评估道路在路网中的一种拓扑重要性。我们采用了六个城市道路网络来做这种中介中心性分析。从我们实验结果来看,这些城市道路网络弧段的BC值的分布呈现一致的规律分布,具有层级性。从总体上来看城市道路网络中大部分等级高的道路具有较高的BC值,大部分等级低的道路具有较低的BC值。
3.我们提出了一种面向路径规划的构建经验层级路网的方法。这种层级路网主要是依据从大量GPS轨迹中挖掘出的出租车经验知识来构建的。构建方法主要分为下面三步。①从原始轨迹中恢复出出租车的经验路径。②根据路段的中介中心性以及经验路径通过该路段的频次和速度,我们分类出经验道路。③从这些分过类的道路中构建出强连通的层级道路网络,这样才能保证路径规划方法的正确应用。我们以武汉市为例,采用该方法构建层级路网,试验结果表明,根据这种经验层级路网可以在不同时间段动态地获得经验上的最优路径。并且,这些路径的通行时间更短,其较传统方法的结果更加合理。
4.我们给出了一个面向路径规划的用Vorono图关联的层级路网模型。在已有的层级模型基础上,其利用Voronoi图来关联层级路网中的相邻层。通过这种方法来确定出上下层之间的出入口的思路与人的大脑在做高速路的路径规划时寻找最近相邻的一个出入口的思考方式是一致的。采用Voronoi图的方法,可以使层级路径搜索更加简单和高效。其搜索的范围更小,时间开销更少。
Finding optimal paths in road networks was a fundamental application in various navigation services which ran on mobile equipments or map websites. Conventional path planning algorithms computed shortest paths between source nodes and target nodes in a graph abstracted from real-world road networks. However, optimal paths produced by conventional methods were usually different from paths adopted by experienced brains who were familiar with local road networks. The paths by human beings were always more reasonable than those computed by machines. Therefore, we proposed a novel hierarchy model of road network for route planning from the perspective of empirical knowledge. The model was extensively studied by the paper and its main contents consists of four parts.
1. We reviewed shortest path algorithms, its variants for preprocessing methods and its dynamic variants. We noted the importance of its preprocessing methods for road network. For both academic research and industrial applications, the preprocess-ing methods was widely adopted as a part of standard optimal path computation procedure. Nevertheless, these methods ignore the empirical knowledge owned by brains in the literatures.
2. We studied on a topological index and hierarchy traits of road network. The com-putation of the topological index,Betweenness Centrality, was based on the shortest path algorithm. Therefore, it was used to evaluate the topological importance of seg-ments in road networks. Six typical urban road networks were selected for Between-ness Centrality analysis. The experimental results showed that the distribution of Betweenness Centrality presented consistency and had a hierarchical property. The statistical results of Betweenness Centrality illustrated that the majority of road segments in high administrative levels characterized high value while the majority of road segments in low administrative levels had low value in urban road networks.
3. We proposed an experienced methodology that constructed hierarchical road net-works for route planning. It depended on taxi drivers' experience mining from massive GPS trajectories. The method mainly consisted of three steps. First, expe-rience routes of taxi drivers were recovered from original trajectories. Second, the experience roads were recognized and classified using travel frequency, speed infor- mation of experience routes and Betweenness Centrality of road segments. Third, strongly connected network of hierarchy were constructed from the classified roads so that hierarchical route planning can be implemented. A case study of a metropoli-tan area, Wuhan city, showed that experiential optimal paths can be dynamically obtained during different time intervals, particularly in rush hours. Experiments demonstrated that travel time of the experiential paths was less than that of the paths planned by conventional methods.
4. We proposed a Voronoi-based hierarchical graph model of road network for route planning. It constructed the hierarchical graph and utilized graph Voronoi diagram to associate adjacent levels in hierarchical graph of road network. The method, by which this hierarchical model determined the nearest neighbor of entry or exit node of upper level road network, coincided with the way of thinking in which human would find entrance, which was nearest to him, to highway when he drove to somewhere faraway. Because of using graph Voronoi diagram, the hierarchical graph model can make the hierarchical searching process simpler and more efficient. The searching range was shrinked and the running time was decreased in the hierarchical route planning.
引文
1 MEHLHORN K. Data structures and algorithms[M]. New York, NY, USA: Springer-Verlag New York, Inc.,1984.
2 BERTSIMAS D, TSITSIKLIS J N. Introduction to linear optimization[M].[S.l.]: Athena Scientific, Belmont, Massachusetts,1997.
3 SHIMBEL A. Structure in Communication Nets[C] In Proceedings of the Sym-posium on Information Networks. Brooklyn:Polytechnic Press of the Polytechnic Institute of Brooklyn,1955:199-203.
4 DANTZIG G B. Discrete-Variable Extremum Problems[J]. Operations Research, 1957,5(2):266-277.
5 MOORE E. The shortest path through a maze[C] Proceedings of the International Symposium on the Theory of Switching. Cambridge, Massachusetts:Harvard Uni-versity Press,1959,2:285-292.
6 BELLMAN R. On a routing problem[J]. Quart. Appl. Math.,1958,16:87-90.
7 DIJKSTRA E. A note on two problems in connexion with graphs[J]. Numerische Mathematik,1959:269-271.
8 PAPE U. Implementation and efficiency of Moore-algorithms for the shortest route problem[J]. Mathematical Programming,1974,7(1):212-222.
9 PALLOTINO S. Shortest path methods:Complexity, interrelations and new propo-sitions[J]. Networks,1984,14(2):257-267.
10 GLOVER F, KLINGMAN D, PHILLIPS N. A New Polynomially Bounded Shortest Path Algorithm[J]. Operations Research,1985,33(1):65-73. http://www. jstor. org/stable/170867.
11 GOLDBERG T, A.V.AND RADZIK. A heuristic improvement of the Bellman-Ford algorithm[J]. Applied Mathematics Letters,1993,6(3):3-6.
12 WILLIAMS J. Algorithm 232:heapsort[J]. Communications of the ACM,1964, 7(6):347-348.
13 DIAL R B. Algorithm 360:shortest-path forest with topological ordering[J]. Com-mun. ACM,1969,12(11):632-633.
14 JOHNSON D B. Efficient Algorithms for Shortest Paths in Sparse Networks[J]. J. ACM,1977,24(1):1-13.
15 FREDMAN M, TARJAN R. Fibonacci heaps and their uses in improved network optimization algorithms [J]. Journal of the ACM (JACM),1987,34(3):596-615.
16 AHUJA R K, MEHLHORN K, ORLIN J, et al. Faster algorithms for the shortest path problem[J]. J. ACM,1990,37(2):213-223.
17 CHERKASSKY B V, GOLDBERG A V, SILVERSTEIN C. Buckets, heaps, lists, and monotone priority queues[C] SODA'97:Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA:Society for In-dustrial and Applied Mathematics,1997:83-92.
18 RAMAN R. Recent results on the single-source shortest paths problem[J]. ACM SIGACT News,1997,28(2):81-87.
19 THORUP M. Integer priority queues with decrease key in constant time and the single source shortest paths problem [J]. Journal of Computer and System Sciences, 2004,69(3):330-353. Special Issue on STOC 2003.
20 CHERKASSKY B, GOLDBERG A, RADZIK T. Shortest paths algorithms:theory and experimental evaluation [J]. Mathematical programming,1996,73(2):129-174.
21 ZHAN F, NOON C. Shortest path algorithms:An evaluation using real road networks.[J]. Transportation Science,1998,32(2):65-73.
22 HART P E, NILSSON N J, RAPHAEL B. A Formal Basis for the Heuristic De-termination of Minimum Cost Paths [J]. IEEE Transactions of systems science and cybernetics,1968, ssc-4(2):100-107.
23 FU L, SUN D, RILETT L. Heuristic shortest path algorithms for transporta-tion applications:state of the art[J]. Computers & Operations Research,2006, 33(11):3324-3343.
24 LARK III J, WHITE III C, SYVERSON K. A best-first search algorithm guided by a set-valued heuristic[J]. IEEE Transactions on Systems, Man and Cybernetics, 1995,25(7):1097-1101.
25 REINEFELD A, MARSLAND T. Enhanced iterative-deepening search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1994,16(7):701-710.
26 ZENG W, CHURCH R L. Finding shortest paths on real road networks:the case for A*[J]. International Journal of Geographical Information Science,2009, 23(4):531-543.
27 LIU B. Route finding by using knowledge about the road network[J]. IEEE Transactions on systems,man,and cybernetics-part A:systems and humans,1997, 27(4):436-448.
28 DANTZIG G. On the shortest route through a network[J]. Management Science, 1960,6(1):87-90.
29 NICHOLSON T A J. Finding the Shortest Route between Two Points in a Network[J]. The Computer Journal,1966,9(3):275-280. http://comjnl. oxfordjournals.org/cgi/content/abstract/9/3/275.
30 POHL I. Bi-directional search[J]. Machine Intelligence,1971:127-140.
31 SINT L, DE CHAMPEAUX D. An Improved Bidirectional Heuristic Search Algo-rithm[J]. J. ACM,1977,24(2):177-191.
32 DE CHAMPEAUX D. Bidirectional Heuristic Search Again[J]. J. ACM,1983, 30(1):22-32.
33 KWA J B. BS*:an admissible bidirectional staged heuristic search algorithm[J]. Artif. Intell.,1989,38(1):95-109.
34 KAINDL H, KAINZ G. Bidirectional heuristic search reconsidered [J]. Journal of Artificial Intelligence Research,1997.
35 DREYFUS S. An appraisal of some shortest-path algorithms [J]. Operations Re-search,1969:395-412.
36 BAST H, FUNKE S, MATIJEVIC D, et al. In Transit to Constant Time Shortest-Path Queries in Road Networks[C]. APPLEGATE D, BRODAL G.9th Workshop on Algorithm Enginneering and Experiments (ALENEX'07). New Orleans, USA: SIAM,2007:toappear.
37 SANDERS P, SCHULTES D. Highway Hierarchies Hasten Exact Shortest Path Queries[C] Proceedings 17th European Symposium on Algorithms (ESA).2005. Berlin:Springer, Springer LNCS, vol.3669.
38 ISHIKAWA K, OGAWA M, AZUMA S, et al. Map navigation software of the electro-multivision of the'91 Toyoto Soarer[J]. Vehicle Navigation and Information Systems Conference,1991,1991,2:463-473.
39 JING N, HUANG Y W, RUNDENSTEINER E A. Hierarchical Encoded Path Views for Path Query Processing:An Optimal Model and Its Performance Evaluation [J]. IEEE Trans. Knowledge and Data Engineering,1998,10(3). http://citeseer. ist.psu.edu/j ing98hierarchical.html.
40 JUNG S, PRAMANIK S. An Efficient Path Computation Model for Hierarchi-cally Structured Topographical Road Maps[J]. IEEE Trans. Knowledge and Data Engineering,2002,14(5).
41 WAGNER D, WILLHALM T. Geometric Speed-Up Techniques for Finding Short-est Paths in Large Sparse Graphs[C] Proc.11th European Symposium on Algo-rithms (ESA).2003. Berlin:Springer, LNCS, vol.2832.
42 GUTMAN R. Reach-Based Routing:A New Approach to Shortest Path Algo-rithms Optimized for Road Networks [C] Proceedings 6th Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia,USA:SIAM,2004:100-111.
43 FLINSENBERG I C. Route Planning Algorithms for Car Navigation[D]. Eind-hoven:Technische Universiteit Eindhoven,2004.
44 KOHLER E, MOHRING R, SCHILLING H. Acceleration of shortest path and constrained shortest path computation [J]. Experimental and Efficient Algorithms, 2005:126-138.
45 GOLDBERG A V, HARRELSON C. Computing the shortest path:A search meets graph theory[C] SODA'05:Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA:Society for Industrial and Applied Mathematics,2005:156-165.
46 MAUE J, SANDERS P, MATIJEVIC D. Goal-directed shortest-path queries using precomputed cluster distances [J]. J. Exp. Algorithmics,2009,14:3.2-3.27.
47 陈玉敏.大区域分布式多级道路网的最优路径算法与服务研究[D].中国武汉：武汉大学测绘遥感信息工程国家重点实验室,2005.
48 郑年波.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报,2007,12(7)：1280-1285.
49 CAR A, FRANK A. General Principles of Hierarchical Spatial Reasoning—The Case of Wayfinding[C] Proceedings of SDH'94..[S.l.]:[s.n.],1994.
50 CAR A, FRANK A U. Modelling a Hierarchy of Space Applied to Large Road Networks[C] IGIS'94:Proceedings of the International Workshop on Advanced Information Systems. London, UK:Springer-Verlag,1994:15-24.
51 陆锋.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报,2000,25(3)：269-275.
52 谢智颖.LBS系统中动态路径选择的理论与方法研究[D].中国武汉：武汉大学测绘遥感信息工程国家重点实验室,2003.
53 郑年波.面向动态导航的交通网络数据模型与应用算法研究[D].中国武汉：武汉大学测绘遥感信息工程国家重点实验室,2007.
54 COOKE K, HALSEY E. The shortest route through a network with time-dependent internodal transit times[J]. Journal of Mathematical Analysis and Applications, 1966,14(3):493-498.
55 KAUFMAN D, SMITH R. Fastest paths in time-dependent networks for intelli-gent vehicle-highway systems application [J]. Journal of Intelligent Transportation Systems,1993,1(1):1-11.
56 ZILIASKOPOULOS A, MAHMASSANI H. Time dependent, shortest-path algo-rithm for real-time intelligent vehicle highway system applications [J]. Transporta-tion Research Record,1993(1408):94-100.
57 CHABINI I. Discrete dynamic shortest path problems in transportation applica-tions:Complexity and algorithms with optimal run time[J]. Transportation Re-search Record:Journal of the Transportation Research Board,1998,1645(-1):170-175.
58 CHABINI I, DEAN B. Shortest path problem in discrete-time dynamic networks: complexity, algorithms and implementations[J]. MIT techinical report,1999.
59 HALPERN J. Shortest route with time dependent length of edges and limited delay possibilities in nodes [J]. Mathematical Methods of Operations Research,1977, 21(3):117-124.
60 ORDA A, ROM R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length [J]. Journal of the ACM (JACM),1990,37(3):607-625.
61 ORDA A, ROM R. Minimum weight paths in time-dependent networks[J]. Net-works,1991,21(3):295-319.
62 AHUJA R K, B.ORLIN J, PALLOTTINO S, et al. Dynamic Shortest Paths Mini-mizing Travel Times and Costs[J]. Networks,2001,41:205.
63 HALL R. The fastest path through a network with random time-dependent travel times[J]. Transportation Science,1986,20(3):182.
64 FU L, RILETT L. Expected shortest paths in dynamic and stochastic traffic net-works[J]. Transportation Research Part B,1998,32(7):499-516.
65 FU L. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information[J]. Transportation Research Part B:Methodological,2001, 35(8):749-765.
66 MILLER-HOOKS E, MAHMASSANI H. Least expected time paths in stochastic, time-varying transportation networks[J]. Transportation Science,2000,34(2):198.
67 TOMKO M, WINTER S, CLARAMUNT C. Experiential hierarchies of streets[J]. Computers,Environment and Urban Systems,2008,32(3):41-52.
68 JIANG B. Street hierarchies:a minority of streets account for a majority of traffic flow[J]. International Journal of Geographical Information Science,2009, 23(8):1033-1048.
69 建设部G.城市道路交通规划设计规范(50220-1995).
70 彭庆艳,蒋应红. 城市化进程中公路与城市道路关系研究[J]. 城市交通,2007,5(2)：47-50.
71 武晓晖.城市道路网合理性研究[D].中国成都：西南交通大学,2008.
72 KUWAHARA M. Hierarchical Road Network-Modeling for Planning and De-sign, http://www.iis.u-tokyo.ac.jp/cgi/teacher_kenkyuu.cgi?kenkyuu_id= 537&eng=1.
73 NEWMAN M E J. The Structure and Function of Complex Networks[J]. SIAM Review,2003,45:167-256.
74 JIANG B, CLARAMUNT C. Topological analysis of urban street networks [J]. Environment and Planning B,2004,31(1):151-162.
75 JIANG B, CLARAMUNT C. A Structural Approach to the Model Generalization of an Urban Street Network*[J]. Geoinformatica,2004,8(2):157-171.
76 PORTA S, CRUCITTI P, LATORA V. The network analysis of urban streets: a primal approach[J]. Environment and Planning B:Planning and Design,2005, 33(5):705-725.
77 PORTA S, CRUCITTI P, LATORA V. The network analysis of urban streets: a dual approach[J]. Physica A:Statistical Mechanics and its Applications,2006, 369(2):853-866.
78 CRUCITTI P, LATORA V, PORTA S. Centrality measures in spatial networks of urban streets [J]. Physical Review E,2006,73(3):36125.
79 BRANDES U. On variants of shortest-path betweenness centrality and their generic computation[J]. Social Networks,2008,30(2):136-145.
80 BADER D, KINTALI S, MADDURI K, et al. Approximating betweenness central-ity [J]. Algorithms and Models for the Web-Graph,2007:124-137.
81 KUIPERS B J. The Spatial Semantic Hierarchy [J]. Artificial Intelli-gence,2000,119:191-233. citeseer.ist.psu.edu/kuipers00spatial.html. http://www.cs.utexas.edu/users/qr/papers/Kuipers-aij-00.html.
82 KUIPERS B. An Intellectual History of the Spatial Semantic Hierarchy[M]. Berlin: Springer,2008:243-364.
83 TIMPF S, VOLTA G S, POLLOCK D W, et al. A conceptual model of wayfinding using multiple levels of abstraction[C] Proceedings of Theories and Methods of Spatio-Temporal Reasoning in Geographic Space.[S.l.]:Springer-Verlag,1992:348-367.
84 TIMPF S, KUHN W. Granularity Transformations in Wayfinding[C] Spatial Cognition Ⅲ.[S.l.]:springer,2003:1035.
85 GOLLEDGE R G. Path selection and route preference in human navigation: A progress report[J]. Spatial Information Theory A Theoretical Basis for GIS, 1995:207-222.
86 DUCKHAM M, KULIK L. "Simplest" Paths:Automated Route Selection for Navigation[J]. Spatial Information Theory,2003:169-185.
87 WINTER S. Route Adaptive Selection of Salient Features[J]. Spatial Information Theory,2003:349-361.
88 HAQUE S, KULIK L, KLIPPEL A. Algorithms for Reliable Navigation and Wayfinding[J]. Spatial Cognition V Reasoning, Action, Interaction,2008:308-326.
89 RICHTER K F, DUCKHAM M. Simplest Instructions:Finding Easy-to-Describe Routes for Navigation [J]. Geographic Information Science,2008:274-289.
90 BERNSTEIN D, KORNHAUSER A. An introduction to map matching for personal navigation assistants [J]. New Jersey TIDE Center,1996.
91 QUDDUS M. High integrity map matching algorithms for advanced transport telematics applications[D]. London,UK:Department of Civil and Environmental Engineering,Imperial College London,2006.
92 JOSHI R. A new approach to map matching for in-vehicle navigation systems:the rotational variation metric[J].2001 IEEE Intelligent Transportation Systems,2001. Proceedings,2001:33-38.
93 YIN H, WOLFSON O. A Weight-based Map Matching Method in Moving Objects Databases[C] SSDBM'04:Proceedings of the 16th International Conference on Scientific and Statistical Database Management. Washington, DC, USA:IEEE Computer Society,2004:437.
94 BRAKATSOULAS S, PFOSER D, SALAS R, et al. On map-matching vehicle tracking data[C] VLDB'05:Proceedings of the 31st international conference on Very large data bases.[S.l.]:VLDB Endowment,2005:853-864.
95 章威,徐建闽,林绵峰.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与信息,2007,7(2)：39-45.
96 GREENFELD J. Matching GPS observations to locations on a digital map[C] In Proc.81th Annual Meeting of the Transportation Research Board. Washington,DC: [s.n.],2002.
97 吴喜之.现代贝叶斯统计学[M].北京：中国统计出版社,2000.
98 BISHOP C, et al. Pattern recognition and machine learning[M].[S.l.]:Springer New York:,2006.
99 DUDA R, HART P, STORK D. Pattern classification[M]. New York:Wiley,2001.
100 BAYES R. T.(1763). An essay toward solving a problem in the doctrine of chances[J]. Philos. Trans. R. Soc. London,1763,53:370-418.
101 廖文等译.贝叶斯统计学原理,模型及应用[M].北京：中国统计出版社,1992.
102 SEP. Bayes Theorem.
103 CHENG J, GREINER R. Comparing Bayesian network classifiers[C] Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI'99).[S.l.]: Morgan Kaufmann Publishers,1999:101-107.
104 陈景年.选择性贝叶斯算法研究[D].中国北京：北京交通大学,2008.
105 FRIEDMAN N, GEIGER D, GOLDSZMIDT M. Bayesian network classifiers [J]. Machine learning,1997,29(2):131-163.
106 CHOW C, LIU C. Approximating discrete probability distributions with depen-dence trees[J]. IEEE transactions on Information Theory,1968,14(3):462-467.
107 FRIEDMAN N, GOLDSZMIDT M. Building classifiers using Bayesian networks[C] Proceedings of the National Conference on Artificial Intelligence. AAAI:[s.n.] 1996:1277-1284.
108 MEHLHORN K, SANDERS P. Algorithms and data strutures[M]. Berlin:Springer, 2008.
109 AURENHAMMER F. Voronoi diagrams—a survey of a fundamental geometric data structure[J]. ACM Comput. Surv.,1991,23(3):345-405.
110 PREPARATA F, SHAMOS M. Computational geometry:an introduction[M].[S.l.]: Springer,1985.
111 OKABE A, BOOTS B, SUGIHARA K. Nearest neighbourhood operations with generalized Voronoi diagrams:a review[J]. International Journal of Geographical Information Science,1994,8(1):43-71.
112 OKABE A, SUZUKI A. Locational optimization problems solved through Voronoi diagrams[J]. European Journal of Operational Research,1997,98(3):445-456.
113 CHEN J, LI C, LI Z, et al. A Voronoi-based 9-intersection model for spatial relations [J]. International Journal of Geographical Information Science,2001, 15(3):201-220.
114 ERWIG M, HAGEN F. The graph Voronoi diagram with applications [J]. Networks, 2000,36(3):156-163.
115 KOLAHDOUZAN M, SHAHABI C. Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases[C] Proceedings of the 30th VLDB Conference. Toronto,Canada:[s.n.],2004:840-851.
2 BERTSIMAS D, TSITSIKLIS J N. Introduction to linear optimization[M].[S.l.]: Athena Scientific, Belmont, Massachusetts,1997.
3 SHIMBEL A. Structure in Communication Nets[C] In Proceedings of the Sym-posium on Information Networks. Brooklyn:Polytechnic Press of the Polytechnic Institute of Brooklyn,1955:199-203.
4 DANTZIG G B. Discrete-Variable Extremum Problems[J]. Operations Research, 1957,5(2):266-277.
5 MOORE E. The shortest path through a maze[C] Proceedings of the International Symposium on the Theory of Switching. Cambridge, Massachusetts:Harvard Uni-versity Press,1959,2:285-292.
6 BELLMAN R. On a routing problem[J]. Quart. Appl. Math.,1958,16:87-90.
7 DIJKSTRA E. A note on two problems in connexion with graphs[J]. Numerische Mathematik,1959:269-271.
8 PAPE U. Implementation and efficiency of Moore-algorithms for the shortest route problem[J]. Mathematical Programming,1974,7(1):212-222.
9 PALLOTINO S. Shortest path methods:Complexity, interrelations and new propo-sitions[J]. Networks,1984,14(2):257-267.
10 GLOVER F, KLINGMAN D, PHILLIPS N. A New Polynomially Bounded Shortest Path Algorithm[J]. Operations Research,1985,33(1):65-73. http://www. jstor. org/stable/170867.
11 GOLDBERG T, A.V.AND RADZIK. A heuristic improvement of the Bellman-Ford algorithm[J]. Applied Mathematics Letters,1993,6(3):3-6.
12 WILLIAMS J. Algorithm 232:heapsort[J]. Communications of the ACM,1964, 7(6):347-348.
13 DIAL R B. Algorithm 360:shortest-path forest with topological ordering[J]. Com-mun. ACM,1969,12(11):632-633.
14 JOHNSON D B. Efficient Algorithms for Shortest Paths in Sparse Networks[J]. J. ACM,1977,24(1):1-13.
15 FREDMAN M, TARJAN R. Fibonacci heaps and their uses in improved network optimization algorithms [J]. Journal of the ACM (JACM),1987,34(3):596-615.
16 AHUJA R K, MEHLHORN K, ORLIN J, et al. Faster algorithms for the shortest path problem[J]. J. ACM,1990,37(2):213-223.
17 CHERKASSKY B V, GOLDBERG A V, SILVERSTEIN C. Buckets, heaps, lists, and monotone priority queues[C] SODA'97:Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA:Society for In-dustrial and Applied Mathematics,1997:83-92.
18 RAMAN R. Recent results on the single-source shortest paths problem[J]. ACM SIGACT News,1997,28(2):81-87.
19 THORUP M. Integer priority queues with decrease key in constant time and the single source shortest paths problem [J]. Journal of Computer and System Sciences, 2004,69(3):330-353. Special Issue on STOC 2003.
20 CHERKASSKY B, GOLDBERG A, RADZIK T. Shortest paths algorithms:theory and experimental evaluation [J]. Mathematical programming,1996,73(2):129-174.
21 ZHAN F, NOON C. Shortest path algorithms:An evaluation using real road networks.[J]. Transportation Science,1998,32(2):65-73.
22 HART P E, NILSSON N J, RAPHAEL B. A Formal Basis for the Heuristic De-termination of Minimum Cost Paths [J]. IEEE Transactions of systems science and cybernetics,1968, ssc-4(2):100-107.
23 FU L, SUN D, RILETT L. Heuristic shortest path algorithms for transporta-tion applications:state of the art[J]. Computers & Operations Research,2006, 33(11):3324-3343.
24 LARK III J, WHITE III C, SYVERSON K. A best-first search algorithm guided by a set-valued heuristic[J]. IEEE Transactions on Systems, Man and Cybernetics, 1995,25(7):1097-1101.
25 REINEFELD A, MARSLAND T. Enhanced iterative-deepening search[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1994,16(7):701-710.
26 ZENG W, CHURCH R L. Finding shortest paths on real road networks:the case for A*[J]. International Journal of Geographical Information Science,2009, 23(4):531-543.
27 LIU B. Route finding by using knowledge about the road network[J]. IEEE Transactions on systems,man,and cybernetics-part A:systems and humans,1997, 27(4):436-448.
28 DANTZIG G. On the shortest route through a network[J]. Management Science, 1960,6(1):87-90.
29 NICHOLSON T A J. Finding the Shortest Route between Two Points in a Network[J]. The Computer Journal,1966,9(3):275-280. http://comjnl. oxfordjournals.org/cgi/content/abstract/9/3/275.
30 POHL I. Bi-directional search[J]. Machine Intelligence,1971:127-140.
31 SINT L, DE CHAMPEAUX D. An Improved Bidirectional Heuristic Search Algo-rithm[J]. J. ACM,1977,24(2):177-191.
32 DE CHAMPEAUX D. Bidirectional Heuristic Search Again[J]. J. ACM,1983, 30(1):22-32.
33 KWA J B. BS*:an admissible bidirectional staged heuristic search algorithm[J]. Artif. Intell.,1989,38(1):95-109.
34 KAINDL H, KAINZ G. Bidirectional heuristic search reconsidered [J]. Journal of Artificial Intelligence Research,1997.
35 DREYFUS S. An appraisal of some shortest-path algorithms [J]. Operations Re-search,1969:395-412.
36 BAST H, FUNKE S, MATIJEVIC D, et al. In Transit to Constant Time Shortest-Path Queries in Road Networks[C]. APPLEGATE D, BRODAL G.9th Workshop on Algorithm Enginneering and Experiments (ALENEX'07). New Orleans, USA: SIAM,2007:toappear.
37 SANDERS P, SCHULTES D. Highway Hierarchies Hasten Exact Shortest Path Queries[C] Proceedings 17th European Symposium on Algorithms (ESA).2005. Berlin:Springer, Springer LNCS, vol.3669.
38 ISHIKAWA K, OGAWA M, AZUMA S, et al. Map navigation software of the electro-multivision of the'91 Toyoto Soarer[J]. Vehicle Navigation and Information Systems Conference,1991,1991,2:463-473.
39 JING N, HUANG Y W, RUNDENSTEINER E A. Hierarchical Encoded Path Views for Path Query Processing:An Optimal Model and Its Performance Evaluation [J]. IEEE Trans. Knowledge and Data Engineering,1998,10(3). http://citeseer. ist.psu.edu/j ing98hierarchical.html.
40 JUNG S, PRAMANIK S. An Efficient Path Computation Model for Hierarchi-cally Structured Topographical Road Maps[J]. IEEE Trans. Knowledge and Data Engineering,2002,14(5).
41 WAGNER D, WILLHALM T. Geometric Speed-Up Techniques for Finding Short-est Paths in Large Sparse Graphs[C] Proc.11th European Symposium on Algo-rithms (ESA).2003. Berlin:Springer, LNCS, vol.2832.
42 GUTMAN R. Reach-Based Routing:A New Approach to Shortest Path Algo-rithms Optimized for Road Networks [C] Proceedings 6th Workshop on Algorithm Engineering and Experiments (ALENEX). Philadelphia,USA:SIAM,2004:100-111.
43 FLINSENBERG I C. Route Planning Algorithms for Car Navigation[D]. Eind-hoven:Technische Universiteit Eindhoven,2004.
44 KOHLER E, MOHRING R, SCHILLING H. Acceleration of shortest path and constrained shortest path computation [J]. Experimental and Efficient Algorithms, 2005:126-138.
45 GOLDBERG A V, HARRELSON C. Computing the shortest path:A search meets graph theory[C] SODA'05:Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms. Philadelphia, PA, USA:Society for Industrial and Applied Mathematics,2005:156-165.
46 MAUE J, SANDERS P, MATIJEVIC D. Goal-directed shortest-path queries using precomputed cluster distances [J]. J. Exp. Algorithmics,2009,14:3.2-3.27.
47 陈玉敏.大区域分布式多级道路网的最优路径算法与服务研究[D].中国武汉：武汉大学测绘遥感信息工程国家重点实验室,2005.
48 郑年波.一种基于道路网络层次拓扑结构的分层路径规划算法[J].中国图象图形学报,2007,12(7)：1280-1285.
49 CAR A, FRANK A. General Principles of Hierarchical Spatial Reasoning—The Case of Wayfinding[C] Proceedings of SDH'94..[S.l.]:[s.n.],1994.
50 CAR A, FRANK A U. Modelling a Hierarchy of Space Applied to Large Road Networks[C] IGIS'94:Proceedings of the International Workshop on Advanced Information Systems. London, UK:Springer-Verlag,1994:15-24.
51 陆锋.基于层次空间推理的交通网络行车最优路径算法[J].武汉测绘科技大学学报,2000,25(3)：269-275.
52 谢智颖.LBS系统中动态路径选择的理论与方法研究[D].中国武汉：武汉大学测绘遥感信息工程国家重点实验室,2003.
53 郑年波.面向动态导航的交通网络数据模型与应用算法研究[D].中国武汉：武汉大学测绘遥感信息工程国家重点实验室,2007.
54 COOKE K, HALSEY E. The shortest route through a network with time-dependent internodal transit times[J]. Journal of Mathematical Analysis and Applications, 1966,14(3):493-498.
55 KAUFMAN D, SMITH R. Fastest paths in time-dependent networks for intelli-gent vehicle-highway systems application [J]. Journal of Intelligent Transportation Systems,1993,1(1):1-11.
56 ZILIASKOPOULOS A, MAHMASSANI H. Time dependent, shortest-path algo-rithm for real-time intelligent vehicle highway system applications [J]. Transporta-tion Research Record,1993(1408):94-100.
57 CHABINI I. Discrete dynamic shortest path problems in transportation applica-tions:Complexity and algorithms with optimal run time[J]. Transportation Re-search Record:Journal of the Transportation Research Board,1998,1645(-1):170-175.
58 CHABINI I, DEAN B. Shortest path problem in discrete-time dynamic networks: complexity, algorithms and implementations[J]. MIT techinical report,1999.
59 HALPERN J. Shortest route with time dependent length of edges and limited delay possibilities in nodes [J]. Mathematical Methods of Operations Research,1977, 21(3):117-124.
60 ORDA A, ROM R. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length [J]. Journal of the ACM (JACM),1990,37(3):607-625.
61 ORDA A, ROM R. Minimum weight paths in time-dependent networks[J]. Net-works,1991,21(3):295-319.
62 AHUJA R K, B.ORLIN J, PALLOTTINO S, et al. Dynamic Shortest Paths Mini-mizing Travel Times and Costs[J]. Networks,2001,41:205.
63 HALL R. The fastest path through a network with random time-dependent travel times[J]. Transportation Science,1986,20(3):182.
64 FU L, RILETT L. Expected shortest paths in dynamic and stochastic traffic net-works[J]. Transportation Research Part B,1998,32(7):499-516.
65 FU L. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information[J]. Transportation Research Part B:Methodological,2001, 35(8):749-765.
66 MILLER-HOOKS E, MAHMASSANI H. Least expected time paths in stochastic, time-varying transportation networks[J]. Transportation Science,2000,34(2):198.
67 TOMKO M, WINTER S, CLARAMUNT C. Experiential hierarchies of streets[J]. Computers,Environment and Urban Systems,2008,32(3):41-52.
68 JIANG B. Street hierarchies:a minority of streets account for a majority of traffic flow[J]. International Journal of Geographical Information Science,2009, 23(8):1033-1048.
69 建设部G.城市道路交通规划设计规范(50220-1995).
70 彭庆艳,蒋应红. 城市化进程中公路与城市道路关系研究[J]. 城市交通,2007,5(2)：47-50.
71 武晓晖.城市道路网合理性研究[D].中国成都：西南交通大学,2008.
72 KUWAHARA M. Hierarchical Road Network-Modeling for Planning and De-sign, http://www.iis.u-tokyo.ac.jp/cgi/teacher_kenkyuu.cgi?kenkyuu_id= 537&eng=1.
73 NEWMAN M E J. The Structure and Function of Complex Networks[J]. SIAM Review,2003,45:167-256.
74 JIANG B, CLARAMUNT C. Topological analysis of urban street networks [J]. Environment and Planning B,2004,31(1):151-162.
75 JIANG B, CLARAMUNT C. A Structural Approach to the Model Generalization of an Urban Street Network*[J]. Geoinformatica,2004,8(2):157-171.
76 PORTA S, CRUCITTI P, LATORA V. The network analysis of urban streets: a primal approach[J]. Environment and Planning B:Planning and Design,2005, 33(5):705-725.
77 PORTA S, CRUCITTI P, LATORA V. The network analysis of urban streets: a dual approach[J]. Physica A:Statistical Mechanics and its Applications,2006, 369(2):853-866.
78 CRUCITTI P, LATORA V, PORTA S. Centrality measures in spatial networks of urban streets [J]. Physical Review E,2006,73(3):36125.
79 BRANDES U. On variants of shortest-path betweenness centrality and their generic computation[J]. Social Networks,2008,30(2):136-145.
80 BADER D, KINTALI S, MADDURI K, et al. Approximating betweenness central-ity [J]. Algorithms and Models for the Web-Graph,2007:124-137.
81 KUIPERS B J. The Spatial Semantic Hierarchy [J]. Artificial Intelli-gence,2000,119:191-233. citeseer.ist.psu.edu/kuipers00spatial.html. http://www.cs.utexas.edu/users/qr/papers/Kuipers-aij-00.html.
82 KUIPERS B. An Intellectual History of the Spatial Semantic Hierarchy[M]. Berlin: Springer,2008:243-364.
83 TIMPF S, VOLTA G S, POLLOCK D W, et al. A conceptual model of wayfinding using multiple levels of abstraction[C] Proceedings of Theories and Methods of Spatio-Temporal Reasoning in Geographic Space.[S.l.]:Springer-Verlag,1992:348-367.
84 TIMPF S, KUHN W. Granularity Transformations in Wayfinding[C] Spatial Cognition Ⅲ.[S.l.]:springer,2003:1035.
85 GOLLEDGE R G. Path selection and route preference in human navigation: A progress report[J]. Spatial Information Theory A Theoretical Basis for GIS, 1995:207-222.
86 DUCKHAM M, KULIK L. "Simplest" Paths:Automated Route Selection for Navigation[J]. Spatial Information Theory,2003:169-185.
87 WINTER S. Route Adaptive Selection of Salient Features[J]. Spatial Information Theory,2003:349-361.
88 HAQUE S, KULIK L, KLIPPEL A. Algorithms for Reliable Navigation and Wayfinding[J]. Spatial Cognition V Reasoning, Action, Interaction,2008:308-326.
89 RICHTER K F, DUCKHAM M. Simplest Instructions:Finding Easy-to-Describe Routes for Navigation [J]. Geographic Information Science,2008:274-289.
90 BERNSTEIN D, KORNHAUSER A. An introduction to map matching for personal navigation assistants [J]. New Jersey TIDE Center,1996.
91 QUDDUS M. High integrity map matching algorithms for advanced transport telematics applications[D]. London,UK:Department of Civil and Environmental Engineering,Imperial College London,2006.
92 JOSHI R. A new approach to map matching for in-vehicle navigation systems:the rotational variation metric[J].2001 IEEE Intelligent Transportation Systems,2001. Proceedings,2001:33-38.
93 YIN H, WOLFSON O. A Weight-based Map Matching Method in Moving Objects Databases[C] SSDBM'04:Proceedings of the 16th International Conference on Scientific and Statistical Database Management. Washington, DC, USA:IEEE Computer Society,2004:437.
94 BRAKATSOULAS S, PFOSER D, SALAS R, et al. On map-matching vehicle tracking data[C] VLDB'05:Proceedings of the 31st international conference on Very large data bases.[S.l.]:VLDB Endowment,2005:853-864.
95 章威,徐建闽,林绵峰.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与信息,2007,7(2)：39-45.
96 GREENFELD J. Matching GPS observations to locations on a digital map[C] In Proc.81th Annual Meeting of the Transportation Research Board. Washington,DC: [s.n.],2002.
97 吴喜之.现代贝叶斯统计学[M].北京：中国统计出版社,2000.
98 BISHOP C, et al. Pattern recognition and machine learning[M].[S.l.]:Springer New York:,2006.
99 DUDA R, HART P, STORK D. Pattern classification[M]. New York:Wiley,2001.
100 BAYES R. T.(1763). An essay toward solving a problem in the doctrine of chances[J]. Philos. Trans. R. Soc. London,1763,53:370-418.
101 廖文等译.贝叶斯统计学原理,模型及应用[M].北京：中国统计出版社,1992.
102 SEP. Bayes Theorem.
103 CHENG J, GREINER R. Comparing Bayesian network classifiers[C] Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI'99).[S.l.]: Morgan Kaufmann Publishers,1999:101-107.
104 陈景年.选择性贝叶斯算法研究[D].中国北京：北京交通大学,2008.
105 FRIEDMAN N, GEIGER D, GOLDSZMIDT M. Bayesian network classifiers [J]. Machine learning,1997,29(2):131-163.
106 CHOW C, LIU C. Approximating discrete probability distributions with depen-dence trees[J]. IEEE transactions on Information Theory,1968,14(3):462-467.
107 FRIEDMAN N, GOLDSZMIDT M. Building classifiers using Bayesian networks[C] Proceedings of the National Conference on Artificial Intelligence. AAAI:[s.n.] 1996:1277-1284.
108 MEHLHORN K, SANDERS P. Algorithms and data strutures[M]. Berlin:Springer, 2008.
109 AURENHAMMER F. Voronoi diagrams—a survey of a fundamental geometric data structure[J]. ACM Comput. Surv.,1991,23(3):345-405.
110 PREPARATA F, SHAMOS M. Computational geometry:an introduction[M].[S.l.]: Springer,1985.
111 OKABE A, BOOTS B, SUGIHARA K. Nearest neighbourhood operations with generalized Voronoi diagrams:a review[J]. International Journal of Geographical Information Science,1994,8(1):43-71.
112 OKABE A, SUZUKI A. Locational optimization problems solved through Voronoi diagrams[J]. European Journal of Operational Research,1997,98(3):445-456.
113 CHEN J, LI C, LI Z, et al. A Voronoi-based 9-intersection model for spatial relations [J]. International Journal of Geographical Information Science,2001, 15(3):201-220.
114 ERWIG M, HAGEN F. The graph Voronoi diagram with applications [J]. Networks, 2000,36(3):156-163.
115 KOLAHDOUZAN M, SHAHABI C. Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases[C] Proceedings of the 30th VLDB Conference. Toronto,Canada:[s.n.],2004:840-851.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |