建構智慧型手機上路徑規劃之通用模型

導航裝置是嵌入式系統及交通運輸科技中熱門的產品，目前在市場上提供此類商品的有PAPAGO、TomTom、Garmin與Mio等。Ford汽車在2011年式Edge車款上也搭載MyFord Touch系統。但現今的導航系統規劃路徑，大多只考慮最短的距離作為路徑規劃的重點，且多採用純向量式結構，一旦遇到需要表現出複雜的道路狀況，往往得將向量擴充成複雜的資料結構，導致更多的節點與計算時間，此外此複雜之資料結構會因其他交通因素更加複雜化，而無法如我們的混合型資料結構保持固定空間與時間複雜度。如以下幾點常見的路徑規畫需求: (1)車輛在行進的過程中，每逢轉彎地方必定減速導致延長到達目的地的時間。(2)目的地在對向車道以及迴轉之相關問題。(3)每段道路的行車速度及綠燈波，影響實際可行進的速度。(4)道路停止標誌而影響到行車速率或是行車狀況。(5)同路段高架橋與平面路段造成導航系統的誤判。(6)道路寬度影響不同車體是否能夠通行。(7)道路收費站影響的行車成本。(8)行車時排放的廢氣影響的社會環境成本。(9)隨時隨地將導航裝置安置於任何車體上的便利性。本文提出了包含轉彎成本、即時的道路情況、道路寬度、收費成本、坡度及考量環境成本之最佳實際路徑規劃演算法通用模型，並採用混合式的地圖資料結構(hybrid data structure)，在現今不斷複雜化的道路及使用者需求之下，將時間與空間複雜度保持在一定的成本。並將此模型實作在iOS與Android平台。

關鍵字

可攜式導航裝置；最佳實際路徑規劃演算法通用模型；智慧型手機

並列摘要

Recently Portable Navigation Devices (PND) with Global Positioning System (GPS) and navigation functions under Android and iOS become very popular in the market, such as PAPAGO, TomTom, Garmin. The shortest path planning of transportation and navigation systems 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, Stop signs, bands of roads, viaduct, gradient and environment are rarely mentioned, that is the shortest path may not be the fastest. Considering all the factors in a path-searching algorithm is complicated. Our recent papers have addressed two algorithms: the fastest practical and the most economical path-planning to balance the path length, traffic congestion, gradient, turns etc. Meanwhile, the Kirby’s concept and a modified Dijkstra’s algorithm are applied to the above algorithms on the streets of metropolitan. The time complexities for the fastest and the most economical path-planning algorithms are , where N is the number of raster cells on a transportation network and C is the maximum weight of links. This paper takes more issues into account, such as U-turns, green wave section, Stop signs, bands of roads, viaduct and environment under Android and iOS. A universal model is constructed based on all the mentioned issues and this model can be applied to obtain all the required algorithms, such as the shortest or faster routes planning, for different purposes with combinations of issues. The space and time complexities of the above combinations.

並列關鍵字

Android ； Dijkstra algorithm ； universal model for route planning

參考文獻

[4] P. Brosch, “A Service Oriented Approach to Traffic Dependent Navigation Systems,” IEEE Congress on Services,Part I, pp. 269-272, 2008.

[6] F. Lu, Y. Duan and N. Zheng, “A practical route guidance approach based on historical and real-time traffic effects,” 17th International Conference on Geo informatics, pp. 1-6, 2009.

[7] Gene Eu Jan, Ki-Yin Chang, Su Gao and Ian Parberry, “A 4-Geometry Maze Routing Algorithm and Its Application on Multi-Terminal Nets,” ACM Trans. on Design Automation of Electronic Systems, Vol. 10, No. 1, pp.116-135, 2005.

[8] Gene Eu Jan, S. H. Hsieh and S. W. Leu, “二維格狀運輸網路中具有轉彎加權之最佳路徑規劃,” 2003 National Computer Symposium, Fong Chia Univ., Tai Chung, Taiwan, OT-05, Dec. 2003.

[11] Gene Eu Jan, Ki-Yin Chang and Ian Parberry, “Optimal Path Planning for Mobile Robot Navigation,” IEEE/ASME Transaction on Mechatronics, Vol. 14, No. 9, pp. 925- 936, Aug. 2008.

國際替代計量

建構智慧型手機上路徑規劃之通用模型

未授權

主題瀏覽