河北大學(xué)電子信息工程學(xué)院 王學(xué)軍 孫榮霞 馬少卿 沈文博

時間耗費最少路徑算法研究

河北大學(xué)電子信息工程學(xué)院 王學(xué)軍 孫榮霞 馬少卿 沈文博

經(jīng)典的Dijkstra、Floyd最短路徑算法不能很好的描述日益變化的現(xiàn)代城市交通網(wǎng)絡(luò).本研究將所在城市交通網(wǎng)絡(luò)圖按照劃分的N個限制搜索區(qū)域,在每個限制搜索區(qū)域中應(yīng)用k-Means算法對該區(qū)域的交通流狀況進(jìn)行聚類分析以得分類簇.在每一個分類簇中,以該簇中各個邊的時間耗費以及結(jié)點耗費作為邊的權(quán)重,替代經(jīng)典最短路徑算法中邊的距離權(quán)重,得到時間耗費最少路徑算法.在網(wǎng)絡(luò)規(guī)模日益擴大情況下,通過采集2周實際交通數(shù)據(jù)進(jìn)行仿真實驗,本算法取得良好效果.

最短路徑;k-means聚類;城市交通網(wǎng)絡(luò)圖;時間耗費

0 引言

最短路徑問題一直是圖論、通信、城市交通網(wǎng)絡(luò)研究的熱點.在城市交通網(wǎng)絡(luò)中,怎樣優(yōu)化從源結(jié)點到目的地結(jié)點的路徑以減少耗費(例如時間耗費、能源耗費等)是重要的研究內(nèi)容.例如醫(yī)院救護(hù)車去救助城市道路中的傷者(交通事故、跌倒老人等)消防車緊急趕往城市火災(zāi)現(xiàn)場去滅火;出租車司機將乘客送到指定地點等等都可以看作是網(wǎng)絡(luò)圖結(jié)點對之間的最短路徑模型.Dijkstra、Bellman-Ford等經(jīng)典最短路徑算法不能很好地解決城市交通網(wǎng)絡(luò)的結(jié)點對之間的最短路徑[1].因為,這些經(jīng)典算法考慮的是靜態(tài)圖中的最短路徑.目前看到的改進(jìn)的經(jīng)典最短路徑算法是靜態(tài)的[2,3].在真實的城市交通網(wǎng)絡(luò)中,最短路徑往往受到很多因素的影響.辟如:車流量隨時間的變化,結(jié)點(交通網(wǎng)絡(luò)中可看作紅綠燈路口)的等待時間,天氣情況(下雨、下雪、大霧等等)城市道路的基礎(chǔ)設(shè)施是否完善,動態(tài)交通網(wǎng)絡(luò)圖受到很多復(fù)雜因素的影響.在城市交通網(wǎng)絡(luò)最短路徑問題中:怎樣選擇一條最優(yōu)路徑快速救助病人、救火、省時送乘客到目的地等,這其中的路徑優(yōu)化其實是時間最短路徑問題,也就是時間耗費最少的路徑問題.本研究擬采用時間耗費替代邊的距離權(quán)重的算法實現(xiàn)時間耗費最少.

1 時間耗費最少路徑算法

社會交通網(wǎng)絡(luò)中交通流量參數(shù)主要有車流量、時間占有率、速度[4]等等.本文是在可見度正常的情況下來分析交通路況的.路段的平均速度的變化,在穩(wěn)定的區(qū)間內(nèi).一天當(dāng)中,以交通早高峰時城市承受的車流量最重,其次是晚高峰,午高峰最少;以一周為例,一般來說周一的車流量最大然后每天遞減,周六周日最小.

1.1 時間耗費最少路徑

本研究設(shè)網(wǎng)絡(luò)圖G={v,E,W}.其中v={1,2,…,n}為結(jié)點集合,E為vij(i≠j)即任意鄰接結(jié)點間的邊的集合.在交通網(wǎng)絡(luò)中,結(jié)點v可看作紅綠燈路口,邊E為鄰接的路口間的路段,W是時間耗費的集合(權(quán)重):它包括路口的等待時間耗費Wi也就是結(jié)點的時間耗費;WL(i,j)(i≠j)為交通網(wǎng)絡(luò)路段的時間耗費即網(wǎng)絡(luò)圖邊的時間耗費.Wi是時間變化的離散隨機變量,WL(i,j)是時間變化的連續(xù)隨機變量.設(shè)L(i,j)==dist(i,j)為鄰接結(jié)點i與結(jié)點j之間的路徑距離簡寫為Li,j;Vij為L(i,j)路段的車輛平均速度;Ti,s為結(jié)點的紅燈等待時間(車輛的紅燈一次循環(huán)等待時間,為了簡化,沒有把車輛左轉(zhuǎn)等待時間計算在內(nèi),只計算直行等待時間)Tig為綠燈通行時間;Vmax為城市路段的限速的最高速度.

