加快傳統Dijkstra最短路徑計算的方法，可依有無分群資訊輔助劃分為兩類，無分群資訊的方法例如雙向搜尋、直線距離A*、有向地標A*，雖然可提升搜尋效率，但由於路網節點數眾多，提升程度很快遇到瓶頸。有分群資訊的方法中，一種是記錄每個有向邊可到達群的集合，以限制展開節點數，但其前處理時間很耗時。另一種採用階層概念，將路網利用分群劃分為高低兩層級，高層路網可由各低層路網的邊界點構成。找尋最短路徑時透過高層路網可減少展開低層節點數。這類方法依照高低層級路網選擇記錄資訊之不同，所佔用的記憶體及搜尋效率表現也不同。
本文研究給定圖形分群之下的階層式最短路徑演算法，利用其前處理得到的輔助資訊加速最短路徑的搜尋。其中高層路網記錄任兩邊界點最短距離及沿途路徑下一節點，低層路網則記錄任一點往返邊界點之最短距離及下或上一節點。對於無交集的分群結果，提供了建立邊界點演算法以找尋銜接各分群之節點。而路徑搜尋的演算核心，提出三個可省除輔助資訊記錄之空間的方案以供選擇，並整理出時空成本考量下的各種方案。至於起終點同群的情況，提出改良式有向地標演算法(群內邊界點ALT)。實驗以台灣路網進行搜尋時間以及所需空間的評估，並與HEPV、Wang兩階層式作法進行比較，結果顯示本文提出的演算法組合空間需求較低，且能在數毫秒內完成最短路徑的搜尋。

Based on use of the cluster information or not, there are two types of techniques for speedup of shortest path computation. Without the cluster information, traditional speedup techniques such as bidirectional search, A* search, and ALT (A* search with Landmarks and Triangle inequality) search can improve the search efficiency but soon reach a bottleneck as the road network grows large. With the cluster information, one kind of cluster-based approach records the set of clusters that each directed edge can reach without detour. It can restrict the number of nodes expanded during the shortest path search, but computing the cluster set information consumes too much time. The other kind of cluster-based approach uses the concept of hierarchical road networks. Nodes of the same clusters form the low-level networks. The high-level network is then built on the border nodes of the low-level networks. Using the high-level network can reduce the number of nodes expanded in low-level networks. The memory requirement and the search efficiency of this approach will vary with the amount of information recorded in high-level and low-level networks.

We study the cluster-based approach which precomputes the hierarchical network information to speed up the search. Specifically, our high-level network records the distance and the next border node of the shortest path for each pair of border nodes. Our low-level network records the to/fro distance and the next/previous node of the shortest path between each node in a low-level network and each of its border nodes. For clustering algorithms which produce disjoint clusters, we propose a border node construction algorithm to find minimal border nodes shared by clusters. Based on the constructed hierarchical networks, several cluster-based algorithms for shortest path computation are implemented. For the case of limited memory, we also propose three alternative search options for space reduction. For the case of intra cluster search where traditional cluster-based methods cannot apply, a local cluster-based ALT is proposed to reduce the node expansion during search. Based on the Taiwan road network, our approach is evaluated in terms of the search time and the memory requirement. For comparison, the space and time complexities of HEPV, Wang's approach and ours are analyzed. The evaluation results show that our approach require less memory and can finish shortest path search in just several milliseconds.

1. 前言       1
1.2. 研究動機與目的	1
1.3. 研究架構	2
2. 文獻探討	3
2.1. 最短路徑的計算	3
2.1.1. 無分群資訊的最短路徑演算法	3
2.1.2. 有分群資訊的最短路徑演算法	6
2.2. 圖形分割方法	9
2.2.1. kd-tree partition	9
2.2.2. METIS	10
3. 基本方法介紹	12
3.1. 基本圖形定義	12
3.2. 分群概念模型	12
3.3. 最短路徑求解	16
3.3.1. 利用階層圖可求解最短路徑長度之證明	16
3.3.2. 分群最短路徑演算法	17
3.3.3. 最短路徑重建演算法	22
4. 延伸方法介紹	27
4.1. 階層圖記錄資訊之省除	27
4.1.1. findNextBorderNode演算法	27
4.1.2. findNextNode演算法	28
4.1.3. findPrevNode演算法	30
4.2. 群間圖之省除—只利用群內圖Dijkstra	31
4.3. 全域地標資訊之省除—只利用群內邊界點ALT	33
5. 實作架構	35
5.1. 實驗環境	35
5.2. 系統架構	35
5.3. 前處理	37
5.4. 實驗與討論	41
5.4.1. 起終點同群且皆非邊界點，傳統ALT與群內邊界點ALT比較	42
5.4.2. 空間省除方法比較	44
5.4.3. kd-tree與METIS分群方法比較	48
5.4.4. 在距離、時間成本地圖中，起終點遠近程度影響之觀察	49
5.5. 與HEPV、Wang之比較	54
6. 結論與未來發展	63
參考文獻	65
附錄一、資料結構	67
附錄二、最短路徑長度求解證明(3.3.1.節Lemma 1～3.)	71
 

