杜牧青 鞠姿彥 呂晨希 李東宇 李 嘉 趙國(guó)軍

(河海大學(xué)土木與交通學(xué)院 南京 210098)

0 引 言

車輛路徑誘導(dǎo)系統(tǒng)向司機(jī)提供的最優(yōu)路徑，一般是一條以行駛距離最短或者行駛時(shí)間最短為目標(biāo)的簡(jiǎn)單路徑[1].從易于實(shí)現(xiàn)的角度，主流車輛路徑誘導(dǎo)系統(tǒng)多采用Dijkstra算法及其改進(jìn)算法(如考慮啟發(fā)信息的A*算法)實(shí)現(xiàn)路徑搜索功能.這類路徑算法在本質(zhì)上都是單路徑算法，通常每次搜索只能得到一條最優(yōu)路徑[2].但是，單一的路徑誘導(dǎo)并不能考慮道路狀況的不確定變化，如擁堵、交通事故的影響，容易將車流集中引導(dǎo)至相同的路線上，導(dǎo)致沿途道路交通量急劇增加形成擁堵，降低了導(dǎo)航系統(tǒng)的實(shí)用性和可信度[3].由于單路徑算法的不足，尋求有效的多路徑算法成為車輛路徑誘導(dǎo)領(lǐng)域的熱點(diǎn)[4].

目前，常見(jiàn)的多路徑生成算法可以被劃分為k-最短路徑算法和完全不相交路徑算法兩種[5].研究學(xué)者在此基礎(chǔ)上提出了許多改進(jìn)算法.Jin等[6]研究了基于一種有約束弧的時(shí)間網(wǎng)絡(luò)的K條最短路徑問(wèn)題.趙禮峰等[7]結(jié)合遺傳算法和模擬退火算法，提出了求解K最短路徑問(wèn)題的新算法.一些學(xué)者提出采用k-最短路徑算法求取多條候選路徑供駕駛員選擇，將最后的決策權(quán)留給駕駛員[8-11]，需要進(jìn)一步考慮駕駛員對(duì)每條路徑的個(gè)性化評(píng)價(jià)[12].因此，目前常用的方法是考慮駕駛員不同偏好的多路徑誘導(dǎo)，其本質(zhì)上仍然是將不同最優(yōu)目標(biāo)的簡(jiǎn)單路徑作疊加.上述多路徑算法通常不考慮網(wǎng)絡(luò)中延誤的不確定性，尤其是信號(hào)交叉口延誤的不確定性.且從多路徑搜索算法的原理而言，駕駛員需要在起點(diǎn)確定方案選擇，不能在多方案之間實(shí)現(xiàn)路徑的轉(zhuǎn)換(除非駕駛員在行駛過(guò)程中手動(dòng)更改路線).可見(jiàn)考慮駕駛員偏好的多路徑到并不能夠從本質(zhì)上實(shí)現(xiàn)回避延誤的問(wèn)題.因此，如何實(shí)現(xiàn)多路徑誘導(dǎo)方案中路線的靈活轉(zhuǎn)換，是幫助駕駛員回避交通延誤的關(guān)鍵問(wèn)題.

Spiess等[13]基于公交線路的客流分配模型，最早提出了超路徑的概念.在公交模型中，最優(yōu)超路徑被解釋為一種最優(yōu)的乘車策略，包含了起終點(diǎn)之間所有可以降低乘車者等車時(shí)間的公交線路集合.Bell[14]進(jìn)一步考慮了道路網(wǎng)絡(luò)中每條路段上行程時(shí)間的不確定性，將Spiess和Florian的公交超路徑應(yīng)用于道路網(wǎng)絡(luò).Bell指出超路徑搜索算法是一種特殊的多路徑算法，以期望行程時(shí)間最小為目標(biāo)，從實(shí)際路網(wǎng)中搜索出起終點(diǎn)之間所有可能最短路徑，納入超路徑子網(wǎng)中.Ma等[15]在Bell研究的基礎(chǔ)上，提出了加快超路徑算法的搜索速度的改進(jìn)方法.然而，當(dāng)前適用于道路網(wǎng)路的超路徑算法都未考慮交叉口延誤對(duì)期望行程時(shí)間的影響，且未考慮超路徑算法在誘導(dǎo)系統(tǒng)的應(yīng)用，無(wú)法為車輛進(jìn)行實(shí)用可靠的路徑誘導(dǎo).

