自適應代價函數(shù)的GPS路線決策研究

李中華，楊 進，倪明濤,王 慧

(1.樂山師范學院 智能信息處理及應用實驗室，四川 樂山 614000；2.樂山師范學院 數(shù)信學院，四川 樂山 614000)

0 引 言

GPS是全球定位系統(tǒng)(Global Positioning System)的簡稱，利用導航衛(wèi)星進行檢測和數(shù)據(jù)交換[1-2]。GPS目前得到廣泛應用，如航海，航空和道路運輸?shù)取Ｆ渲械缆愤\輸最普遍，也即為車載GPS。

隨著中國經(jīng)濟的發(fā)展，道路建設得到快速發(fā)展，同時人們對車輛的擁有量也在大幅度增加。從而導致城市交通擁堵，影響上班和出行，造成交通事故。因此，準確掌握道路交通狀況，根據(jù)個人需求選擇有效路徑成為關鍵。然而，傳統(tǒng)的路徑規(guī)劃方法和代價函數(shù)都很簡單。文獻[3-5]分別提出了采用蟻群算法優(yōu)化路徑的方法，考慮了通行時間、路徑距離和路況信息，基于多參數(shù)優(yōu)化理論進行尋優(yōu)；姜鈺梁，等[6]對GPS動態(tài)數(shù)據(jù)進行了分析，提出了有效避免干擾的動態(tài)數(shù)據(jù)提取算法；孫文彬，等[7]主要針對單源單匯網(wǎng)絡提出了一種最短路徑搜索的并行算法；文獻[8-12]分別就路徑優(yōu)化的某單一領域進行了研究。

這些學者盡管對GPS路徑優(yōu)化進行了研究，但對目前復雜的GPS路徑優(yōu)化，僅考慮單一因素以及將道路狀況簡單化描述，或者固定代價目標等都是不夠的。而且，不能實現(xiàn)由用戶隨時定制GPS路徑?jīng)Q策的代價函數(shù)，從而在實際應用中缺乏靈活性。隨著道路復雜度增加，影響到達目的地的因素也非常多。如何通過算法來根據(jù)需求對代價函數(shù)實現(xiàn)自適應調整，從而求解相應的最佳路徑，是筆者的主要研究目標。

筆者將所有影響交通運行的道路狀況指標，如路程，道路等級，堵車概率，臨時通車政策，節(jié)假日通車情況，堵車時段等考慮為路況集，由這些集合的綜合指標構成道路的網(wǎng)絡邊權，然后根據(jù)用戶的目標函數(shù)采用路徑尋優(yōu)算法確定最佳路徑。

1 GPS路線決策數(shù)學模型

1.1 GPS終端對電子地圖路況分析

城市道路路況對車輛的行車消耗是不同的，不同條件將產(chǎn)生不同的結果。算法的目的就是根據(jù)用戶最關心的目標內容，由GPS終端對每個路徑進行分析，找出影響用戶關心的目標函數(shù)最小的路徑，稱為最優(yōu)路徑。

定義1：假設描述一段路況的參數(shù)為G={g1，g2，…，gn}，其中：g1為路程；g2為道路等級；g3為交通擁擠率；g4為交通擁擠量；g5為假日交通狀況；g6為交通禁令；…。

為得到線路對用戶需求代價函數(shù)影響的綜合指數(shù)，采用權重求和方式，算法如下。

假設權重向量P=[P1，P2，…，Pn]；線路綜合路況指標為r，則：

r(i，j)=P×G=[P1g1+P2g2+…+Pngn]

(1)

式中：r(i，j)表示i，j間直接連接線路的路況綜合指標；n為G中所包含元素個數(shù)；Pi∈[0，5]根據(jù)gi對代價函數(shù)的影響大小來確定；gi是根據(jù)路況條件對代價函數(shù)的影響將其轉換成距離的兌換因子。

所以式(1)可以改寫為：

r(i，j)=P×G=[g1+P2g2+…+Pngn]

(2)

由式(2)可知，r(i，j)實際上是考慮了其它路況等信息后得到的綜合線路長度，其值是≥g1的。根據(jù)定義1，確定各路況信息的兌換因子數(shù)，如式(3)：

(3)