圖目錄

圖2.1：Dijkstra演算法搜尋擴散範圍	4
圖2.2：A*搜尋擴散範圍與Dijkstra比對圖	5
圖2.3：HEPV中Spuer Graph的Encoded Path View	7
圖2.4：Wang的邊界點定義	8
圖2.5：採用中位點切割之2d-tree及其原始資料點	10
圖2.6：METIS分群流程	11
圖3.1：圖形G及其子圖(群)	15
圖3.2：群內圖，及點A,J的群內路徑資訊	15
圖3.3：群間圖Gborder，及點C,D的群間路徑資訊	15
圖3.4：演算法架構	16
圖3.5：起終點皆為邊界點	18
圖3.6：起終點不同群，且至少一方非邊界點	18
圖3.7：起終點同群，且一方為邊界點	18
圖3.8：起終點同在群內	18
圖3.9：分群最短路徑演算法流程	19
圖3.10：分群最短路徑演算法	21
圖3.11：起點s到終點e的最短路徑	23
圖3.12：邊界點到邊界點路徑重建演算法	24
圖3.13：群內點到邊界點路徑重建	25
圖3.14：邊界點到群內點路徑重建	26
圖4.1：取得「起點邊界點到終點邊界點」的起點下一邊界點	28
圖4.2：取得「群內點到同群邊界點」的起點下一節點	29
圖4.3：取得「邊界點到同群群內點」的終點上一節點	30
圖4.4：群內圖Dijkstra的所有可能擴散路徑	31
圖4.5：群內邊界點ALT演算法流程	33
圖4.6：群內邊界點ALT的區域與經邊界點最短路徑	34
圖5.0：系統架構圖	36
圖5.1：前處理流程	37
圖5.2：建立邊界點演算法	38
圖5.3：採用METIS或kd-tree群間無節點交集之分群結果	39
圖5.4：METIS、kd-tree分群及地標示意圖	39
圖5.5：傳統ALT與各項組合下之群內邊界ALT的搜尋時間	43
圖5.6：各種空間省除方法組合搜尋時間(起終不同群且至少一方非邊界點)	44
圖5.7：各種空間省除方法組合搜尋時間(隨機起終點分佈)	46
圖5.8：空間省除方法組合的搜尋時間、所需空間關係圖及明細	47
圖5.9：CB最快組合在兩種不同分群方法下之搜尋速度 (固定128群)	48
圖5.10：距離成本地圖中，各起終點遠近程度下的搜尋時間盒狀圖及明細(METIS 128群)	51
圖5.11：時間成本地圖中，各起終點遠近程度下的搜尋時間盒狀圖及明細(METIS 128群)	53
圖5.12：分群數量與總邊界點數量關係 (採用METIS與kd-tree分群方法)	55
圖5.13：METIS分群下，CB、HEPV、Wang所需空間觀測及比較結果	57
圖5.14：CB空間省除方法各項組合所需空間趨勢	58

 
表目錄

表3.1：圖3.11範例中，各路段採用重建演算法對照	23
表4.1：可改用findNextBorderNode之虛擬碼位置對應	28
表5.1：實驗環境	35
表5.2：前處理資訊	40
表5.3：各項實驗的初始參數設定	42
表5.4：空間省除方法組合明細	42
表5.5：任意起終點詳細分佈內容	46
表5.6：各級道路速限	49
表5.7：距離成本地圖中，各遠近程度下之起終點分佈	50
表5.8：時間成本地圖中，各遠近程度下之起終點分佈	52
表5.9：評估變數設定	54
表5.10：群內圖、群間圖欄位大小	55
表5.11：CB、HEPV、Wang前處理檔案大小比較	56
表5.12：CB、HEPV、Wang前處理時間複雜度比較	59
表5.13：CB、HEPV、Wang最短路徑長度求解時間複雜度比較	61
表5.14：CB空間省除各組合下之路徑重建複雜度整理	62