文中基于交叉口信號(hào)配時(shí)提出了一種交叉口延誤的計(jì)算方法，重新編寫(xiě)了超路徑算法，用于路徑搜索.并依據(jù)超路徑算法“推薦優(yōu)先綠燈相位”的特點(diǎn)，引入了車路協(xié)同技術(shù)完善超路徑誘導(dǎo)系統(tǒng).通過(guò)車輛和道路的信息交互，超路徑誘導(dǎo)系統(tǒng)不斷以語(yǔ)音、文字、圖像、視頻等方式向駕駛者提示前方路況和應(yīng)做的選擇，實(shí)現(xiàn)車輛在超路徑子網(wǎng)中靈活轉(zhuǎn)換路線，降低交叉口延誤.同時(shí)依托超路徑誘導(dǎo)系統(tǒng)可以實(shí)現(xiàn)流量在網(wǎng)絡(luò)中的合理分配，降低網(wǎng)絡(luò)整體車輛行程時(shí)間，優(yōu)化網(wǎng)絡(luò)性能.

1 考慮交叉口轉(zhuǎn)向延誤的超路徑算法

1.1 超路徑搜索原理

超路徑考慮路網(wǎng)中延誤的不確定性，是由起終點(diǎn)之間所有可能最短路徑構(gòu)成的集合.原始的超路徑算法，以終點(diǎn)作為初始搜索節(jié)點(diǎn)對(duì)路網(wǎng)中的路段逐一搜索，篩選出能降低期望行程延誤的路段，組成超路徑.超路徑搜索結(jié)果還包括每個(gè)路段在超路徑集合中被選擇的概率，該概率可作為將流量分派到超路徑集合各路段上的比例[16].本文對(duì)原始的超路徑搜索算法做出改進(jìn)，對(duì)信號(hào)交叉口節(jié)點(diǎn)進(jìn)行擴(kuò)展，以路段的行駛時(shí)間與交叉口期望延誤之和最小為目標(biāo)函數(shù)，得到起訖點(diǎn)之間的超路徑結(jié)果.

原始的超路徑算法僅考慮路段延誤的不確定性，將其解釋為離開(kāi)其上游結(jié)點(diǎn)的延誤.當(dāng)考慮交叉口轉(zhuǎn)向延誤時(shí)，離開(kāi)結(jié)點(diǎn)的延誤將取決于車輛經(jīng)過(guò)交叉口的轉(zhuǎn)向行為.由交叉口西側(cè)和北側(cè)進(jìn)口道進(jìn)入交叉口的車輛，在從南側(cè)和東側(cè)出口道離開(kāi)時(shí)所受延誤影響會(huì)有明顯不同，即分別為右轉(zhuǎn)對(duì)應(yīng)直行和直行對(duì)應(yīng)左轉(zhuǎn).兩種轉(zhuǎn)向?qū)?yīng)的相位配時(shí)不同，所受延誤影響必然存在差異.基于此，本文在路網(wǎng)中對(duì)于有信號(hào)控制的交叉口節(jié)點(diǎn)進(jìn)行擴(kuò)展，克服了原始超路徑算法不能反映交叉口轉(zhuǎn)向阻抗的缺點(diǎn).本文采用網(wǎng)絡(luò)擴(kuò)展法表示交叉口的轉(zhuǎn)向行為，將交叉口的各個(gè)轉(zhuǎn)向抽象成虛擬路段，用這些路段阻抗代表交叉口轉(zhuǎn)向延誤[17].以圖1為例，對(duì)于單行車道，有四種轉(zhuǎn)向，引入四條虛擬路段；對(duì)于雙行車道，有十二種轉(zhuǎn)向，引入十二條虛擬路段.

圖1 道路交叉口的擴(kuò)展表示

在擴(kuò)展的道路網(wǎng)絡(luò)中，最優(yōu)超路徑問(wèn)題被描述為以路段行駛時(shí)間和交叉口期望延誤之和最小為目標(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)

