導航系統路徑的規劃與負載平衡

To achieve load-balance of Navigation System Routing

黃群崴(Chyun-Wei Huang)

指導教授 ： 柯仁松

國立中正大學/工學院/資訊工程學系/碩士(2013年)

摘要

隨著車輛的普及，近十年來車輛數的成長十分可觀，進而產生了交通壅塞的問題。交通壅塞不僅增加駕駛人的行車時間，也造成環境上的汙染與經濟上之耗費。為解決此一問題，過往發展出許多路徑規劃演算法，其多以路徑長度規劃出最短路徑，但最短路徑並非皆為最佳路徑，對駕駛人而言，時間花費最少之路徑，才會是最佳路徑，惟現行技術所規劃出之最短路徑上倘若有交通壅塞或事故發生，則將使行車時間不減反增。此外，現行技術所規劃出之路徑一旦規劃即無法再做更改，但道路之情形是隨時在變動的，若無法隨時更新，則可能使駕駛人選擇了交通壅塞的道路，最終使所有駕駛人陷於車陣中。因此，本論文之重點為以動態重新規劃路徑之方式，找出行駛時間較短之路徑。
而在本論文中，也介紹了目前道路交通模擬器之模型，分別為宏觀模型、中觀模型、微觀模型和亞微觀模型，而此次研究中，所採用的模擬器為微觀模型為主的城市交通模擬器SUMO。一般而言，在模擬器將所有的路徑或是交通號誌時間模擬完成後，就無法再做修改，但透過交通控制介面TraCI連結我們的程式，將可使車輛於行駛途中變換路徑。因此，我們可以模擬本篇論文所提出之方法，當塞車時依據路幅較大、速限較高之道路等方式來重新規劃路徑，而實驗數據也顯示出重新規劃路徑之方法，比現行技術之方法節省了約30%之旅途時間。

關鍵字

動態路徑規劃 ； 道路交通模擬器 ； 最佳路徑 ； 交通控制介面

並列摘要

With the popularity of vehicle, the amount of vehicle has large growth and also leads to the traffic congestion. Traffic congestion not only wastes drivers' time but also make the environment pollution and economy cost. In order to solve the problem, there were lots routing algorithms which plan the shortest path by the length of path trying to find the best path for drivers. However, the best path for drivers is the one which they can spend the least time. If the routing algorithm just considers the length of path, it would ignore the reality condition like the car accidents and traffic congestion. In addition, the path planned by routing algorithm in today can't re-route when there are accidents; consequently, all drivers might be in the traffic congestion. Therefore, the key point of this paper is using the dynamic rerouting to find the path which can spend the drivers' time least.
We also have introduced the current model of road traffic simulator in this paper, macroeconomic model, meso model, microscopic model and submicroscopic model respectively, and the simulator named Simulation of Urban Mobility (SUMO) that we using is microscopic in this study. In general, after the simulator have simulated all the paths or traffic signals, we can’t modify anymore, but through the Traffic Control Interface (TraCI) to connect our program, the vehicle could be to change routes as travel. Therefore we can simulate the proposed methods. When traffic congestions are happening, we’ll base on the larger roads and the higher limit speed to re-route path. And the simulation results compared to the technology nowadays has shown our method saved about 30% of the travel time finally.

並列關鍵字

Dynamic routing ； Road traffic simulator ； The best route ； Traffic Control Interface

參考文獻

[15] Vi Tran Ngoc Nha, Soufiene Djahel and John Murphy, “A comparative study of vehicles' routing algorithms for route planning in smart cities,” 於 Vehicular Traffic Management for Smart Cities (VTM), Dublin, 2012.

[1] VICS, “http://www.vics.or.jp/index1.html,” [線上].

[2] 台北市政府交通局, “http://www.dot.taipei.gov.tw/,” [線上].

[3] SUMO, “http://sumo.sourceforge.net/,” [線上].

[4] Sheng-hai An, Byung-Hyug Lee, Dong-Ryeol Shin, “A Survey of Intelligent Transportation Systems,” Third International Conference on Computational Intelligence, Communication Systems and Networks, 2011.