[1]	謝逢鳴，有前處裡下最短路徑演算法之研究，淡江大學資訊管理系碩士論文，2006年。
[2]	A.V. Goldberg and C. Harrelson, “Computing the shortest path: A* search meets graph theory,” 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '05),Vancouver, Canada, 2005.
[3]	A.V. Goldberg and R. Werneck, “Computing point-to-point shortest paths from external memory,” SIAM Workshop on Algorithms Engineering and Experimentation (ALENEX '05), Vancouver, Canada, 2005.
[4]	B. Liu, “Route finding by using knowledge about the road network,” IEEE Transactions On Systems, Man, and Cybernetics-Part A: Systems and Humans, 27(4), 1997, pp. 436-448.
[5]	D. Schultes, “Fast and exact shortest path quries using highway hierarchies,” Master’s thesis, Department of Computer Science, Universitt des Saarlandes, Germany, 2005.
[6]	E. W. Dijkstra, “A note on two problems in connecion with graphs,” Numerische Mathematik, 1, 1959, pp. 269-271.
[7]	F. B. Zhan and C. E. Noon, “Shortest path algorithms: An evaulation using real road networks,” Transportation Science, 32(1), 1998, pp. 65-73.
[8]	H. Samet, The Design and Analysis of Spatial Data Structures, Addison Wesley, 1989.
[9]	E. Kohler, R. H. Mohring , and H. Schilling,“Acceleration of shortest path and constrained shortest path computation,” Institute of Mathematics, TU Berlin, 2004.
[10]	F. Schulz, D. Wagner, and K. Weihe, “Dijkstra's algorithm on-line: An empirical case study from public railroad transport, ” ACM Journal of Experimental Algorithmics, vol. 5, no. 12, 2000.
[11]	G. Karypis and V. Kumar, “A fast and high quality multilevel scheme for partitioning irregular graphs,” Tech. Rep. No.95-035, University of Minnesota, Department of Computer Science / Army HPC Research Center, Minneapolis, MN 55455, 1998.
[12]	G. Karypis and V. Kumar, “ Multilevel algorithm for multi-constraint graph partitioning ,” Tech. Rep. No.98-019, University of Minnesota, Department of Computer Science / Army HPC Research Center, Minneapolis, MN 55455, 1998.
[13]	G. Karypis and V. Kumar, “ Multilevel k-way partitioning scheme for irregular graphs,” Tech. Rep. No.95-064, University of Minnesota, Department of Computer Science / Army HPC Research Center, Minneapolis, MN 55455, 1998.
[14]	P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, SSC4 (2), 1968, pp. 100-107.
[15]	M. B. Habbal, H. N. Koutsopoulos, and S. R. Lerman, “A decomposition algorithm for the all-pairs shortest path problem on massively parallel computer architectures,” Transportation Science, 28(4), 1994, pp. 292-308.
[16]	R. H. Mohring, H. Schilling, B. Schutz, D. Wagner, and T. Willhalm, “Partitioning graphs to speed up Dijkstra’s algorithm,” Submitted to WEA, 2005.
[17]	R. Hamill and N. Martin, “Database support for path query functions,” Key Technologies for Data Management, Proc. BNCOD 21, Springer Verlag, LNCS 3112, 2004, pp. 84-99.
[18]	S. Jung and S. Pramanik, “An efficient path computation model for hierarchy structured topographical road,” IEEE Transactions of Knowledge and Data Engineering, 14(5), 2002, pp. 1029-1046.
[19]	T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms 2nd Edition, 2001.
[20]	Y.-W. Huang, N. Jing, and E. A. Rundensteiner, “Hierarchical optimization of optimal path finding for transportation applications,” ACM 5th Int. Conf on Information and Knowledge Management (CIKM'96), Rockville, Maryland, USA, 1996, pp.261-268.
[21]	Y.-W. Huang, N. Jing, and E. A. Rundensteiner, “Optimizing path query performance: graph clustering strategies”, Transportation Research part C, 8, 2000, pp. 381-408.
[22]	Z. Wang, O. Che, L. Chen, and A. Lim, “An efficient shortest path computation system for real road networks,” Lecture Notes in Computer Science, 4031, 2006.