點到點之間的最短路徑問題是近年普遍研究及關注的焦點，也常應用於地理資訊系統(GIS)上。有關求解最短路徑的演算法從最早提出的Dijkstra演算法，到後來慢慢加入輔助資訊的直線A*演算法和有向地標 A*演算法等，其執行時間和效率逐漸有所改善。最短路徑演算法傳統常用於一般開車路網地圖上，找尋起迄兩點間最短距離路徑，但是卻少見應用於大眾運輸系統上。目前全球各地捷運及公車路網越來越發達，也越來越複雜，對於這方面的研究也就更顯重要。大眾運輸系統的路網和開車路網有諸多不同之處，例如行車路線固定、最短路徑需要考量轉乘時間和次數、不同交通工具共線問題等。本研究針對高鐵、鐵路、公車及捷運等路網系統，使用前處理整合成一份具轉乘資訊的共通路網。計算最短路徑時分成距離和時間兩種成本模式，並分別考量轉乘次數及轉乘時間，提出多維度索引標籤的擴充法。最後於實驗結果找出適合於各種應用情況的演算法，我們發現在距離成本模式下以一維索引標籤8-地標A*演算法表現最好，而在時間成本模式下則以二維索引標籤Dijkstra擴充演算法表現較佳。最後我們提供一個綜合應用模式，讓使用者可在選擇起終點、距離或時間成本模式、指定轉乘次數之下，快速找到最短路徑，並展示實做出的圖形使用者介面(GUI)。

The point-to-point shortest path problem has been a hot topic of research for many years. It has often found application in the geographic information systems. Many algorithms provide solution to the shortest path problem, which evolve from the early Dijkstra algorithm, the straight-line A* algorithm, to the landmark A* algorithm. The A* algorithms can use the auxiliary remaining distance information to improve execution time and efficiency. The shortest path algorithm is often used in the roadmap for car drivers to find the shortest path between two points. It is still not popular to see its application in the route map for public transportation systems. As the subway and the bus systems develop worldwide, their route maps tend to be more complex. The research on finding the shortest path in such route maps will become important. The route map has many features unlike its roadmap counterpart, which include fixed route lines, co-running routes, and factors of transfer time and transfer count. In this work, we use preprocessing to generate an integrated route map with transfer information from Taiwan High Speed Rail, Taiwan Railway, the bus, and the metropolitan rapid transit (MRT) systems in Taipei. We propose an extension to the shortest path algorithm which uses multi-dimensional labels for route information indexing. It allows the computation of cost in distance or time, and the consideration of the transfer time and the transfer count. In the experiments, we found that in the distance cost mode, the 8-landmark A* algorithm indexed by 1-dimensional labels performs the best. We also found that in the time cost mode, the Dijkstra algorithm indexed by two-dimensional labels performs the best. Finally we demonstrated a graphic user interface which allows the selection of start and end stations, the distance or time cost mode, and the desired transfer counts to find the shortest paths in the integrated route map in a short time.

第一章	緒論	1
1.1	研究背景與動機	1
1.2	研究問題與目的	1
1.3	研究架構	2
第二章	文獻探討	4
2.1	戴氏演算法（Dijkstra）	4
2.2	直線距離A*	5
2.3	有向地標A*	6
2.4	大眾運輸路網最短路徑問題	7
2.5	大眾運輸路網特色及地圖建置上的困難	8
2.6	現有公車捷運系統之現況	8
第三章	方法介紹	9
3.1	本研究前處理說明	9
3.1.1	預處理表格產生過程及表格定義	9
3.1.2	大眾運輸路網地圖轉乘點擷取標準	12
3.1.3	同位點及不可合併節點設定	12
3.1.4	利用座標資訊檢查路線沿途兩相鄰車站之輸入路徑距離	13
3.1.5	利用座標資訊檢查任兩點最短路徑沿途之預設路徑距離	13
3.1.6	前處理流程概要	14
3.2	問題定義	21
3.3	擴充不同路徑狀態索引標籤的最短路徑演算法	23
3.3.1	擴充演算法說明	23
3.3.2	不計轉乘次數一維索引標籤距離成本最短路徑演算法	24
3.3.3	含轉乘時間二維索引標籤時間成本最短路徑演算法	26
3.3.4	考慮轉乘次數三維索引標籤距離成本及時間成本最短路徑演算法	30
3.4	三種演算法範例說明	32
3.5	回溯最短路徑	36
3.5.1	一維索引標籤距離成本演算法之路徑回溯	36
3.5.2	二維索引標籤時間成本演算法之路徑回溯	39
3.5.3	三維索引標籤演算法可選擇轉乘次數之下距離成本或時間成本之路徑回溯     40
第四章	實驗結果	41
4.1	實驗設計	41
4.2	實驗環境	41
4.3	採用地圖及評估指標	41
4.4	不計轉乘次數之一維索引標籤演算法最短距離成本評估	42
4.5	含轉乘時間之二維索引標籤演算法最短時間成本評估	45
4.6	三維索引標籤演算法特定轉乘次數之下實驗結果評估	48
4.7	圖形介面展示	51
第五章	結論與未來發展	58
參考文獻	59
附錄一	資料結構設計	60