對(duì)于擴(kuò)展的網(wǎng)絡(luò)，虛擬路段對(duì)應(yīng)于交叉口的轉(zhuǎn)向，其最大延誤dij由信號(hào)燈周期性變化引起，令其等于該轉(zhuǎn)向的非綠燈時(shí)長(zhǎng).本文假設(shè)車輛在隨機(jī)時(shí)刻到達(dá)交叉口，并定義交叉口轉(zhuǎn)向ri服務(wù)頻率fri(fri=1/dri).在超路徑中，對(duì)于任意交叉口進(jìn)口道節(jié)點(diǎn)i，可能存在多個(gè)可用的轉(zhuǎn)向ri，采用集合Ri表示該節(jié)點(diǎn)的全部可用轉(zhuǎn)向.進(jìn)一步，定義交叉口服務(wù)頻率fi=∑ri∈Rifri，則車輛在交叉口進(jìn)口道的等待時(shí)間期望wi為

(5)

式中：α∈(0,1]，α的取值取決于對(duì)交叉口信號(hào)配時(shí)的估計(jì)，在本文中假設(shè)α=1.

1.2 算法步驟

因此，本文的超路徑算法流程包括以下步驟：

步驟1指定起點(diǎn)r和終點(diǎn)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時(shí)，令fij=1/dij；當(dāng)dij=0時(shí)，令fij=∞.

步驟2查找集合L中(uj+cij)最小的路段(i,j)，作為當(dāng)前路段，并將其從集合L中移除.

步驟3若當(dāng)前路段滿足條件ui≥uj+cij，則進(jìn)入步驟4；否則，返回步驟2.

步驟4更新當(dāng)前路段(i,j)的上游節(jié)點(diǎn)i到終點(diǎn)s的考慮延誤的最短行駛時(shí)間ui.

若ui=∞，fi=0，則進(jìn)行如下運(yùn)算：

否則，進(jìn)行如下運(yùn)算：

步驟5更新節(jié)點(diǎn)i處的組合服務(wù)頻率變量和數(shù)據(jù)，作如下運(yùn)算：

fi=fi+fij

步驟6將當(dāng)前路段(i,j)加入到集合H中，此時(shí)，若滿足條件L=?或uj+cij≥ur，進(jìn)入步驟7；否則，返回步驟2.

步驟7求解路段及節(jié)點(diǎn)選擇概率：將網(wǎng)絡(luò)中的全部路段(i,j)，按照uj+cij的值，從大到小排序；根據(jù)排序后的順序遍歷全部路段，若路段(i,j)∈H，則進(jìn)行如下運(yùn)算：

否則，令pij=0.

從起點(diǎn)r開(kāi)始，追溯到達(dá)終點(diǎn)s的超路徑并輸出，用于路徑誘導(dǎo)決策.

1.3 算例

為了進(jìn)一步闡明超路徑算法的含義，采用方格網(wǎng)型的交通網(wǎng)絡(luò)并對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，見(jiàn)圖2.以點(diǎn)r為起點(diǎn)，點(diǎn)s為終點(diǎn)，除5、16外其余為信號(hào)燈控制的節(jié)點(diǎn)，網(wǎng)絡(luò)中共含有20個(gè)節(jié)點(diǎn)和31條雙車道路段，并將網(wǎng)絡(luò)圖進(jìn)行虛擬路段展開(kāi).圖3為路網(wǎng)中有信號(hào)控制的各交叉口的信號(hào)相位配時(shí)圖，表1為各路段的行程時(shí)間，表2為基于最大悲觀期望假設(shè)求得的各交叉口轉(zhuǎn)向的等待時(shí)間.

圖2 實(shí)例網(wǎng)絡(luò)圖

圖3 交叉口相位配時(shí)圖

表1 路段的行駛時(shí)間

基于最大悲觀期望假設(shè)，對(duì)于各轉(zhuǎn)向路段延誤的計(jì)算以圖2所示T型交叉口2為例進(jìn)行說(shuō)明.當(dāng)行駛路線的前向交叉口編號(hào)為r，后續(xù)交叉口編號(hào)為3時(shí)，車輛在交叉口2時(shí)需要直行.對(duì)照?qǐng)D3的相位圖，在交叉口2處的直行只屬于第一相位且在一個(gè)周期內(nèi)第一相位的綠燈時(shí)間是25 s，黃燈時(shí)間是5 s，紅燈時(shí)間是60 s.由于車輛在黃燈時(shí)間和紅燈時(shí)間內(nèi)停車等待，因此，確定執(zhí)行通過(guò)的轉(zhuǎn)向延誤為65 s.依照這個(gè)原理，推出圖2道路網(wǎng)絡(luò)中所有交叉口的轉(zhuǎn)向延誤，見(jiàn)表2.

