請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5987完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 張堂賢(Tang-Hsien Chang) | |
| dc.contributor.author | Bor-Chia Hsieh | en |
| dc.contributor.author | 謝伯嘉 | zh_TW |
| dc.date.accessioned | 2021-05-16T16:19:05Z | - |
| dc.date.available | 2013-08-17 | |
| dc.date.available | 2021-05-16T16:19:05Z | - |
| dc.date.copyright | 2013-08-17 | |
| dc.date.issued | 2013 | |
| dc.date.submitted | 2013-08-13 | |
| dc.identifier.citation | [1] Cherkassky, B.V., A.V. Goldberg, and T. Radzik. (1996). Shortest paths algorithms: Theory and experimental evaluation. Mathematical Programming, 129-174.
[2] 任維廉, 涂榮庭, 呂明穎, 呂堂榮. (2009). 探討先進旅行者資訊系統相關商品的知覺風險. 中華民國運輸學會. [3] 交通部運輸研究所. (2001). 台灣地區發展智慧型運輸系統 (ITS) 系統架構之研究 (Ⅰ). 交通部運輸研究所. [4] Smith, J.C. and K. Russam. (1989). Some possible effects of AUTOGUIDE on traffic in London. IEEE International Conference on Vehicle Navigation and Information Systems. Toronto, Canada. [5] French, B. and C. Queree. (1991). The intelligent highway. RTI/IVHS News. London. [6] Boyce, D.E., A.M. Kirson, and J.L. Schofer. (1994). Design and implementation of ADVANCE：The Illinois dynamic navigation and route guidance demonstration program. IEEE International Conference on Vehicle Navigation and Information Systems. Ottawa, Canada. [7] Klunder, G.A. and H.N. Post. (2006). The shortest path problem on large-scale real-road networks. NETWORKS, 182-194. [8] Pallottino S., and Scutella M. G. (1998). Shortest path algorithms in transportation models: classical and innovative aspects, Equilibrium and Advanced Transportation Modeling. [9] Lawler, E. L. (1976), Combinatorial Optimization: Networks and Matroids. Holt, New York : Rinehart and Winston.Lewis, C. D. (1982), Industrial and Business Forecasting Method, Southampton: The Camelot Press Ltd. [10] Gallo, G., and Pallottino, S. (1986), “Shortest Path Methods: An Unifying Approach”, Mathematical Programming Study, Vol. 26, pp. 38-64. [11] Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 269-271. [12] Bellman, R. (1958). On a routing problem. Quart. Appl. Mathematics, 87-90. [13] Kershenbaum, A. (1981), “A note on finding shortest path trees,” Networks, Vol. 11, No.1, pp. 399-400. [14] Gallo, G. (1980), “Reoptimization procedures in shortest path problems”, Rivista di Matematica per le Scienze Economiche e Sociali, Vol. 3, No.1, pp. 3-13. [15] Dreyfus, S.E. (1969). An appraisal of some shortest path algorithms. Operations Research, 395-412. [16] Ziliaskopoulos, A. K., and Mahmassani, H. S. (1993), “Time-dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications,” Transportation Research Record, No. 1408, pp. 94-100. [17] Desrochers, M., and Soumis, F. (1988), “A generalized permanent labelling algorithm for the shortest path problem with time windows”, INFOR, Vol. 26, No. 3, pp. 191-212. [18] Kirby, R. F., and Potts, R. B. (1969), “The minimum route problem for networks with turn penalties and prohibitions,” Transportation Research, Vol. 3, pp. 397-408. [19] Ziliaskopoulos, A. K., and Mahmassani, H. S. (1996), “A Note on Least Time Path Computation Considering Delays and Prohibitions for Intersection Movements”, Transportation Research Part B, Vol. 30, No. 5, pp. 359-367. [20] Hansen, P. (1980), Bicriterion path problems, In Fandel, G., and Gal, T. (Eds.), Multicriteria decision making: theory and applications, Heidelberg :Springer, pp. 109-127. [21] Jacob, R., M.V. Marathe, and K. Nagel. (1998). A computational study of routing algorithms for realistic transportation networks. Proceedings WAE'98 Saarbrucke, (頁 167-17). Germany. [22] Cordeau, J.F., et al. (2002). A guide to vehicle routing heuristics. The Journal of the Operational Research Society, 頁 512-522. [23] Chabini, I. (1997). A new short paths algorithm for discrete dynamic networks. Proceedings of 8th IFAC Symposium on Transportation Systems. Chania, Greece. [24] Chabini, I. (1998). Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time. Transportation Research Records, 170-175. [25] Cooke, K.L. and E. Halsey. (1966). The shortest route through a network with time dependent intermodal transit time. Journal of Math. Anal. Appl., 492-498. [26] Bellman, R., On a routing problem. Quart. Appl. Mathematics, 1958. 16: p. 87-90. [27] Sturtevant, N. and Buro, M. (2005). Partial pathfinding using map abstraction and refinement. ceedings of AAAI, 47-52. [28] Daganzo, C.F. (2002). Reversibility of the time-dependent shortest path problem. Transportation Research Part B, 665-668. [29] Ahuja, R.K., T.L. Magnanti, and J.B. Orlin. (1993). Network flows: Theory, algorithms, and applications. Englewood Cliffs, NY.: Prentice-Hall. [30] Bertsekas, D.P. (1991). Linear network optimization: Algorithms and codes. Cambridge, MA: The MIT Press. [31] Denardo, E.V. and B.L. Fox. (1979). Shortest-route methods: 1. Reaching, pruning, and buckets. 於 Operations Research (頁 161-186). [32] Denardo, E.V. and B.L. Fox. (1979). Shortest-route methods: 2. Group knapsacks, expanded networks, and branch-and-bound. 於 Operations Research (頁 548-566). [33] Deo, N. and C. Pang. (1984). Shortest path algorithms: Taxonomy and annotation. Networks, 275-323. [34] Gallo, G. and S. Pallottino. (1984). Shortest path methods in transportation models. 於 Transportation Planning Models (M. Florian, ed.) (頁 227-256). [35] Gallo, G. and S. Pallottino. (1988). Shortest path algorithms. Annals of Operational Research, 3-79. [36] Halpern, J. and I. Priess. (1974). Shortest path with time constraints on movement and parking. Networks, 241-253. [37] Johnson, D.B. (1973). Algorithms for shortest paths. NY: Cornell Univ.: Ithaca. [38] Orda, A. and R. Rom. (1990). Shortest path and minimum-delay algorithms in network with time-dependent edge length. Journal of the ACM, 607-625. [39] Shier, D.R. and C. Witzgall. (1981). Properties of labeling methods for determining shortest path trees. 於 Journal of Research of the National Bureau of Standards (頁 317-330). [40] SteenbrinkP.A. (1974). Optimization of transport networks. London: John Wiley & Sons. [41] Van Vliet, D. (1978). Improved shortest path algorithms for transport networks. Transportation Research, 7-20. [42] 張堂賢、闕嘉宏. (2012). 依時性後推式路徑演算系統開發. 運輸學刊. [43] 葉羿稚. (2007). 行前即時路徑規劃演算法之研究. 台灣大學土木工程學系碩士論文. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5987 | - |
| dc.description.abstract | 「條條大路通羅馬」，交通運輸的快速發展，使得我們要前往目的地，時常都有許多選擇，然而因為有許多不同的選擇，該如何選擇就變成了另一個困擾。市面上有許多路徑導引程式，不論「行前路徑導引」或「途中路徑導引」，多以空間最短路徑為決策目標，然而實際使用的時候，卻時常發現導引程式提供的最佳路徑車多雍塞。
為解決傳統路徑導引程式往往僅依照空間距離做為路徑導引決策的變數，未考慮實際交通路況的問題，本研究使用路段旅行時間做為路徑選擇的成本，建置一適用於國道高速公路路網的依時性A*路徑演算系統。以A* Algorithm做為路徑演算的基礎，將整合車輛偵測器(VD)與電子收費系統(ETC)資料的旅行時間資料庫做為依時性演算法之資料來源，並加入後推式演算法以配合不同使用者的需求。使用者輸入起點、訖點以及預計出發/抵達時間，系統就會根據旅行時間資料庫提供的路段旅行資料，提供建議旅行路徑與總旅行時間。 本研究驗證A* Algorithm能夠有效限制路徑搜尋的方向，以較短的時間取得令人滿意的建議路徑，這在路網龐大複雜時，能夠有效縮短運算時間，節省運算資源。本研究同時驗證，後推式演算法雖然需要較長的演算時間，但是演算結果與前推式演算法一致，能夠節省使用者欲於特定時間抵達目的地而反覆求解的時間。 | zh_TW |
| dc.description.abstract | “All roads lead to Rome.” Because of the developing of transportation, we usually have a lot of way that we can pick to reach a destination. With the choices increasing, which way should we choose become another problem. There are kinds of route guidance program in the market. Whatever “pre-trip route guiding” or “en-route route guiding,” most of them use the length of path to make a decision. However we can usually found out that the route it provides always in a traffic jam.
To solve the problem that traditional route guidance programs usually pick out the shortest route but not the best route, this study replaces the spacing cost with traveling-time cost to build a time-dependent A* route planning system which can match highway characteristic. This program based on A* Algorithm and uses VD and ETC data as data sources. It also contain time-dependent backward algorithm to fit different travel planning demands. Users just input origin, destination, and expectation departure/arrival time, system will output recommend route and total traveling time. This study verify that A* Algorithm can limit route-searching direction to find a satisfactory route within a short time. While the road network coming huge and complex, it can efficaciously saving calculating time. This study also verify that backward algorithm get the same result as forward algorithm, though backward algorithm take more time to solve the problem. | en |
| dc.description.provenance | Made available in DSpace on 2021-05-16T16:19:05Z (GMT). No. of bitstreams: 1 ntu-102-R00521506-1.pdf: 7323268 bytes, checksum: 47b72eb4129ebd4423f26dd85755c461 (MD5) Previous issue date: 2013 | en |
| dc.description.tableofcontents | 第一章 緒論 1
1.1 研究背景與動機 1 1.2 研究目的 2 1.3 研究範圍 2 1.4 研究內容與流程 3 第二章 文獻回顧 5 2.1 智慧型運輸系統(ITS) 5 2.1.1 先進旅行者資訊系統(ATIS) 6 2.1.2 行前資訊系統 6 2.1.3 旅行者資訊系統的效益 7 2.2 路徑規劃類型 8 2.3 最短路徑問題(Shortest Path Problem) 12 2.3.1 路網結構資料 12 2.3.2 路網基本定義 13 2.3.3 最短路徑問題 14 2.4 Dijkstra’s Algorithm與A* Algorithm 19 2.4.1 Dijkstra’s Algorithm 19 2.4.2 Dijkstra’s Algorithm範例 22 2.4.3 Dijkstra’s Algorithm評析 24 2.4.4 A* Algorithm 24 2.5 依時性最短路徑問題 25 2.5.1 依時性最短路徑問題 25 2.5.2 依時性最短路徑演算法 27 2.5.3 依時性前推式最短路徑演算法 27 2.6 小結 28 第三章 研究方法 30 3.1 依時性資料庫與資料融合 30 3.2 A* Algorithm 32 3.2.1 A* Algorithm運作原理 32 3.2.2 A* Algorithm參數設計 35 3.3 前(後)推式路徑演算法原理及證明過程 36 3.4 時間連續性與時間間隙問題 38 3.5 小結 43 第四章 系統建構 45 4.1 系統架構與運作邏輯 45 4.2 系統建置 47 4.2.1 使用者介面 47 4.2.2 建立路網節點資料 47 4.2.3 資料儲存結構 48 4.3 路徑演算模組 50 4.3.1 前推式路徑演算流程 51 4.3.2 後推式路徑演算流程 52 4.3.3 建議路徑輸出方式 54 4.4 相關子程式 55 4.4.1 標準時間轉換 55 4.4.2 候選路段集合 56 第五章 路徑規劃實作 57 5.1 實驗範圍 57 5.2 路網節點相關資料 58 5.3 系統實作案例測試 65 5.3.1 旅行路徑經過一個以下系統交流道 66 5.3.2 旅行路徑經過兩個以上系統交流道 68 5.4 後推式演算法實作測試 70 5.4.1 旅行路徑經過一個系統交流道 71 5.4.2 旅行路徑經過兩個系統交流道 72 第六章 結論與建議 76 6.1 結論 76 6.2 建議 77 參考文獻 79 附錄 84 | |
| dc.language.iso | zh-TW | |
| dc.title | 依時性A*路徑演算系統開發－以國道高速公路路網為例 | zh_TW |
| dc.title | Development of Time-Dependent A* Route Planning System: A Case Study of Taiwan Highway System | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 101-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陶治中,黃文鑑 | |
| dc.subject.keyword | 依時性最短路徑問題,Dijkstra’s Algorithm,A* Algorithm,後推式路徑演算法,路徑導引系統, | zh_TW |
| dc.subject.keyword | the time-dependent shortest path problem,Dijkstra’s Algorithm,A* Algorithm,the backward route algorithm,route guidance system, | en |
| dc.relation.page | 108 | |
| dc.rights.note | 同意授權(全球公開) | |
| dc.date.accepted | 2013-08-13 | |
| dc.contributor.author-college | 工學院 | zh_TW |
| dc.contributor.author-dept | 土木工程學研究所 | zh_TW |
| 顯示於系所單位： | 土木工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-102-1.pdf | 7.15 MB | Adobe PDF | 檢視/開啟 |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。