圖目錄
圖1-1: 本論文研究流程圖	3
圖2-1: Dijkstra演算法採同心圓方式擴展節點示意圖	4
圖2-2: 直線A*演算法採橢圓方式擴展節點示意圖	6
圖2-3: 地標A*估算剩餘距離h(V,E)示意圖	6
圖3-1: 同位點設定示意圖，A、B兩同位點皆擁有鄰居X、Y、Z、T、U	13
圖3-2: 輸入路徑距離檢查示意圖，必需滿足直線距離line_dist<=路徑距離dist之幾何條件	13
圖3-3: 任兩有座標節點A、D其最短路徑A-B-C-D沿途預設路徑距離檢查示意圖	14
圖3-4: 前處理流程圖	15
圖3-5: 新增節點流程圖	16
圖3-6: 新增路線流程圖	18
圖3-7: 產生新地圖流程圖	19
圖3-8: 在同位點存在下，改良ALT估計剩餘距離法示意圖	20
圖3-9: ALT時間模式示意圖	24
圖3-10: 同位終點示意圖，左邊實線路線到達終點End_Node之同位點equivalent_node亦可視為可到達終點	26
圖3-11: 鄰居回溯判斷圖。A-B-C-D-E路徑中，由E擴展鄰居時，D、C不能再加入	29
圖3-12: 二維索引標籤演算法路徑狀態關係圖	29
圖3-13: 三維索引標籤演算法路徑狀態關係圖	32
圖3-14: 實例路網圖，包含有10個節點及10條不同的路線，三種演算法皆假設起點V1終點V6。	33
圖3-15: ㄧ維索引標籤距離成本演算法有序佇列變化狀況	34
圖3-16: 二維索引標籤時間成本演算法有序佇列變化狀況	35
圖3-17: 三維索引標籤距離成本演算法有序佇列變化狀況	36
圖3-18: 路線共線狀況圖	37
圖4-1: 地標A*演算法挑選地標位置圖	43
圖4-2: 距離成本、純含有座標節點地圖1000筆平均時間及平均效率結果比較圖	44
圖4-3: 距離成本、夾雜無座標節點地圖1000筆平均時間及平均效率結果比較圖	45
圖4-4: 時間成本、純含有座標節點地圖1000筆平均時間及平均效率結果比較圖	46
圖4-5: 時間成本、夾雜無座標節點地圖1000筆平均時間及平均效率結果比較圖	47
圖4-6: 時間及距離成本最短路徑規劃比較圖，起點三重，終點信義行政中心，轉乘站有台北車站和忠孝復興	47
圖4-7: 純含有座標節點地圖1000筆平均時間及平均效率結果比較圖	48
圖4-8: 夾雜無座標節點地圖1000筆平均時間及平均效率結果比較圖	49
圖4-9: 2次轉乘次數以下時間成本規劃結果，起點三重，終點信義行政中心	51
圖4-10: 圖形介面外觀	52
圖4-11: 圖形化系統介面讀取地圖初始	53
圖4-12: 圖形介面呈現最短路徑計算結果	54
圖4-13: 路徑計算結果簡圖(0次轉乘次數之下)	55
圖4-14: 路徑計算結果簡圖(1次轉乘次數之下)	56
圖4-15: 局部放大之路徑計算結果簡圖(1次轉乘次數之下)	56
圖4-16: 路徑計算結果簡圖(2次轉乘次數之下)	57