當?shù)缆反嬖诮煌ń箷r或只能逆行時，g6=1；這時對應的P6=∞。

1.2 GPS終端最優(yōu)路徑計算

根據(jù)用戶各個具體條件下對目標指數(shù)的要求不同，自適應調整代價函數(shù)。

用戶代價函數(shù)集J={Jt，Jf，…}

(4)

式中：T[i,k]為i,k兩點間的消耗時間；F[i,k]為i,k兩點間的消耗費用；Jt(i，j)為i，j兩點間的消耗時間；Jf(i，j)為i，j兩點間的消耗費用；i為起始地；j為目的地；N為節(jié)點集。

當i，k之間出現(xiàn)禁止通行和逆行等臨時交通規(guī)定或沒有直接連接時，T[i,k]和F[i,k]等目標函數(shù)值為∞，但是為迭代能統(tǒng)一進行和保證計算的收斂性，可以將此時的T[i,k]和F[i,k]值取為遠遠大于其余路線的消耗值，如取1 000等。最具有代表性的算法就是DIJKSTRA，該算法主要用于解決圖論中最優(yōu)路徑求解問題。對于GPS路徑優(yōu)化問題，只要將影響行車的路況條件數(shù)學模型建立起來，就是路徑優(yōu)化問題，采用DIJKSTRA算法是最有效的。

算法原理如下：假設網(wǎng)絡中總節(jié)點數(shù)為N；計算節(jié)點集為Q；P0為路徑計算時的初始節(jié)點；d(i，j)為節(jié)點i和j之間的距離；S(P)為源節(jié)點到P節(jié)點間最短距離；最初Q=[P0]。進行如下步驟：

步驟1: 讀取各段線路的路況化模型參數(shù)，根據(jù)下式進行計算最短路徑。

(5)

步驟2: 在N集中新增一個點，根據(jù)式(6)計算最短路徑。

(6)

重復第2步，直到Q=N，結束。

2 仿真實驗

假設有的城市道路交通拓撲圖，如圖1。

圖1 城市道路網(wǎng)絡Fig.1 City road network

圖1中每個節(jié)點代表一個地點或道路岔口，兩點之間的連線代表道路，道路的綜合狀況用邊權描述。根據(jù)用戶不同的代價函數(shù)要求，邊權的含義不一樣。如果用戶要求兩點之間所耗時間最短，則系統(tǒng)自動將道路狀況轉換為時間。如果用戶要求兩點之間油耗最少，則系統(tǒng)自動將各道路的狀況轉換為標準油耗指標作為邊權，等等。

條件：假設道路狀況信息如表1。道路的權重為[1,0.5,1,2,0.8,1]，根據(jù)圖2的仿真計算結果，假設要從1節(jié)點到9節(jié)點，要求所消耗時間最少，則GPS自動確定的路徑是：1→2→4→9。

表1 網(wǎng)絡中各道路路況信息Table 1 Conditions of roads

(續(xù)表1)

g1g2g3g4g5g610．84800．61310．91530．2490010．08160．75190．64150．5902010．13990．16260．66130．3607010．28730．77300．01350．7196010．82800．77150．86360．3356010．55480．85460．18810．4780010．32040．54270．26470．2238010．77970．59430．18120．4244010．87740．26310．53970．6218110．57080．49570．51860．0913010．55950．99140．70090．1492010．71070．13460．78460．1495010．33210．33070．25550．0888010．93770．01510．91510．67800

圖2代價函數(shù)J最小的路徑
Fig.2ThesmallestrouteofcostfunctionJ

3 結 語

筆者將城市道路路況信息按照用戶定義的目標不同轉換成等價的路線長度指標，然后用道路長度指標作為拓撲圖的邊權，采用圖論中最有效的求最優(yōu)路徑的方法求出滿足用戶要求的最優(yōu)路徑。該最優(yōu)路徑就是GPS導航儀指示的行車路線。經(jīng)對14節(jié)點的道路系統(tǒng)進行仿真，得出了各對節(jié)點間的最優(yōu)路線，仿真結果證明該方法是有效的。

[1] 朱玉璽,崔如春,黃峻藝.“GPS最短路徑”搜索研究與實施[J].計算機工程與設計,2005,26(9):2437-2438.

