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

時(shí)間耗費(fèi)最少路徑算法研究

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

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

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

0 引言

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

1 時(shí)間耗費(fèi)最少路徑算法

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

1.1 時(shí)間耗費(fèi)最少路徑

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

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

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

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

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

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

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

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

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

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

圖1 仿真實(shí)驗(yàn)城市交通網(wǎng)絡(luò)圖

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

3 結(jié)論

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

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

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

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

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

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

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

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

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

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

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

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