碩士 / 淡江大學 / 資訊管理學系碩士班 / 98 / 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.
| Identifer | oai:union.ndltd.org:TW/098TKU05396009 |
| Date | January 2010 |
| Creators | Chung-Lin Huang, 黃仲麟 |
| Contributors | Shih-Chieh Wei, 魏世杰 |
| Source Sets | National Digital Library of Theses and Dissertations in Taiwan |
| Language | zh-TW |
| Detected Language | English |
| Type | 學位論文 ; thesis |
| Format | 62 |
Page generated in 0.1553 seconds