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

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

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