①當(dāng)WL(i,j)=Li,j/Vi,j(i≠j)∈(Tjs,Tjs+Tjg),Wj=0;紅燈循環(huán)結(jié)束,綠燈通行結(jié)束之前,車輛的路段耗費時間如果在這個時間區(qū)域內(nèi),那么車輛的節(jié)點耗費時間為零.②當(dāng)WL(i,j)<=Tjs時,則有Wj=tj,tj∈(ti,Tjs),可見此路段的交通路況不是擁堵的.③而當(dāng)WL(i,j)>=Tjs+Tjg時,此路段的路況趨向于擁堵.Wi時間依賴的離散變量,而WL(i,j)卻是連續(xù)的隨機變量.Dijkstra等經(jīng)典的最短路徑算法不能很好的滿足當(dāng)今日益增大的交通網(wǎng)絡(luò)的需求,無法近似計算動態(tài)隨機城市交通網(wǎng)絡(luò)的時間耗費.

根據(jù)上述分析,本研究按照時間耗費最少來求解最短路徑問題,也就是將動態(tài)的網(wǎng)絡(luò)邊以及結(jié)點耗費轉(zhuǎn)化為可衡量的時間耗費,并將時間耗費等效為網(wǎng)絡(luò)圖邊的權(quán)重應(yīng)用于那些經(jīng)典的最短路徑算法.Dijkstra等算法已證明其最短路徑的子路徑仍然是最短路徑,這其實就是一種貪心策略.

定義1:時間耗費最少路徑:就是從源結(jié)點s到目的地結(jié)點d的所有鄰接路徑中,總的時間耗費Wt(s,d)最少的那條路徑.Wt(s,d)其中Wi是時間耗費最少路徑中經(jīng)過的結(jié)點的耗費值,而Wt(i,j)則是鄰接結(jié)點間的邊的時間耗費值.由于Wi是離散變量每個結(jié)點等待時間近似為時間的常數(shù)這項值較容易測得.而∑Wt(i,j)為動態(tài)變化的,令由于近似時間等待常數(shù)則Wt(s,d)等價于Li,j是鄰接結(jié)點間的路徑距離,它是常數(shù),那么求min∑Wt(i,j)相當(dāng)于求其對偶問題,即希望從源結(jié)點s到目的地結(jié)點d所經(jīng)過的每一條邊Li,j的平均通過速度為那么當(dāng),則有車輛將在此Li,j邊獲得最少時間耗費.基于貪心策略,時間耗費最短路徑中的子路徑仍然是時間耗費最少的路徑,那么一定有時間耗費最少,即

1.2 聚類區(qū)域的限制搜索區(qū)域,應(yīng)用時間耗費最少路徑算法

定義2:時間耗費簇:用k-means聚類算法把網(wǎng)絡(luò)圖劃分為k個簇,在每個簇中將圖G中的結(jié)點與邊的耗費等效為相應(yīng)時間耗費的結(jié)點,包含這樣結(jié)點的簇稱為時間耗費簇.經(jīng)典的最短路徑算法在求源結(jié)點s到目的地結(jié)點d的最短路徑中,往往需要遍歷整個圖,廣度優(yōu)先搜索的總運行時間為O(V+E).文獻(xiàn)[6,7]分別改進(jìn)了交通網(wǎng)絡(luò)的限制搜索區(qū)域.假設(shè)B市有M個區(qū),則這M個區(qū)就是限制搜索的區(qū)域.如果源結(jié)點s與目的地結(jié)點d在同一分區(qū),則搜索范圍將大幅減少;在同一個區(qū)域內(nèi),按照k-means聚類算法劃分的k個簇,然后按照時間耗費最少這個標(biāo)準(zhǔn),搜索這k個聚類簇.一般而言,在城市交通網(wǎng)絡(luò)中,k取值3~4為最佳.如果不在同一個區(qū)域,同理仍然是在鄰接的區(qū)域內(nèi)搜索k個時間耗費簇.時間耗費最少算法:前面已經(jīng)提到過,用時間耗費來代替靜態(tài)圖鄰接結(jié)點間的邊的權(quán)重.交通網(wǎng)絡(luò)圖中時間耗費包括結(jié)點耗費和路段的時間耗費.

