摘要
科技進步日新月異，近年來各式各類的嵌入式產品更是爭奇鬥艷。其中以擁有全球定位系統(Global Positioning System, GPS)及導航功能之可攜式導航裝置(Portable Navigation Device, PND)最為熱門。在市面上提供導航規劃路徑商品的公司，像是PAPAGO、TomTom、 Garmin，其規劃路線的主要特色多以距離最短的路徑作為規劃重點。然而，在實際道路行駛上不單單只有距離會影響車輛行駛的成本，還要考慮到實際的行車速度、具有綠燈波的路段、車輛轉彎的次數與方向、路面坡度高低都會影響行車時間與油耗之多寡。因此，最短路徑規劃和快速道路規劃的結果不一定是一條實用的最快速與最經濟路徑。在本文中提出了兩個結合最短距離、轉彎次數、路面坡度、綠燈坡路段與即時交通資訊之實用的最快速與實用的最經濟路徑演算法。利用此兩個演算法，發展出在可攜式導航裝置上執行之實際終端應用，並將其實作於搭載Android系統HTC Magic智慧型手機(Smartphone)。
並列摘要
Nowadays, Portable Navigation Devices (PND) with Global Positioning System (GPS) and navigation functions become very popular in the market in the recent years, such as PAPAGO, TomTom, Garmin. Technically, the path length, traffic congestion and number of turns are the major factors in path planning of transportation and navigation systems. Meanwhile, the shortest path planning has been widely studied in the literatures. Unfortunately, most researches only take the issue of shortest distance into account, and the impact of turns, green wave section, traffic congestion and gradient are rarely mentioned, that is the shortest path may not be the fastest. Considering all three factors in a path-searching algorithm is complicated. This proposal addresses two algorithms: the Fastest Practical and the Most Economical Practical Path-planning to balance the path length, traffic congestion, gradient and turns. The Kirby’s concept and a modified Dijkstra’s algorithm are applied to those proposed algorithms on a transportation network. The time complexities for the Fastest and the Most Economical Path-planning algorithms are O(√NlogC), where N is the intersections on a transportation network.