杜牧青 鞠姿彥 呂晨希 李東宇 李 嘉 趙國軍
(河海大學(xué)土木與交通學(xué)院 南京 210098)
車輛路徑誘導(dǎo)系統(tǒng)向司機提供的最優(yōu)路徑,一般是一條以行駛距離最短或者行駛時間最短為目標(biāo)的簡單路徑[1].從易于實現(xiàn)的角度,主流車輛路徑誘導(dǎo)系統(tǒng)多采用Dijkstra算法及其改進算法(如考慮啟發(fā)信息的A*算法)實現(xiàn)路徑搜索功能.這類路徑算法在本質(zhì)上都是單路徑算法,通常每次搜索只能得到一條最優(yōu)路徑[2].但是,單一的路徑誘導(dǎo)并不能考慮道路狀況的不確定變化,如擁堵、交通事故的影響,容易將車流集中引導(dǎo)至相同的路線上,導(dǎo)致沿途道路交通量急劇增加形成擁堵,降低了導(dǎo)航系統(tǒng)的實用性和可信度[3].由于單路徑算法的不足,尋求有效的多路徑算法成為車輛路徑誘導(dǎo)領(lǐng)域的熱點[4].
目前,常見的多路徑生成算法可以被劃分為k-最短路徑算法和完全不相交路徑算法兩種[5].研究學(xué)者在此基礎(chǔ)上提出了許多改進算法.Jin等[6]研究了基于一種有約束弧的時間網(wǎng)絡(luò)的K條最短路徑問題.趙禮峰等[7]結(jié)合遺傳算法和模擬退火算法,提出了求解K最短路徑問題的新算法.一些學(xué)者提出采用k-最短路徑算法求取多條候選路徑供駕駛員選擇,將最后的決策權(quán)留給駕駛員[8-11],需要進一步考慮駕駛員對每條路徑的個性化評價[12].因此,目前常用的方法是考慮駕駛員不同偏好的多路徑誘導(dǎo),其本質(zhì)上仍然是將不同最優(yōu)目標(biāo)的簡單路徑作疊加.上述多路徑算法通常不考慮網(wǎng)絡(luò)中延誤的不確定性,尤其是信號交叉口延誤的不確定性.且從多路徑搜索算法的原理而言,駕駛員需要在起點確定方案選擇,不能在多方案之間實現(xiàn)路徑的轉(zhuǎn)換(除非駕駛員在行駛過程中手動更改路線).可見考慮駕駛員偏好的多路徑到并不能夠從本質(zhì)上實現(xiàn)回避延誤的問題.因此,如何實現(xiàn)多路徑誘導(dǎo)方案中路線的靈活轉(zhuǎn)換,是幫助駕駛員回避交通延誤的關(guān)鍵問題.
Spiess等[13]基于公交線路的客流分配模型,最早提出了超路徑的概念.在公交模型中,最優(yōu)超路徑被解釋為一種最優(yōu)的乘車策略,包含了起終點之間所有可以降低乘車者等車時間的公交線路集合.Bell[14]進一步考慮了道路網(wǎng)絡(luò)中每條路段上行程時間的不確定性,將Spiess和Florian的公交超路徑應(yīng)用于道路網(wǎng)絡(luò).Bell指出超路徑搜索算法是一種特殊的多路徑算法,以期望行程時間最小為目標(biāo),從實際路網(wǎng)中搜索出起終點之間所有可能最短路徑,納入超路徑子網(wǎng)中.Ma等[15]在Bell研究的基礎(chǔ)上,提出了加快超路徑算法的搜索速度的改進方法.然而,當(dāng)前適用于道路網(wǎng)路的超路徑算法都未考慮交叉口延誤對期望行程時間的影響,且未考慮超路徑算法在誘導(dǎo)系統(tǒng)的應(yīng)用,無法為車輛進行實用可靠的路徑誘導(dǎo).
文中基于交叉口信號配時提出了一種交叉口延誤的計算方法,重新編寫了超路徑算法,用于路徑搜索.并依據(jù)超路徑算法“推薦優(yōu)先綠燈相位”的特點,引入了車路協(xié)同技術(shù)完善超路徑誘導(dǎo)系統(tǒng).通過車輛和道路的信息交互,超路徑誘導(dǎo)系統(tǒng)不斷以語音、文字、圖像、視頻等方式向駕駛者提示前方路況和應(yīng)做的選擇,實現(xiàn)車輛在超路徑子網(wǎng)中靈活轉(zhuǎn)換路線,降低交叉口延誤.同時依托超路徑誘導(dǎo)系統(tǒng)可以實現(xiàn)流量在網(wǎng)絡(luò)中的合理分配,降低網(wǎng)絡(luò)整體車輛行程時間,優(yōu)化網(wǎng)絡(luò)性能.
超路徑考慮路網(wǎng)中延誤的不確定性,是由起終點之間所有可能最短路徑構(gòu)成的集合.原始的超路徑算法,以終點作為初始搜索節(jié)點對路網(wǎng)中的路段逐一搜索,篩選出能降低期望行程延誤的路段,組成超路徑.超路徑搜索結(jié)果還包括每個路段在超路徑集合中被選擇的概率,該概率可作為將流量分派到超路徑集合各路段上的比例[16].本文對原始的超路徑搜索算法做出改進,對信號交叉口節(jié)點進行擴展,以路段的行駛時間與交叉口期望延誤之和最小為目標(biāo)函數(shù),得到起訖點之間的超路徑結(jié)果.
原始的超路徑算法僅考慮路段延誤的不確定性,將其解釋為離開其上游結(jié)點的延誤.當(dāng)考慮交叉口轉(zhuǎn)向延誤時,離開結(jié)點的延誤將取決于車輛經(jīng)過交叉口的轉(zhuǎn)向行為.由交叉口西側(cè)和北側(cè)進口道進入交叉口的車輛,在從南側(cè)和東側(cè)出口道離開時所受延誤影響會有明顯不同,即分別為右轉(zhuǎn)對應(yīng)直行和直行對應(yīng)左轉(zhuǎn).兩種轉(zhuǎn)向?qū)?yīng)的相位配時不同,所受延誤影響必然存在差異.基于此,本文在路網(wǎng)中對于有信號控制的交叉口節(jié)點進行擴展,克服了原始超路徑算法不能反映交叉口轉(zhuǎn)向阻抗的缺點.本文采用網(wǎng)絡(luò)擴展法表示交叉口的轉(zhuǎn)向行為,將交叉口的各個轉(zhuǎn)向抽象成虛擬路段,用這些路段阻抗代表交叉口轉(zhuǎn)向延誤[17].以圖1為例,對于單行車道,有四種轉(zhuǎn)向,引入四條虛擬路段;對于雙行車道,有十二種轉(zhuǎn)向,引入十二條虛擬路段.
圖1 道路交叉口的擴展表示
在擴展的道路網(wǎng)絡(luò)中,最優(yōu)超路徑問題被描述為以路段行駛時間和交叉口期望延誤之和最小為目標(biāo)函數(shù)的數(shù)學(xué)優(yōu)化模型,為
(1)
s.t.
(2)
pij∈[0,1],?(i,j)∈A
(3)
wi≥dij·pij,?(i,j)∈A
(4)
對于擴展的網(wǎng)絡(luò),虛擬路段對應(yīng)于交叉口的轉(zhuǎn)向,其最大延誤dij由信號燈周期性變化引起,令其等于該轉(zhuǎn)向的非綠燈時長.本文假設(shè)車輛在隨機時刻到達交叉口,并定義交叉口轉(zhuǎn)向ri服務(wù)頻率fri(fri=1/dri).在超路徑中,對于任意交叉口進口道節(jié)點i,可能存在多個可用的轉(zhuǎn)向ri,采用集合Ri表示該節(jié)點的全部可用轉(zhuǎn)向.進一步,定義交叉口服務(wù)頻率fi=∑ri∈Rifri,則車輛在交叉口進口道的等待時間期望wi為
(5)
式中:α∈(0,1],α的取值取決于對交叉口信號配時的估計,在本文中假設(shè)α=1.
因此,本文的超路徑算法流程包括以下步驟:
步驟1指定起點r和終點s;創(chuàng)建路段集合L,將路網(wǎng)中所有路段加入集合L中;創(chuàng)建超路徑的路段集合H,令集合H初始為空集.初始化各變量如下:
令us=0,yr=1;
令ui=∞,?i≠s;
令yi=0,?i≠r;
令fi=0,?i∈V;pij=0,?(i,j)∈A;
當(dāng)dij>0時,令fij=1/dij;當(dāng)dij=0時,令fij=∞.
步驟2查找集合L中(uj+cij)最小的路段(i,j),作為當(dāng)前路段,并將其從集合L中移除.
步驟3若當(dāng)前路段滿足條件ui≥uj+cij,則進入步驟4;否則,返回步驟2.
步驟4更新當(dāng)前路段(i,j)的上游節(jié)點i到終點s的考慮延誤的最短行駛時間ui.
若ui=∞,fi=0,則進行如下運算:
否則,進行如下運算:
步驟5更新節(jié)點i處的組合服務(wù)頻率變量和數(shù)據(jù),作如下運算:
fi=fi+fij
步驟6將當(dāng)前路段(i,j)加入到集合H中,此時,若滿足條件L=?或uj+cij≥ur,進入步驟7;否則,返回步驟2.
步驟7求解路段及節(jié)點選擇概率:將網(wǎng)絡(luò)中的全部路段(i,j),按照uj+cij的值,從大到小排序;根據(jù)排序后的順序遍歷全部路段,若路段(i,j)∈H,則進行如下運算:
否則,令pij=0.
從起點r開始,追溯到達終點s的超路徑并輸出,用于路徑誘導(dǎo)決策.
為了進一步闡明超路徑算法的含義,采用方格網(wǎng)型的交通網(wǎng)絡(luò)并對每個節(jié)點進行編號,見圖2.以點r為起點,點s為終點,除5、16外其余為信號燈控制的節(jié)點,網(wǎng)絡(luò)中共含有20個節(jié)點和31條雙車道路段,并將網(wǎng)絡(luò)圖進行虛擬路段展開.圖3為路網(wǎng)中有信號控制的各交叉口的信號相位配時圖,表1為各路段的行程時間,表2為基于最大悲觀期望假設(shè)求得的各交叉口轉(zhuǎn)向的等待時間.
圖2 實例網(wǎng)絡(luò)圖
圖3 交叉口相位配時圖
表1 路段的行駛時間
基于最大悲觀期望假設(shè),對于各轉(zhuǎn)向路段延誤的計算以圖2所示T型交叉口2為例進行說明.當(dāng)行駛路線的前向交叉口編號為r,后續(xù)交叉口編號為3時,車輛在交叉口2時需要直行.對照圖3的相位圖,在交叉口2處的直行只屬于第一相位且在一個周期內(nèi)第一相位的綠燈時間是25 s,黃燈時間是5 s,紅燈時間是60 s.由于車輛在黃燈時間和紅燈時間內(nèi)停車等待,因此,確定執(zhí)行通過的轉(zhuǎn)向延誤為65 s.依照這個原理,推出圖2道路網(wǎng)絡(luò)中所有交叉口的轉(zhuǎn)向延誤,見表2.
表2 交叉口轉(zhuǎn)向的路段延誤
按算法步驟,篩選出超路徑,并在每條路段上標(biāo)注其被駕駛員選擇的概率,即誘導(dǎo)系統(tǒng)將車流量分配到各路段的比重,見圖4.
圖4 實例的路線概率圖
由路段概率得出可靠最短路徑一共有3條:①r-6-11-12-13-18-19-s,被選擇的概率為0.25;②r-6-11-16-17-18-19-s,被選擇的概率為0.25;③r-6-7-12-13-18-19-s,被選擇的概率為0.5.
算法運行獲得的三組結(jié)果見圖5.由圖5可知,在獲取的多組解中,用戶可以選擇這3條出行路徑靈活地改變行進路線,降低延誤時間.
圖5 實例的路線選擇圖
車路協(xié)同基于無線通信、傳感探測等技術(shù)獲取車輛和道路信息,通過車車、車路通信進行信息交互和共享,實現(xiàn)車輛與基礎(chǔ)設(shè)施之間智能協(xié)同與配合[18].車路協(xié)同系統(tǒng)由智能交通管理系統(tǒng)、智能通信系統(tǒng)、智能車輛子系統(tǒng)和智能路側(cè)系統(tǒng)四個部分組成[19-20].智能交通管理系統(tǒng)處理由智能車輛子系統(tǒng)和智能路側(cè)系統(tǒng)獲取的信息,計算超路徑子網(wǎng)中包含的各轉(zhuǎn)向?qū)?yīng)的時間,具體分為以下兩種情況:
分析比較出時間最短的轉(zhuǎn)向,并推薦給駕駛員.從而保證車輛在交叉口處始終選擇優(yōu)先綠燈相位,最小化交叉口等待延誤.圖6為車路協(xié)同系統(tǒng)的構(gòu)架,圖7為依托車路協(xié)同技術(shù)的超路徑誘導(dǎo)系統(tǒng)的信息交互原理.
圖6 車路協(xié)同系統(tǒng)構(gòu)架圖
圖7 車路協(xié)同信息交互
車輛在實際路況中行駛,超路徑誘導(dǎo)系統(tǒng)將進行如下誘導(dǎo).在出發(fā)前,車輛路徑誘導(dǎo)系統(tǒng)為駕駛員篩選出圖4的超路徑子網(wǎng),首先推薦駕駛員沿路段r-6行駛.具體流程如下.
步驟1當(dāng)車輛行駛接近交叉口6的通信范圍時,路側(cè)系統(tǒng)檢測到車輛駛?cè)?,獲取該車輛前直行車輛數(shù)Q1直=40輛、直行車流速度v1直=60 km/h、直行車輛流率q直=3 600輛/h、左轉(zhuǎn)車輛數(shù)Q1左=30、左轉(zhuǎn)車流速度v1左=50 km/h、左轉(zhuǎn)車輛流率q左=3 000輛/h、該交叉口信號燈當(dāng)前相位狀態(tài)信息,將這些信息傳輸給管理系統(tǒng).
步驟2智能車輛子系統(tǒng)從多路徑誘導(dǎo)方案中獲得在當(dāng)前交叉口的轉(zhuǎn)向策略集合S和車輛當(dāng)前位置,S包括直行和左轉(zhuǎn),并將這些信息傳輸至智能交通管理系統(tǒng).
步驟3計算車輛到直行和左轉(zhuǎn)的停車線時間.
最后,根據(jù)判斷條件t左>t直,向智能車輛子系統(tǒng)遞直行轉(zhuǎn)向.
步驟3車輛子系統(tǒng)顯示路徑推薦,車輛接收直行指令,車輛會提前變道,駛離交叉口.
圖8為車路協(xié)同誘導(dǎo)示意.駕駛員依據(jù)圖5三組行駛路線進行靈活的路線轉(zhuǎn)換.行駛至下一個路口時,超路徑誘導(dǎo)系統(tǒng)繼續(xù)根據(jù)“推薦優(yōu)先綠燈相位”的原則,從超路徑子網(wǎng)中搜索路徑推薦給駕駛員,直至行駛至目標(biāo)點.全部交叉口誘導(dǎo)示意圖見圖9.
圖8 車路協(xié)同誘導(dǎo)示意圖
圖9 完整交叉口誘導(dǎo)示意圖
由此可見,在以超路徑算法為依托的車輛路徑誘導(dǎo)系統(tǒng)中,駕駛員在交叉口可以靈活變換行車路線,達到降低交叉口延誤的效果,從而實現(xiàn)“可靠最短”的出行目的.
基于1.3提出的超路徑搜索算法,并應(yīng)用上述車輛誘導(dǎo)方法,從網(wǎng)絡(luò)總體流量角度分析超路徑誘導(dǎo)方案的優(yōu)點.假設(shè)某時段內(nèi)共計100名駕駛員從起點r行駛至終點s.分別沿超路徑算法篩選出來的三條路徑(見圖5)和時間最短的唯一路徑行駛,統(tǒng)計出車輛在交叉口的延誤情況,見表3.其中,車輛依據(jù)圖4的選擇比例計算結(jié)果,分配在超路徑中.
表3 超路徑和單路徑延誤時間對比
由表3的結(jié)果表明,在路網(wǎng)中應(yīng)用超路誘導(dǎo)系統(tǒng),可降低21.9%的總體平均延誤.由此可見,采用超路徑誘導(dǎo)策略,可以實現(xiàn)流量在網(wǎng)絡(luò)中的合理分配,達到網(wǎng)絡(luò)整體車輛行程時間最短的目的.
本文基于交叉口信號配時提出了一種交叉口等待時間的計算方法,并用于超路徑搜索.基于最大悲觀期望假設(shè)利用信號配時方案求得交叉口各轉(zhuǎn)向最大等待時間,進一步通過線性組合求出車輛在交叉口等待期望,避免了處理大量數(shù)據(jù),加快了路徑誘導(dǎo)方案的搜索速度.在路徑誘導(dǎo)方面,提出了在車路協(xié)同環(huán)境下實現(xiàn)對優(yōu)先綠燈相位的判斷的解決方案,進一步完善了超路徑誘導(dǎo)系統(tǒng),達到了優(yōu)先推薦綠燈相位的目的.
對于個體而言,駕駛員可以通過誘導(dǎo)系統(tǒng)在超路徑子網(wǎng)中靈活改變行駛路線,實現(xiàn)達到降低行程延誤的目的.對于整體網(wǎng)絡(luò)而言,超路徑基于交叉口服務(wù)頻率來合理分配路段車流量,降低整體網(wǎng)絡(luò)的車輛行駛時間,提升交通網(wǎng)絡(luò)性能,會產(chǎn)生巨大的經(jīng)濟效益.隨著人們對個性化出行需求的增多,超路徑誘導(dǎo)系統(tǒng)可引入相應(yīng)的需求因子變更目標(biāo)函數(shù),在提高網(wǎng)絡(luò)性能的同時,實現(xiàn)對用戶的個性化誘導(dǎo).同時,本文通過完善車路協(xié)同技術(shù)的判斷機制,實現(xiàn)了車路協(xié)同技術(shù)與超路徑誘導(dǎo)系統(tǒng)的結(jié)合,將在有效降低駕駛員行程延誤和完善智能交通誘導(dǎo)體系上發(fā)揮巨大作用.
本文基于信號配時計算車輛在交叉口的等待時間時,存在兩個假設(shè)條件:①最大悲觀期望假設(shè),假設(shè)車輛在交叉口每個轉(zhuǎn)向的等待時間是紅燈加黃燈時間;②獨立性假設(shè),假設(shè)車輛可選擇的相位相互獨立,計算在交叉口的期望等待時間時將各轉(zhuǎn)向等待時間線性組合.這兩個假設(shè)較為理想,可能會導(dǎo)致與實際情況存在一定偏差.今后的研究將上述假設(shè)條件做進一步完善,使得超路徑搜索結(jié)果更加貼合實際路網(wǎng)情況.