表目錄
表2-1: Dijkstra演算法，參考Hart等.[10]	4
表3-1: 預處理地圖表格記錄資訊總覽	9
表3-2: 路線可轉乘車站表<merge.txt>	9
表3-3: 路線不可轉乘車站表<no_merge.txt>	10
表3-4: 節點座標資訊表<nodexy.txt>	10
表3-5: 路線資料表格式<route_info.txt>	10
表3-6: 節點去向鄰居資訊總表<map.txt>及節點來向鄰居資訊總表<rmap.txt>	11
表3-7: 路線名稱資訊表<route_name.txt>	11
表3-8: 路線沿途節點及距離表<route.txt>	11
表3-9: 兩點預估之路徑距離使用直線距離加上參數調整對照表	17
表3-10: 不同準則下本文採用之演算法及路徑狀態索引標籤維度組合表	23
表3-11: 不計轉乘次數一維索引標籤最短路徑演算法	24
表3-12: 含轉乘時間二維索引標籤最短路徑演算法	27
表3-13: 三維索引標籤戴氏演算法	30
表3-14: 最短路徑結果實例表	37
表3-15: 最短路徑沿途可用路線表，標記V表可用路線	37
表3-16: 最短路徑沿途可用路線權重表(Ms,a)	38
表3-17: 最少轉乘路線最終挑選結果表	38
表3-18: 一維回溯路徑挑選路線演算法	39
表4-1: 本研究實驗環境	41
表4-2: 本研究採用之兩種地圖的基本資料表	41
表4-3: 本研究地標選用的節點	43
表4-4: 距離成本、純含有座標節點地圖1000筆平均時間及平均效率結果比較表	43
表4-5: 距離成本、夾雜無座標節點地圖1000筆平均時間及平均效率結果比較表	44
表4-6: 時間成本參數設定表:	45
表4-7: 時間成本、純含有座標節點地圖1000筆平均時間及平均效率結果比較表	46
表4-8: 時間成本、夾雜無座標節點地圖1000筆平均時間及平均效率結果比較表	46
表4-9: 純含有座標節點地圖1000筆平均時間及平均效率結果比較表	48
表4-10: 夾雜無座標節點地圖1000筆平均時間及平均效率結果比較表	49
表4-11: 三維索引標籤演算法時間成本模式參數表	49
表4-12: 時間成本最短模式之下選擇指定轉乘次數2次以下為例	49
表4-13: 圖形介面各種模式和準則組合採用之演算法	53
表5-1: 不同成本模式下時間和效率最佳演算法	58

[1]	鄭宇辰，利用高低層路網加快最短路徑計算之實作，淡江大學資訊管理研究所碩士論文(2008)。
[2]	謝逢鳴，有前處理最短路徑演算法之研究，淡江大學資訊管理研究所碩士論文(2006)。
[3]	何文基，整合時刻表之大眾運輸行前旅次規劃分析方法 ，中華大學運輸科技與物流管理學系碩士論文(2005)。
[4]	李思謙，軌道運輸系統行前旅次規劃問題之研究 ，國立成功大學交通管理(科學)學所碩士論文(1996)。
[5]	張存保，“基於WebGis的程式公交問路系統”，2003海峽兩岸智慧運輸系統學術研討會，pp 2-9~2-15(2004)。
[6]	台北市大眾運輸及公車路線查詢系統，http://www.taipeibus.taipei.gov.tw/。
[7]	E. W. Dijkstra,“A note on two problems in connection with graphs,” Numerische Mathematik, 1,  pp. 269-271,1959.
[8]	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.
[9]	A.V. Goldberg, H. Kaplan, and R. Werneck,“Reach for A*: efficient point-to-point shortest path algorithms,” Report MSR-TR-2005-132, Microsoft Research, October 2005.
[10]	P. E. Hart, N. J. Nilsson, B. Raphael,“A formal basis for the heuristic determination of minimum cost paths,”IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100-107,1968.
[11]	N.Koncz,J.Greenfield and K.Mouskos, “A strategy for solving static  multiple-optimal-path transit  network  problems,” Journal of Transportation Engineering, 122 (3), pp.218-225, 1996.
[12]	M. Thorup,“Integer priority queues with decrease key in constant time and the single source shortest paths problem,”Journal of Computer and System Sciences, 69 (3), pp.330-353, 2004.
[13]	Google Maps, http://maps.google.com.
[14]	UrMap, http://www.urmap.com/.