基于交通限制信息的動態(tài)最優(yōu)路徑規(guī)劃算法

基于交通限制信息的動態(tài)最優(yōu)路徑規(guī)劃算法

0交通堵塞的改善隨著城市交通的發(fā)展，道路數(shù)量不斷增加，道路網(wǎng)絡變得越來越復雜。同時,交通管理也日趨復雜,如在道路上根據(jù)預計的交通流設置單行、禁行限制,動態(tài)交通信息的發(fā)布有力地促進了交通合理分流,提高了交通的安全和效率。在路網(wǎng)中選擇最優(yōu)路徑并按最優(yōu)路徑行駛,是旅行者的最佳選擇。然而交通堵塞的發(fā)生,以及交通限制信息的存在,對選擇最優(yōu)路徑造成困難。車輛如果能夠在這樣的道路網(wǎng)絡找到從起點到目的的最優(yōu)路徑,則不僅節(jié)省了燃油和時間,而且可以從宏觀上改善交通狀況,減少或者避免交通堵塞?；诖四康?本文首先討論了具有交通限制約束的道路網(wǎng)絡模型,然后給出了一種考慮了靜態(tài)和動態(tài)交通限制信息的最優(yōu)路徑算法。1用于路段的交通限制信息道路網(wǎng)絡中存在兩類基本要素:結(jié)點和路段。圖1所示的是一個典型的具有5個結(jié)點和6條路段的道路網(wǎng)絡G。在圖1中,結(jié)點用圓圈表示,圓圈內(nèi)的數(shù)字表示結(jié)點的序號;路段用兩個結(jié)點之間的連線表示,路段旁邊的數(shù)字表示路段的長度。道路網(wǎng)絡采用鄰接矩陣也可以采用鄰接表表示。圖1中道路網(wǎng)絡G的鄰接表如圖2所示。道路網(wǎng)絡中存在兩類交通限制信息:第一類是動態(tài)的交通限制信息,例如發(fā)生在路段上的交通堵塞,其特點是隨時間變化較快;第二類是靜態(tài)的交通限制信息,例如設置在結(jié)點處的禁止通行標志,其特點是隨時間變化較慢。為了表示路段的交通擁堵狀況,給路段要素增加一個加權(quán)系數(shù)屬性,并將路段長度與加權(quán)系數(shù)的乘積稱為路段的加權(quán)長度。路段的交通越堵塞,此路段的加權(quán)系數(shù)越大,對應路段的加權(quán)長度也越長。用路段的加權(quán)長度表示車輛通過此路段的時間。結(jié)點交通限制信息主要指結(jié)點的禁行標志,用結(jié)點的禁行標志表描述。如圖3所示,如果從結(jié)點1駛向結(jié)點2時,在結(jié)點2處禁止左轉(zhuǎn)彎,這就意味著禁止從結(jié)點1經(jīng)過結(jié)點2進入結(jié)點5。所以,對于該禁行標志就可以通過在結(jié)點2處加入一個點對1,5來表示,1代表禁行起點的結(jié)點序號,5代表禁行終點的結(jié)點序號。實際上,結(jié)點2處的禁行標志可能不止1個,例如從結(jié)點3駛向結(jié)點2時,在該處禁止右轉(zhuǎn)彎,于是點對3,5也要加入。這樣,結(jié)點2處的所有禁行點對構(gòu)成了該結(jié)點的禁行標志表如表1所示。2行車路線的尋找最優(yōu)路徑是指駕駛員給定了起點和終點之后,系統(tǒng)自動在整個道路網(wǎng)絡中按照距離最短或者時間最短尋找一條最優(yōu)的行車路線。在整個道路網(wǎng)絡中尋找一條起點和終點之間的最短路徑的算法是一種經(jīng)典算法,其最常見的算法是Dijkstra算法。2.1最優(yōu)路徑選取前面已用路段的加權(quán)長度表示車輛通過此路段所需要的時間,因此最優(yōu)路徑也可以表示為加權(quán)長度最短的路徑。將Dijkstra算法中的長度替換為路徑的加權(quán)長度,就可求出連接起點和終點的最短路徑,也即考慮了動態(tài)交通信息的最短路徑。算法如下:設G=(V,E,w)為有限權(quán)圖,其中V是其中頂點集合,E是邊的集合,w是E中邊(i,j)的權(quán)的集合,稱為該邊的長度,記w(i,j)。下面求從起點s到終點e的最短路徑。設T是V的一個子集,且S不屬于T,記S=V-T(S順序記錄著最優(yōu)路徑上的結(jié)點)。對T中每一個頂點t,記WL(t)為s到t的所有路徑(這些路徑不包括T中其它的任何點)中加權(quán)長度最短的路徑的長度,WL(t)稱為t關(guān)于s的指標。若此路徑不存在,則令WL(t)=∞。(1)對T中每一頂點t,求WL(t)。(2)設m是T中具有關(guān)于s的指標值最小的頂點,即WL(m)=mint∈T(WL(t))WL(m)=mint∈Τ(WL(t))(1)(3)如果m就是終點e,則結(jié)束;否則令S′=SY{m},T′=T-{m}如果T′為空,則到(4);否則計算T′中每個頂點關(guān)于S′的指標WL′(m)=mint∈T[WL(t)?WL(m)+w(m,t)]WL′(m)=mint∈Τ[WL(t)?WL(m)+w(m,t)](2)(4)用S′代替S,T′代替T,重復(1)的操作,直至m到達e為止。(5)聲明s到e不存在最短路徑。2.2發(fā)送禁行標志的方法可以知道,結(jié)點的禁止通行標志涉及到此結(jié)點的前一個結(jié)點、此結(jié)點本身和下一個結(jié)點。由于Dijkstra算法沒有考慮前后結(jié)點的相關(guān)性,而不能適用于存在靜態(tài)交通限制信息的道路網(wǎng)絡。步驟(1)中WL(t)的取值變?yōu)?查看s的禁行標志表,如果是從t到s的單行線,則返回無窮大;否則返回路段的加權(quán)長度值。步驟(2)中w(m,t)的取值為:查看m的禁行標志表,如果m沒有設置任何禁行標志,則返回路段的加權(quán)長度。如果設置了禁行標志,則因為m是已經(jīng)求出了最優(yōu)路徑的結(jié)點,則求出最優(yōu)路徑上m的前一個結(jié)點mf。如果禁止從mf經(jīng)過m到達t則返回無窮大,否則返回路段的加權(quán)長度。這樣,就可以在道路網(wǎng)絡中存在靜態(tài)和動態(tài)的交通限制信息時尋找最優(yōu)路徑。我們將這種改進后的算法稱為基本尋路算法。2.3現(xiàn)有算法的改進如果所有從s到e的路徑都經(jīng)過某個結(jié)點c,則將這樣的結(jié)點c稱之為關(guān)節(jié)點。如果在關(guān)節(jié)點c處設置了禁止通行標志,并且在從s到c的最優(yōu)路徑上,c的前一個結(jié)點恰好是禁止通行標志的起點,則基本尋路算法會失效。在實際的道路網(wǎng)絡中,由于關(guān)節(jié)點處的交通非常擁擠,為了改善關(guān)節(jié)點處的道路狀況,一般情況下不會在關(guān)節(jié)點處設置禁止通行標志。但是為了實現(xiàn)最優(yōu)路徑算法的完整性,仍然需要對算法作進一步改進,實現(xiàn)這種情況下的尋路。步驟(1)WL(t)的取值變?yōu)?查看s的禁行標志表,如果是從s到t的單行線,則返回無窮大;如果s是t處所設置的禁行標志的起點,則返回無窮大;否則返回的路段加權(quán)長度值。步驟(2)w(m,t)的取值變?yōu)?查看m結(jié)點的禁行標志表,如果m結(jié)點和t結(jié)點都沒有設置任何禁行標志,則返回路段的加權(quán)長度;如果m結(jié)點設置了禁行標志,則因為m是已經(jīng)求出了最優(yōu)路徑的結(jié)點,則求出m的前一個結(jié)點設為mf。如果禁止從mf經(jīng)過m到達t則返回無窮大;查看t結(jié)點的禁行標志表,如果t結(jié)點設置了禁行標志并且m結(jié)點恰好是禁行標志的起點則返回無窮大;其他情況則返回路段的加權(quán)長度。這樣改進的算法我們稱之為擴展尋路算法。實際的尋路算法為:首先應用基本尋路算法,如果找到了最優(yōu)路徑則成功返回。否則應用擴展尋路算法,如果找到了最優(yōu)路徑則成功返回,否則返回沒有找到最優(yōu)路徑的出錯信息。3靜態(tài)和動態(tài)交通信息的最優(yōu)路徑清華大學汽車研究所開發(fā)了一種基于GPS的車輛自主導航系統(tǒng)。該系統(tǒng)的路網(wǎng)最優(yōu)