大眾運輸系統最短路徑之研究

機構典藏 > College of Business and Management > Graduate Institute & Department of Information Management > Thesis > Item 987654321/52129

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/52129

Title:	大眾運輸系統最短路徑之研究
Other Titles:	Finding the shortest path for the public transportation systems
Authors:	黃仲麟;Huang, Chung-lin
Contributors:	淡江大學資訊管理學系碩士班魏世杰;Wei, Shih-chieh
Keywords:	大眾運輸路網;路徑狀態多維度索引標籤擴充法;Dijkstra演算法;直線A演算法;有向地標A演算法;Public Transportation System;Multi-Dimensional Label Extension For Route Indexing;Dijkstra Algorithm;Straight-Line A* Algorithm;Landmark A* Algorithm
Date:	2010
Issue Date:	2010-09-23 16:52:06 (UTC+8)
Abstract:	點到點之間的最短路徑問題是近年普遍研究及關注的焦點，也常應用於地理資訊系統(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.
Appears in Collections:	[Graduate Institute & Department of Information Management] Thesis

Files in This Item:

File	Size	Format
index.html	0Kb	HTML	305	View/Open

Loading...