- 學位論文
探討動態導航中如何有效率的提供即時最佳路徑服務
A Study on Efficiently Providing the Dynamic Shortest Path Service in Navigation Systems
摘要
大多數目前的車用導航系統已具備有接收即時路況的通訊技術與動態導航的計算能力，動態導航是能夠考慮交道路況來規劃最佳行駛路線。導航軟體可以藉由行車前的運算，依據駕駛者之出發地點與目的地、交通路況以及駕駛偏好等規劃出行駛路線(最短路徑)，但實際上往往因為交通路況會隨著時間不斷地改變，使得駕駛人必須重新調整行駛路線。本篇論文將動態導航方式分為兩種，一種是像過去相關研究的文獻所介紹之重新計算路徑的方式；另一種是維護路徑的方式。前者在接受查詢時，依當下的交通路況，即時搜尋出一條新的路徑，每一次重新計算行駛路線都將耗費時間與系統資源；後者在交通路況改變時，馬上調整現有的所有路徑，而在接受查詢時，可以立即回覆被維護的路徑。本篇論文考量第二種方式，研究當道路狀況改變時，如何對指定的路徑進行維護以保持最佳路徑。提出的方法將有效地利用外部記憶體(external memory)來存放道路資料與其他輔助資訊，並在進行維護時，只要載入需要的部份道路資料即可對指定的路徑進行調整。最後，透過實驗驗證所提出的方法完成更新所花的時間及I/O次數上的效能。
參考文獻
[37] 謝耘東, 在資料廣播環境中進行最短路徑查詢之研究, 碩士論文, 國立台北科技大學資訊工程系碩士班, 2008.
[2] S. Chaudhuri and C. D. Zaroliagis, “Shortest path queries in digraph of small treewidth,” In International Colloquium on Automata, Languages, and Programming, pages 244-255. Lect. Notes in Comp. Sci., 944, 1995.
[3] G. Ausiello, G. F. Italiano, A. Marchetti-Spaccamela, and U. Nanni, “Incremental algorithms for minimal length paths,” Journal of Algorithms, 12(4):615-638,1991.
[4] P. G. Franciosa, D. Frigioni, and R. Giaccio, “Semi-dynamic shortest paths and breadth-first search on digraphs,” In Symposium on Theoretical Aspects of Computer Science, pages 33-46. Lect. Notes in Comp. Sci, 1200, 1997
[5] R. K. Ahuia, K. Mehlhorn, J. B. Orlin, and R. E. Tarjan, “Faster algorithms for the shortest paths problem,” Journal of the ACM, 37(2):213-233, 1990.