定義3:時間耗費最少路徑算法:W(i,j)是i到j(luò)的時間權(quán)重;path(i,j):i到j(luò)的路徑上i的后繼點;輸入帶權(quán)鄰接矩陣a(i,j).(1)賦初值,對所有i、j,W(i,j)?a(i,j),path(i,j)?j,k=l.(2)更新W(i,j),path(i,j)對所有i,j,若W(i,k)+W(k,j)

其中W(i,j)=Wi+Wt(i,j).

2 仿真實驗

仿真試驗建立在連續(xù)兩周對保定市五四路、長城大街、恒祥大街、裕華路的包圍區(qū)域內(nèi)的交通路段和交叉口的觀測數(shù).仿真軟件為Matlab2014a.對比了時間耗費最少路徑算法與經(jīng)典的Floyd最短路徑算法(將Floyd算法的靜態(tài)距離等效為相應(yīng)的時間耗費).由于周一早高峰時段,交通路況最為繁重,這一時間段最適合比較兩種算法的時間耗費.所以仿真試驗選取周一早高峰7:00-9:00這一時間段.城市仿真圖,如圖1所示.

圖1 仿真實驗城市交通網(wǎng)絡(luò)圖

圖1是無向圖.仿真實驗發(fā)現(xiàn),時間耗費最少路徑算法比Flord經(jīng)典算法最大節(jié)約時間為3.29min的路徑:4與13;5與13;時間耗費最少算法選擇的路線是13、14、6、5、4;Flord選擇是13、3、6、5、4.4與13的路線包含5與13.仿真實驗也發(fā)現(xiàn)在節(jié)點數(shù)較少的情況下,時間差為0,兩種算法選擇了同樣的路線.以結(jié)點對3與4為例:兩種算法都是選擇了圖1中3、6、5、4這一路線.這一路線相對來說距離最短并且避免了擁堵路段.

3 結(jié)論

本文將機器學(xué)習(xí)聚類技術(shù)應(yīng)用于城市交通路況,在城市的每個區(qū)域內(nèi)根據(jù)聚類簇劃分成限制搜索區(qū)域,減小了搜索規(guī)模.本研究的時間耗費最少路徑算法,相對于經(jīng)典Floyd算法用于城市交通網(wǎng)絡(luò)時,通過2周實際采集交流數(shù)據(jù),得到本研究的時間耗費最少算法能夠最大縮短3.29分鐘,至少也等于距離權(quán)重的Floyd算法等效時間耗費.

[1]科爾曼(美)(Cormen,T.H.)等,著.殷建平,等譯.算法導(dǎo)論(原書第3版)[M].北京:機械工業(yè)出版社,2013,1:340-410.

[2]劉代波,侯孟書,武澤旭,屈鴻.一種高效的最短路徑樹動態(tài)更新算法[J].計算機科學(xué),2011,38(7):96-99.

[3]王樹西,吳政學(xué).改進(jìn)的Dijkstra最短路徑算法及其應(yīng)用研究[J].計算機科學(xué),2012,39(5):223-228.

[4]孫占全,潘景山,張贊軍,張立東,青艷.基于主成分分析與支持向量機結(jié)合的交通流預(yù)測[J].公路交通科技,2009,26(5):127-131.

[5]周志華著.機器學(xué)習(xí)[M].北京:清華大學(xué)出版社,2016(197-214):198-215.

[6]陸鋒,盧冬梅,崔偉宏.交通網(wǎng)絡(luò)限制搜索區(qū)域時間最短路徑算法[J].中國圖像圖形學(xué)報,1999,4(10):849-853.

[7]付夢印,李杰,鄧志紅.限制搜索區(qū)域的距離最短路徑規(guī)劃算法[J].北京理工大學(xué)學(xué)報,2004,24(10):88-89.

王學(xué)軍(1984-),男,碩士研究生在讀,主要研究方向:算法、人工智能、機器學(xué)習(xí).

馬少卿(1992-),男,碩士研究生在讀,主要研究方向:算法分析.

沈文博(1988-),男,碩士研究生在讀,主要研究方向:智能微電網(wǎng).

孫榮霞(1960-),女,河北保定人,教授級工程師,主要研究方向:測控技術(shù)以及風(fēng)光互補發(fā)電的教學(xué)與科研工作.