資料探勘應用於導航系統的多重路徑規劃

Abstract

目前於多重路徑規劃(multi-path planning)的研究中，替代道路的搜尋是非常普遍應用的。在真實的路網中，駕駛者印象中的最短路徑往往容易造成塞車的現象。而現有的衛星導航可以提供一條正確到達目的地的路徑規劃，卻沒有辦法告知駕駛者如何避開車。 本論文目的為建置一個在真實路網上的車輛路徑規劃系統，接著以資料探勘(data mining)的FP-growth建構車流量資料庫和平均速度，再以每一區段時間紀錄不同時段的動態車況，在考量時間的情況下，可以清楚知道旅行時間的車流變化。然後使用關聯法則(association rule)中過高的信心度(confidence)路段視為塞車區域。再建立一條代克斯托演算法(Dijkstra’s algorithm)所選擇的最短路徑，配合螞蟻族群演算法(ant colony optimization)放射性的搜尋路徑，用以產生在最短距離附近的替代道路集合，根據虛擬螞蟻的行進路徑產生費洛蒙(pheromone)，而在關聯法則中所得知過高的信心度，也會對費洛蒙值產生抑制的動作。最後，依費洛蒙的強度決定一條替代道路，以達到最快速到達目的地的需求。以現有的路網地圖為例測試本系統達成控制目標與學習的功能。由模擬結果得知，本論文所提出演算法可以達到不錯的導航系統。

Recently, scanning of candidate paths is widely applied in the research of multi-path planning. In the real road network, traffic-jam happened usually in this situation which drivers make a impression on the shortest path based on short distance. At present, a correct path from start point to destination is product by GPS, but drivers don’t know how to avoid traffic-jam. In this paper, a modified algorithm is proposed and it has been applied onto a real road network. The database of car flow is build by using the technique of data mining, FP-growth. The traffic condition in different time segments is recorded and high confidence product by association rule is regarded as traffic-jam regions. Then, candidate path sets are gathered by ant colony optimization, candidate path sets are based on the shortest path which is product by Dijkstra’s algorithm. Pheromone is product by the paths which virtual ants have tracked. The high confidence product by association rule restrains the increase of pheromone. Finally, a candidate path is decided by the quantity of pheromone. The aim of attending the destination quickly has accomplished. The road networks are used as examples to test learning ability and controllability of the proposed system. The experimental results show the navigation system is satisfactory.