表2 交叉口轉(zhuǎn)向的路段延誤

按算法步驟，篩選出超路徑，并在每條路段上標(biāo)注其被駕駛員選擇的概率，即誘導(dǎo)系統(tǒng)將車流量分配到各路段的比重，見(jiàn)圖4.

圖4 實(shí)例的路線概率圖

由路段概率得出可靠最短路徑一共有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.

算法運(yùn)行獲得的三組結(jié)果見(jiàn)圖5.由圖5可知，在獲取的多組解中，用戶可以選擇這3條出行路徑靈活地改變行進(jìn)路線，降低延誤時(shí)間.

圖5 實(shí)例的路線選擇圖

2 基于車路協(xié)同的超路徑誘導(dǎo)應(yīng)用

車路協(xié)同基于無(wú)線通信、傳感探測(cè)等技術(shù)獲取車輛和道路信息，通過(guò)車車、車路通信進(jìn)行信息交互和共享，實(shí)現(xiàn)車輛與基礎(chǔ)設(shè)施之間智能協(xié)同與配合[18].車路協(xié)同系統(tǒng)由智能交通管理系統(tǒng)、智能通信系統(tǒng)、智能車輛子系統(tǒng)和智能路側(cè)系統(tǒng)四個(gè)部分組成[19-20].智能交通管理系統(tǒng)處理由智能車輛子系統(tǒng)和智能路側(cè)系統(tǒng)獲取的信息，計(jì)算超路徑子網(wǎng)中包含的各轉(zhuǎn)向?qū)?yīng)的時(shí)間，具體分為以下兩種情況：

分析比較出時(shí)間最短的轉(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é)同信息交互

車輛在實(shí)際路況中行駛，超路徑誘導(dǎo)系統(tǒng)將進(jìn)行如下誘導(dǎo).在出發(fā)前，車輛路徑誘導(dǎo)系統(tǒng)為駕駛員篩選出圖4的超路徑子網(wǎng)，首先推薦駕駛員沿路段r-6行駛.具體流程如下.

步驟1當(dāng)車輛行駛接近交叉口6的通信范圍時(shí)，路側(cè)系統(tǒng)檢測(cè)到車輛駛?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、該交叉口信號(hào)燈當(dāng)前相位狀態(tài)信息，將這些信息傳輸給管理系統(tǒng).

步驟2智能車輛子系統(tǒng)從多路徑誘導(dǎo)方案中獲得在當(dāng)前交叉口的轉(zhuǎn)向策略集合S和車輛當(dāng)前位置，S包括直行和左轉(zhuǎn)，并將這些信息傳輸至智能交通管理系統(tǒng).

步驟3計(jì)算車輛到直行和左轉(zhuǎn)的停車線時(shí)間.

最后，根據(jù)判斷條件t左>t直，向智能車輛子系統(tǒng)遞直行轉(zhuǎn)向.

步驟3車輛子系統(tǒng)顯示路徑推薦，車輛接收直行指令，車輛會(huì)提前變道，駛離交叉口.

圖8為車路協(xié)同誘導(dǎo)示意.駕駛員依據(jù)圖5三組行駛路線進(jìn)行靈活的路線轉(zhuǎn)換.行駛至下一個(gè)路口時(shí)，超路徑誘導(dǎo)系統(tǒng)繼續(xù)根據(jù)“推薦優(yōu)先綠燈相位”的原則，從超路徑子網(wǎng)中搜索路徑推薦給駕駛員，直至行駛至目標(biāo)點(diǎn).全部交叉口誘導(dǎo)示意圖見(jiàn)圖9.

圖8 車路協(xié)同誘導(dǎo)示意圖

圖9 完整交叉口誘導(dǎo)示意圖

由此可見(jiàn)，在以超路徑算法為依托的車輛路徑誘導(dǎo)系統(tǒng)中，駕駛員在交叉口可以靈活變換行車路線，達(dá)到降低交叉口延誤的效果，從而實(shí)現(xiàn)“可靠最短”的出行目的.