Zhu Yuxi,Cui Ruchun,Huang Junyi.“GPS shortest path”search study and pratice[J].Computer Engineering and Design,2005,26(9):2437- 2438.

[2] 范曉燕,周乾.GPS測量中多路徑效應研究綜述[J].工程地球物理學報,2010,7(3):382-387.

Fan Xiaoyan,Zhou Qian.Review of multipath effects in GPS measurement[J].Chinese Journal of Engineering Geophysics,2010,7(3):382-387.

[3] 唐爐亮,常曉猛,李清泉,等.基于蟻群優(yōu)化算法與出租車GPS數(shù)據(jù)的公眾出行路徑優(yōu)化[J].中國公路學報,2011,24(2):89-96.

Tang Luliang,Chang Xiaomeng,Li Qingquan,et al.Public travel route optimization based on ant colony optimization algorithm and taxi GPS data[J].China Journal of Highway and Transport,2011,24(2):89-96.

[4] 伊廷華,張永恒,李宏男,等.基于改進粒子濾波算法的GPS多路徑效應理論與試驗研究[J].應用基礎與工程科學,2011,19(3):429- 441.

Yi Tinghua,Zhang Yongheng,Li Hongnan,et al.Theoretical and experimental investigations of GPS multipath effect based on improved particle filtering algorithm[J].Journal of Basic Science and Engineering,2011,19(3):429-441.

[5] 王安保,胡小明.基于GPS的啟發(fā)式Ad hoc路由算法研究[J].計算機應用研究,2010,27(12):4708-4710.

Wang Anbao,Hu Xiaoming.Heuristic routing algorithm based on GPS location information for Ad hoc networks[J].Application Research of Computers,2010,27(12):4708-4710.

[6] 姜鈺梁,譚智力,黃玉金.基于GPS的移動平臺路徑控制方法研究[J].湖南科技大學學報：自然科學版,2010,25(4):43-46.

Jiang Yuliang,Tan Zhili,Huang Yujin.Investigation of path control method in GPS navigation[J].Journal of Hunan University of Science & Technology:Natural Science,2010,25(4):43-46.

[7] 孫文彬,譚正龍,王江,等.最短路徑算法的并行化策略分析[J].地理與地理信息科學,2013,29(4):17-20.

Sun Wenbin,Tan Zhenglong,Wang Jiang,et al.An analysis of parallelizing shortest path algorithm[J].Geography and Geo-Information Science,2013,29(4):17-20.

[8] 李芳芳,劉棟,高憲文,等.基于多目標規(guī)劃的WSN路徑動態(tài)選擇算法[J].東北大學學報：自然科學版,2013,34(8):1082-1085.

Li Fangfang,Liu Dong,Gao Xianwen,et al.Dynamic routing algorithm based on multi-objective programming for WSN[J].Journal of Northeastern University:Natural Science,2013,34(8):1082-1085.

[9] 李耀軍,潘泉,趙春暉,等.基于空間關系幾何約束的無人機景象匹配導航[J].計算機應用研究,2010,27(10):382-385.

Li Yaojun,Pan Quan,Zhao Chunhui,et al.Scene matching navigation for UAV based on spatial relationship geometric constraints[J].Application Research of Computers,2010,27(10):382-385.

[10] Lin Shuying,Cai Wenxue.Logistices vehicle routing problem between two objects based on real-time traffic data[C]// IEEE International Conference on Service Operations and Logistics and Informatics.New York:IEEE,2008:2989-2994.

[11] 王亞潔,賈順平,蔣金亮.城市生活垃圾收運路線優(yōu)化模型及算法研究[J].重慶交通大學學報：自然科學版,2012,31(5):1024-1026.

Wang Yajie,Jia Shunping,Jiang Jinliang.Model and algorithm study for route optimization of municipal solid waste collection and transportation[J].Journal of Chongqing Jiaotong University:Natural Science,2012,31(5):1024-1026.

[12] 任其亮,喬丹.災后應急救援運輸路徑優(yōu)化模型研究[J].重慶交通大學學報:自然科學版,2010,29(6):951-954.

Ren Qiliang,Qiao Dan.Emergency rescue transportation route optimization model after disaster[J].Journal of Chongqing Jiaotong University:Natural Science,2010,29(6):951-954.