帶限制的交通網(wǎng)絡(luò)最短路徑建模方法

帶限制的交通網(wǎng)絡(luò)最短路徑建模方法

1基于圖的概念的分析隨著社會(huì)的發(fā)展和城市人口的增加，城市交通問(wèn)題已成為一個(gè)日益嚴(yán)重的問(wèn)題。作為一個(gè)復(fù)雜的系統(tǒng)，城市交通包括交通燈的合理配置、單一性和禁行等限制，以及交通燈的合理配置、單一性和禁行等限制，從而合理地分配交通流，提高交通和交通安全效率。然而，不同的地圖可以充分顯示公共交通系統(tǒng)的各種情況。因此，引入地圖的概念將限制城市公共交通系統(tǒng)的情況進(jìn)行分析。在圖論中對(duì)一般情況下最短路徑問(wèn)題的求解已有了較為成熟的算法.對(duì)車(chē)輛誘導(dǎo)系統(tǒng)而言,現(xiàn)實(shí)的交通情況中許多經(jīng)典算法不能直接應(yīng)用,因?yàn)樵趯?shí)際道路條件下,為了使得交通暢通,交通管理部門(mén)制定了許多規(guī)則,其中包括路段單行、路口禁止左、右轉(zhuǎn)行等等情況,這樣就使得表面上連通的道路網(wǎng)絡(luò)實(shí)際上可能并不連通.因此本文考慮設(shè)計(jì)算法將這種含有交通限制的路網(wǎng)轉(zhuǎn)化為不含禁行的一般路網(wǎng),然后再利用圖論中的有效經(jīng)典算法完成最終的最優(yōu)路徑求解.2最短路徑的網(wǎng)絡(luò)模型2.1vi-vj-el的sq3實(shí)際道路中禁止通行作為一種強(qiáng)制的交通規(guī)則普遍存在,對(duì)于含有禁行路線的道路網(wǎng)絡(luò)包括兩種:第一種是某一路段禁止通行;第二種情況是某一路口禁止左轉(zhuǎn)、或禁止右轉(zhuǎn)或者禁止直行.于是我們可以用這樣一個(gè)四元組G(V,E,F,M)來(lái)表示道路中含有禁行路線的道路網(wǎng),其中(1)V是結(jié)點(diǎn)集,V={v1,v2,…,vn}(代表路口、站點(diǎn)等).(2)E表示單向弧集,E={e1,e2,…,ek},其中el=〈vi,vj〉,即元素el是以vi為弧尾以vj為弧頭的單向弧(代表實(shí)質(zhì)存在的交通線路).(3)F表示禁行路線集合,F={f1,…,fr;d1,…,dg},其中fl=〈vi,vj,vk〉表示從結(jié)點(diǎn)vi經(jīng)由〈vi,vj〉到達(dá)結(jié)點(diǎn)vj,再經(jīng)由〈vj,vk〉到達(dá)結(jié)點(diǎn)vk是禁行的.dl=〈vi,vj〉,表示結(jié)點(diǎn)vi經(jīng)由〈vi,vj〉到達(dá)結(jié)點(diǎn)vj是禁行的(代表由于某種原因強(qiáng)行禁止通行的車(chē)輛通行線路).(4)M是帶權(quán)的鄰接矩陣,mij表示〈vi,vj〉上的權(quán)重,其中元素mij≥0,〈vi,vj〉∈E(代表車(chē)輛通行某段線路的長(zhǎng)度).對(duì)于含有禁行路線的路網(wǎng),定義從點(diǎn)vs出發(fā),vt為終點(diǎn)的不含禁行路線的有向路線稱為合法的vs→vt有向路徑,在所有合法的vs到vt有向路徑中其所經(jīng)過(guò)的所有有向弧的權(quán)之和最小的路徑為vs→vt的最短路.另外,還要指出對(duì)于不含禁行路線的道路網(wǎng)絡(luò)情況較為簡(jiǎn)單.與含有禁行路線的道路網(wǎng)絡(luò)相比,不含禁行路線的道路網(wǎng)絡(luò)實(shí)際上可以用三元組G(V,E,M)來(lái)表述,對(duì)它的最優(yōu)路徑的求解,可以直接利用圖論中最短路徑算法,其中比較成熟和效率較高的算法是按路徑長(zhǎng)度遞增的順序產(chǎn)生最短路徑的Dijkstra算法.2.2清除d,v,m對(duì)于含有禁行路線的道路網(wǎng)絡(luò),不能直接利用經(jīng)典Dijkstra算法來(lái)求解最優(yōu)路徑.于是我們考慮將含有交通限制的路網(wǎng)轉(zhuǎn)化為不含禁行的一般路網(wǎng)再進(jìn)行處理,具體步驟如下:(1)把圖G(V,E,F,M)轉(zhuǎn)化成G(V,E,Ff,M),其中Ff={f1,f2,…,fr}.該步驟實(shí)際上是將〈vp,vq〉,(vp,vq∈V)等只包含兩點(diǎn)一線的禁行有向線段從原圖中直接刪除,即剔除d1,…,dg,從而完成簡(jiǎn)化的過(guò)程;(2)把圖G(V,E,Ff,M)轉(zhuǎn)化成為G(V′,E′,M′),其中V′=E.即E中epq=〈vp,vq〉對(duì)應(yīng)于vpq∈V′.也就是說(shuō),vpq∈V′,當(dāng)且僅當(dāng)存在epq∈E;〈vpq,vyz〉∈E′,當(dāng)且僅當(dāng)存在epq∈E,eyz∈E,q=y且〈vp,vq,vz〉ue06fFf;此時(shí)令mpqz=mpq,其中mpq∈M,mpqz是E′中弧〈vpq,vqz〉上的權(quán)重,mpqz∈M′;(3)在G(V′,E′,M′)基礎(chǔ)上添加S={si},T={tj}及相應(yīng)的邊和邊上的權(quán)重,得G(V*,E*,M*),其中V*=V′∪S∪T;E*=E′∪Es∪ET,其中所有〈si,viq〉的集合構(gòu)成Es,所有〈vpj,tj〉的集合構(gòu)成ET,對(duì)?vpj,viq∈V′;M*=M′∪Ms∪Mt,其中MS為ES中所有〈si,viq〉上的權(quán)重,令其均為0,而MT為ET中所有〈vpj,tj〉上的權(quán)重,令〈vpj,tj〉的權(quán)重為mpj.至此,我們已經(jīng)完成了由含有禁行路線的道路網(wǎng)絡(luò)G(V,E,Ff,M)到不含禁行的一般路網(wǎng)G(V*,E*,M*)的轉(zhuǎn)化.這樣,求G中最優(yōu)路徑vi→vj也就等價(jià)于在G*中求解si→tj的最短路.3禁行路線v#,e#,m構(gòu)造的較短路徑例假設(shè)圖G(V,E,F,M)中V={v1,v2,…,v5},E={〈v1,v2〉,〈v2,v1〉,〈v2,v3〉,〈v3,v2〉,…},F={〈v2,v1〉,〈v4,v3〉,〈v5,v4〉,〈v3,v2,v4〉}以及權(quán)重信息M={m12=m21=1,m23=m32=2,m24=m42=5,…},具體信息如圖1所示.現(xiàn)在我們需要求解某兩點(diǎn)間的最短路(例如:求解v1到v5的最短路).經(jīng)過(guò)算法步驟(1)對(duì)原始圖G(V,E,F,M)的簡(jiǎn)單處理,我們得到G(V,E,Ff,M)如圖2所示.圖G(V,E,Ff,M)中包含了禁行路線的部分信息,如v2不能直接通過(guò)路網(wǎng)到達(dá)v1,v4不能直接到達(dá)v3和v5也不能直接到達(dá)v4.此時(shí),還需注意對(duì)于從v3不能間接通過(guò)v2到達(dá)v4,即〈v3,v2,v4〉這種路口禁止通行的信息還未在圖形中表述出來(lái).再經(jīng)過(guò)算法步驟(2),(3),我們就可以完整地將以上這種含有禁行路線的求最短路問(wèn)題的圖G(V,E,F,M)轉(zhuǎn)化得到不含禁行路線的圖G(V*,E*,M*)(圖3).由此,對(duì)應(yīng)于圖G(V,E,F,M)中的禁行路線〈v2,v1〉,〈v4,v3〉,〈v5,v4〉以及〈v3,v2,v4〉對(duì)應(yīng)于轉(zhuǎn)化后的圖G*中就不存在結(jié)點(diǎn)v21,v43,v54及邊〈v32,v24〉.最后,我們就可以根據(jù)經(jīng)典的Dijkstra算法對(duì)不含禁行路線的圖G(V*,E*,M*)進(jìn)行計(jì)算,易知G(V*,E*,M*)中從s1到t5的最短路為s1→v12→v23→v34→v45→t5.容易發(fā)現(xiàn)圖G*中的這條路徑對(duì)應(yīng)于原來(lái)圖G中的路徑v1→v2→v3→v4→v5,從而我們就得到了v1到v5的最短路徑.按照上面的步驟,再利用經(jīng)典的Dijkstra算法容易得到圖G(V,E,F,M)中各點(diǎn)間的最短路徑,結(jié)果如表1所示.4交通網(wǎng)絡(luò)的建模優(yōu)化本文從含有禁行路線的道路網(wǎng)絡(luò)的轉(zhuǎn)化及對(duì)Dijks