基于1.3提出的超路徑搜索算法，并應(yīng)用上述車輛誘導(dǎo)方法，從網(wǎng)絡(luò)總體流量角度分析超路徑誘導(dǎo)方案的優(yōu)點(diǎn).假設(shè)某時(shí)段內(nèi)共計(jì)100名駕駛員從起點(diǎn)r行駛至終點(diǎn)s.分別沿超路徑算法篩選出來(lái)的三條路徑(見(jiàn)圖5)和時(shí)間最短的唯一路徑行駛，統(tǒng)計(jì)出車輛在交叉口的延誤情況，見(jiàn)表3.其中，車輛依據(jù)圖4的選擇比例計(jì)算結(jié)果，分配在超路徑中.

表3 超路徑和單路徑延誤時(shí)間對(duì)比

由表3的結(jié)果表明，在路網(wǎng)中應(yīng)用超路誘導(dǎo)系統(tǒng)，可降低21.9%的總體平均延誤.由此可見(jiàn)，采用超路徑誘導(dǎo)策略，可以實(shí)現(xiàn)流量在網(wǎng)絡(luò)中的合理分配，達(dá)到網(wǎng)絡(luò)整體車輛行程時(shí)間最短的目的.

3 結(jié) 束 語(yǔ)

本文基于交叉口信號(hào)配時(shí)提出了一種交叉口等待時(shí)間的計(jì)算方法，并用于超路徑搜索.基于最大悲觀期望假設(shè)利用信號(hào)配時(shí)方案求得交叉口各轉(zhuǎn)向最大等待時(shí)間，進(jìn)一步通過(guò)線性組合求出車輛在交叉口等待期望，避免了處理大量數(shù)據(jù)，加快了路徑誘導(dǎo)方案的搜索速度.在路徑誘導(dǎo)方面，提出了在車路協(xié)同環(huán)境下實(shí)現(xiàn)對(duì)優(yōu)先綠燈相位的判斷的解決方案，進(jìn)一步完善了超路徑誘導(dǎo)系統(tǒng)，達(dá)到了優(yōu)先推薦綠燈相位的目的.

對(duì)于個(gè)體而言，駕駛員可以通過(guò)誘導(dǎo)系統(tǒng)在超路徑子網(wǎng)中靈活改變行駛路線，實(shí)現(xiàn)達(dá)到降低行程延誤的目的.對(duì)于整體網(wǎng)絡(luò)而言，超路徑基于交叉口服務(wù)頻率來(lái)合理分配路段車流量，降低整體網(wǎng)絡(luò)的車輛行駛時(shí)間，提升交通網(wǎng)絡(luò)性能，會(huì)產(chǎn)生巨大的經(jīng)濟(jì)效益.隨著人們對(duì)個(gè)性化出行需求的增多，超路徑誘導(dǎo)系統(tǒng)可引入相應(yīng)的需求因子變更目標(biāo)函數(shù)，在提高網(wǎng)絡(luò)性能的同時(shí)，實(shí)現(xiàn)對(duì)用戶的個(gè)性化誘導(dǎo).同時(shí)，本文通過(guò)完善車路協(xié)同技術(shù)的判斷機(jī)制，實(shí)現(xiàn)了車路協(xié)同技術(shù)與超路徑誘導(dǎo)系統(tǒng)的結(jié)合，將在有效降低駕駛員行程延誤和完善智能交通誘導(dǎo)體系上發(fā)揮巨大作用.

本文基于信號(hào)配時(shí)計(jì)算車輛在交叉口的等待時(shí)間時(shí)，存在兩個(gè)假設(shè)條件：①最大悲觀期望假設(shè)，假設(shè)車輛在交叉口每個(gè)轉(zhuǎn)向的等待時(shí)間是紅燈加黃燈時(shí)間；②獨(dú)立性假設(shè)，假設(shè)車輛可選擇的相位相互獨(dú)立，計(jì)算在交叉口的期望等待時(shí)間時(shí)將各轉(zhuǎn)向等待時(shí)間線性組合.這兩個(gè)假設(shè)較為理想，可能會(huì)導(dǎo)致與實(shí)際情況存在一定偏差.今后的研究將上述假設(shè)條件做進(jìn)一步完善，使得超路徑搜索結(jié)果更加貼合實(shí)際路網(wǎng)情況.