自適應(yīng)代價(jià)函數(shù)的GPS路線決策研究

李中華，楊 進(jìn)，倪明濤,王 慧

(1.樂(lè)山師范學(xué)院 智能信息處理及應(yīng)用實(shí)驗(yàn)室，四川 樂(lè)山 614000；2.樂(lè)山師范學(xué)院 數(shù)信學(xué)院，四川 樂(lè)山 614000)

0 引 言

GPS是全球定位系統(tǒng)(Global Positioning System)的簡(jiǎn)稱，利用導(dǎo)航衛(wèi)星進(jìn)行檢測(cè)和數(shù)據(jù)交換[1-2]。GPS目前得到廣泛應(yīng)用，如航海，航空和道路運(yùn)輸?shù)?。其中道路運(yùn)輸最普遍，也即為車載GPS。

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

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

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

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

1.1 GPS終端對(duì)電子地圖路況分析

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

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

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

假設(shè)權(quán)重向量P=[P1，P2，…，Pn]；線路綜合路況指標(biāo)為r，則：

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

(1)

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

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

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

(2)

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

(3)

當(dāng)?shù)缆反嬖诮煌ń箷r(shí)或只能逆行時(shí)，g6=1；這時(shí)對(duì)應(yīng)的P6=∞。

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

根據(jù)用戶各個(gè)具體條件下對(duì)目標(biāo)指數(shù)的要求不同，自適應(yīng)調(diào)整代價(jià)函數(shù)。

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

(4)

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

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

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

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

(5)

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

(6)

重復(fù)第2步，直到Q=N，結(jié)束。

2 仿真實(shí)驗(yàn)

假設(shè)有的城市道路交通拓?fù)鋱D，如圖1。

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

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

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

表1 網(wǎng)絡(luò)中各道路路況信息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代價(jià)函數(shù)J最小的路徑
Fig.2ThesmallestrouteofcostfunctionJ

3 結(jié) 語(yǔ)

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

[1] 朱玉璽,崔如春,黃峻藝.“GPS最短路徑”搜索研究與實(shí)施[J].計(jì)算機(jī)工程與設(shè)計(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測(cè)量中多路徑效應(yīng)研究綜述[J].工程地球物理學(xué)報(bào),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].中國(guó)公路學(xué)報(bào),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] 伊廷華,張永恒,李宏男,等.基于改進(jìn)粒子濾波算法的GPS多路徑效應(yīng)理論與試驗(yàn)研究[J].應(yīng)用基礎(chǔ)與工程科學(xué),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].計(jì)算機(jī)應(yīng)用研究,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的移動(dòng)平臺(tái)路徑控制方法研究[J].湖南科技大學(xué)學(xué)報(bào)：自然科學(xué)版,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].地理與地理信息科學(xué),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] 李芳芳,劉棟,高憲文,等.基于多目標(biāo)規(guī)劃的WSN路徑動(dòng)態(tài)選擇算法[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版,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] 李耀軍,潘泉,趙春暉,等.基于空間關(guān)系幾何約束的無(wú)人機(jī)景象匹配導(dǎo)航[J].計(jì)算機(jī)應(yīng)用研究,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ùn)路線優(yōu)化模型及算法研究[J].重慶交通大學(xué)學(xué)報(bào)：自然科學(xué)版,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] 任其亮,喬丹.災(zāi)后應(yīng)急救援運(yùn)輸路徑優(yōu)化模型研究[J].重慶交通大學(xué)學(xué)報(bào):自然科學(xué)版,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.