劉明劍, 朱云鶴, 張思佳, 孫 華

(大連海洋大學(xué) 信息工程學(xué)院, 遼寧 大連 116023)

交叉路口是城市路網(wǎng)中重要的節(jié)點(diǎn)與樞紐,也是城市道路交通安全和擁堵頻發(fā)的瓶頸點(diǎn)[1-5]。隨著具備聯(lián)網(wǎng)功能和完全自動駕駛車輛(connected and automated vehicles,CAV)的出現(xiàn),在降低交叉路口交通事故和緩解擁堵方面,將發(fā)揮革命性作用[6]。目前,針對CAV的交叉路口管理系統(tǒng)研究主要分為兩類:①在傳統(tǒng)交通信號控制系統(tǒng)基礎(chǔ)上,利用CAV獲得高精度交通數(shù)據(jù),對信號控制系統(tǒng)相位和相序方案進(jìn)行調(diào)整來滿足智能車輛的通行需求;②拋棄傳統(tǒng)的信號控制方式,實(shí)現(xiàn)針對全自動駕駛車輛調(diào)度的無信號交叉路口管理模式。

在基于CAV的改進(jìn)傳統(tǒng)信號控制系統(tǒng)研究中,Li等[7]介紹了基于CAV信號控制系統(tǒng)的全局規(guī)劃、局部規(guī)劃以及自組織控制模式,通過數(shù)據(jù)分析,給出上述模式適用的不同交通情況。Guo等[8]將CAV獲得數(shù)據(jù)集成到信號控制系統(tǒng)中,根據(jù)CAV狀態(tài)信息對相位和相序進(jìn)行優(yōu)化,來提升交叉路口的通行效率。

雖然上述研究成果能夠在一定程度上提高CAV的通行效率,然而信號控制系統(tǒng)本質(zhì)是為人類駕駛車輛服務(wù),對于可以精確控制的CAV而言,執(zhí)行效率仍然過低。因此,一些研究機(jī)構(gòu)開始著眼于未來,研究適用于CAV的交叉路口控制系統(tǒng),其中起步較早的是德克薩斯大學(xué)奧斯丁分校Stone團(tuán)隊(duì)開發(fā)的自治交叉路口管理系統(tǒng)(autonomous intersection management,AIM)[9],研究者設(shè)計(jì)了性能較為優(yōu)秀的先來先服務(wù)(first come first served, FCFS)控制策略。并在此基礎(chǔ)上,相繼提出了多種高效的控制策略[10],包括支持人類駕駛車輛的FCFS-light控制策略和考慮緊急車輛通行的FCFS-emerg策略等。Vasirani等[11]也在AIM系統(tǒng)中以競價拍賣為核心思想,設(shè)計(jì)了基于組合拍賣的交叉路口控制策略。

隨后,基于車輛集中調(diào)度方式,Mahbub等[12]提出了在狀態(tài)和控制雙約束條件下進(jìn)行有效調(diào)度的交叉路口控制策略。Xu等[13]基于蒙特卡洛搜索方法,提出了協(xié)同駕駛控制策略,提高了交叉路口的通行效率。Zhu等[14]通過預(yù)測車輛可能到達(dá)延遲,建立了基于準(zhǔn)確預(yù)測車輛到達(dá)時間的交叉路口控制策略。劉明劍等[15]提出了基于禁忌搜索的交叉路口控制策略,通過消減車輛間沖突關(guān)系,來提升交叉路口的吞吐量。常玉林等[16]提出了基于蟻群算法的控制策略,通過分析交叉路口車流量情況,能夠更加準(zhǔn)確地搜索到車輛的最優(yōu)行駛路徑。Pei等[17]提出了一種基于動態(tài)規(guī)劃的多車協(xié)作控制策略。吳偉等[18]建立了基于混合整數(shù)線性規(guī)劃的交叉口控制策略。

利用分布式控制方式,蔣陽升等[19]提出了一種基于虛擬車隊(duì)的時序調(diào)度模型,實(shí)現(xiàn)了交叉路口調(diào)度的全局優(yōu)化。Gonzlez等[20]提出了一種多車分布式協(xié)作管理系統(tǒng),該系統(tǒng)通過引入明確的規(guī)則,讓車輛遵守規(guī)則來提高通行效率。Yesilyurt等[21]通過共享車輛在交叉路口中期望占據(jù)的行駛區(qū)域以及它們的預(yù)計(jì)到達(dá)時間,來協(xié)調(diào)車輛間通行順序。

也有學(xué)者利用深度學(xué)習(xí)方法開展了交叉路口調(diào)度的研究,Zhang等[22]提出了一種基于卷積神經(jīng)網(wǎng)絡(luò)的框架來預(yù)測不同車流密度下的車輛平均等待時間,進(jìn)而選擇耗時最少的方案作為調(diào)度策略。

FCFS目前仍然為一種高效的交叉路口控制策略,但FCFS控制策略缺乏對未來交叉路口車流量變化的考量,容易發(fā)生死鎖,決策過程中也存在一定的盲目性,不利于實(shí)現(xiàn)交叉路口中車輛吞吐量的最大化需求。交通信號控制策略是針對人類駕駛車輛設(shè)計(jì)的策略,對于能夠精確控制的CAV而言,存在執(zhí)行效率過低的問題;基于啟發(fā)式算法的交叉路口控制策略在車流量密度較大時容易陷入局部最優(yōu),無法進(jìn)一步提升交叉路口的通行效率。

為了解決上述交叉路口控制策略存在的問題,本文提出了一種基于最大團(tuán)自治交叉路口控制策略,在保證系統(tǒng)實(shí)時性需求的前提下,提高了交叉路口的通行效率,最后通過仿真實(shí)驗(yàn)證明了控制策略的有效性與可靠性。

1 問題描述與建模

自治交叉路口控制系統(tǒng)是服務(wù)于具備完全自動駕駛功能CAV的交叉路口控制系統(tǒng)。首先,CAV進(jìn)入交叉路口區(qū)域,開始向路側(cè)單元發(fā)送預(yù)約通過交叉路口的請求;其次,路側(cè)單元根據(jù)接收到的預(yù)約請求信息,模擬出車輛的行駛軌跡;再次,控制系統(tǒng)依據(jù)相應(yīng)控制策略,給出CAV在交叉路口中的通行順序;最后,CAV駛離交叉路口區(qū)域,中斷與路側(cè)單元之間通信。交叉路口控制系統(tǒng)如圖1所示。

圖1 交叉路口控制系統(tǒng)

1.1 自治交叉路口控制系統(tǒng)的處理機(jī)制

(1) 交叉路口空間區(qū)域劃分機(jī)制。將矩形的交叉路口空間區(qū)域S進(jìn)行網(wǎng)格化劃分處理,劃分為g2個二維空間小區(qū)域網(wǎng)格。劃分之后路口的第i個小區(qū)域網(wǎng)格為si,那么整個交叉路口S可以看作是由si組成的有限集合,如圖1所示。

S={si|1≤i≤g2,g∈N+}。

(1)

(2) 交叉路口時間批處理機(jī)制。定義整個交叉路口控制系統(tǒng)的離散時間域?yàn)門,將其等量切分后每個處理周期為Ti,整個控制系統(tǒng)的時間軸T是由批處理周期Ti組成的無限集合:

T={T1,T2,…,Ti,Ti+1,…,Tk}。

(2)

在每一個批處理周期Ti,自治交叉路口控制系統(tǒng)接收到預(yù)約過交叉路口的車輛請求集合為R:

R={vi|1≤i≤n,m∈N+}。

(3)

從R集合中選取可以通過交叉路口的車輛請求集合為Rac:

Rac={vi|1≤i≤m≤n,n、m∈N+},Rac?R。

(4)

1.2 控制系統(tǒng)建模

為了提高自治交叉路口的通行效率,并保證行車安全,需要確保在每一個批處理周期,預(yù)約通過交叉路口的任意兩輛車之間均不存在沖突關(guān)系,即車輛vi和vj(i≠j)在交叉路口行駛過程中,任意時刻均不能占用相同的一個或一組小網(wǎng)格交叉路口空間區(qū)域。

通過以上分析,建立每個批處理周期自治交叉路口求解的目標(biāo)函數(shù)f,即在集合R選取最大車輛預(yù)約請求集合maxRac:

(5)

2 求解算法

2.1 基于最大團(tuán)的自治交叉路口控制問題描述

基于第1節(jié)分析的車輛間的沖突關(guān)系可以建立車輛間沖突關(guān)系圖,即節(jié)點(diǎn)(CAV)以及弧(車輛間的沖突關(guān)系)組成的沖突關(guān)系圖G=(V,E),其中V為圖G中車輛預(yù)約請求集合Rall的車輛節(jié)點(diǎn)集;E則為車輛沖突關(guān)系的集合,即存在預(yù)約請求沖突關(guān)系的車輛節(jié)點(diǎn)之間有邊連接。自治交叉路口控制系統(tǒng)流程如圖2所示。

圖2 控制系統(tǒng)整體流程

2.2 基于最大團(tuán)的自治交叉路口控制策略

尋找最大相容車輛節(jié)點(diǎn)集合maxRac的3個子階段如下。

(1) 隨機(jī)選擇車輛預(yù)約請求節(jié)點(diǎn)階段:隨機(jī)從集合中選擇一個車輛預(yù)約請求節(jié)點(diǎn),對選擇車輛節(jié)點(diǎn)性質(zhì)沒有傾向性。

(2) 選擇最大度的車輛預(yù)約請求節(jié)點(diǎn)階段:從集合中選擇一個具有最大度的車輛預(yù)約請求結(jié)點(diǎn)(初始時計(jì)算)。

(3) 選擇懲罰節(jié)點(diǎn)階段:加入節(jié)點(diǎn)懲罰機(jī)制,使得搜索過程多樣化,避免搜索停滯,基于貪心算法,越頻繁加入當(dāng)前團(tuán)的點(diǎn),則在未來選擇過程中越不容易被重新選擇。

NDMC控制策略3個子階段運(yùn)行完成之后,輸出最終接受車輛數(shù)集合Rac,即本周期內(nèi)找到的最大接受請求車輛集合。

3 實(shí)驗(yàn)與分析

為了對本研究提出的基于最大團(tuán)的自治交叉路口控制策略的準(zhǔn)確性和執(zhí)行效率進(jìn)行驗(yàn)證,在開源自治交叉路口仿真平臺AIM[12]中,設(shè)定在平衡與不平衡2種車流量情況下對NDMC控制策略、FCFS控制策略、基于禁忌搜索控制策略(Tabu)[15]以及交通信號控制策略(traffic-light)的性能進(jìn)行了對比評估。

3.1 實(shí)驗(yàn)仿真設(shè)定

(1)仿真參數(shù)設(shè)定。在AIM系統(tǒng)中,設(shè)定一個雙向六車道正方形交叉路口區(qū)域(g=12)[12],單條車道寬度設(shè)定為3.25 m;生成車輛數(shù)量分布服從泊松分布,交通流分布服從Greenshields模型,車輛行駛速度依據(jù)車流量變化進(jìn)行調(diào)整;交通路口通信范圍為以交叉路口中心點(diǎn)位半徑的300 m區(qū)域;車型為2種并按照2點(diǎn)分布生成(小型車尺寸為4.30 m×2.35 m,生成概率為0.8;大型車尺寸為10.0 m×2.5 m,生成概率為0.2)?？刂葡到y(tǒng)的時間仿真步為0.02 s,時間片的劃分與仿真步保持一致,系統(tǒng)批處理周期為2 s,實(shí)驗(yàn)的執(zhí)行時間均為1 h。

3.2 平衡車流下控制策略性能評估實(shí)驗(yàn)

在AIM仿真平臺中,平衡車流量情況表示進(jìn)入交叉路口4個方向上車流量基本相當(dāng)。

(1)車輛排隊(duì)情況分析。交叉路口各個駛?cè)敕较蛏宪囕v到達(dá)服從數(shù)學(xué)期望λ相一致的泊松分布,不失一般性,λ分別取值為0.100、0.125、0.150、0.175。統(tǒng)計(jì)2 min內(nèi)交叉路口中車輛的排隊(duì)情況。如圖3所示,NDMC控制策略當(dāng)λ取值為0.100、0.125、0.150時排隊(duì)總數(shù)低于26輛;而當(dāng)λ=0.175時,車輛排隊(duì)數(shù)呈增加趨勢,但也維持在80輛之內(nèi),顯示出了較強(qiáng)的魯棒性。

圖3 服從泊松分布取不同λ值的車輛排隊(duì)長度對比

(2)平衡車流量情況下對比情況。在每個交叉路口進(jìn)入方向的每條車道起始處依據(jù)泊松分布生成車流,車輛密度ω從0輛/h變化到2 500輛/h,車輛前進(jìn)方向依據(jù)交通規(guī)則基礎(chǔ)上按照隨機(jī)規(guī)則生成(如最右側(cè)車道,車輛有直行或右轉(zhuǎn)彎2種前進(jìn)方向)。交通信號控制策略采用固定的相位配時方案,如表1所示。

表1 傳統(tǒng)交通信號控制的相位配時

圖4為本文策略與其他策略性能對比情況。如圖4(a)所示,隨著車流量密度增加,FCFS控制策略發(fā)生死鎖次數(shù)也隨之增加,車輛完成數(shù)方面增加較為緩慢,當(dāng)車流量密度小于500 輛/h時,NDMC控制策略與其他策略性能基本相當(dāng);當(dāng)車輛密度大于1 000輛/h時,NDMC控制策略優(yōu)于其他策略。當(dāng)車流量密度小于240輛/h時,NDMC控制策略與其他策略的平均等待時間均維持在可接受范圍內(nèi);當(dāng)流量密度超過300輛/h時,FCFS控制策略的平均等待時間出現(xiàn)了大幅度增加;當(dāng)車輛密度超過2 000輛/h時,NDMC控制策略的平均等待時間低于其他控制策略。

圖4 平衡車流下不同策略性能對比情況

隨后,在平衡車流量情況下,對NDMC控制策略服務(wù)車輛數(shù)和拒絕車輛數(shù)情況進(jìn)行評估,如圖5所示。NDMC控制策略服務(wù)車輛數(shù)即車輛完成數(shù)隨著車流量密度增加呈現(xiàn)出增加趨勢,當(dāng)車輛密度大于1 000輛/h時,增加趨勢減緩;拒絕車輛數(shù)也隨著車輛密度增加而提高,當(dāng)車輛密度為2 500輛/h時,拒絕的車輛數(shù)為3 656輛次,呈現(xiàn)出逐漸增加趨勢。這是因?yàn)殡S著車流量密度增加,每個周期內(nèi)請求數(shù)在增多,導(dǎo)致每個周期找到最優(yōu)解即最大團(tuán)的效率逐步降低。

圖5 車輛完成數(shù)和拒絕數(shù)對比分析

3.3 不平衡車流下控制策略性能評估實(shí)驗(yàn)

在交叉路口東西進(jìn)入方向車流量ω從0輛/h變化到2 500輛/h,南北兩進(jìn)入方向的車流量密度維持1 500輛/h,其他參數(shù)設(shè)置與平衡車流下實(shí)驗(yàn)設(shè)置相同。

圖6為不平衡車流下車輛平均等待時間。如圖6(a)所示,FCFS策略的車輛平均等待時間指標(biāo)受不平衡車流影響最為明顯。當(dāng)車輛密度超過500輛/h時,本文策略和Tabu控制策略性能基本相當(dāng),優(yōu)于其他控制策略;當(dāng)車輛密度超過1 600輛/h時,NDMC策略平均等待時間要低于其他策略。圖6(b)繪制了NDMC和FCFS控制策略在交叉路口南北方向和東西方向上的車輛平均等待時間對比情況。在NDMC控制策略中,南北方向車輛產(chǎn)生的平均等待時間高于東西方向車輛所產(chǎn)生平均等待時間,但仍然優(yōu)于FCFS控制策略。

圖6 不平衡車流下車輛平均等待時間對比

綜上,為了對本文控制策略的執(zhí)行效率進(jìn)行評估,首先,評估了服從泊松分布不同λ取值的車輛排隊(duì)長度的變化情況,證明該策略有較強(qiáng)魯棒性;其次,與FCFS、Tabu和traffic-light控制策略在車輛完成數(shù)和車輛平均等待時間2個方面進(jìn)行了對比評估,實(shí)驗(yàn)結(jié)果表明:本文控制策略性能均優(yōu)于上述控制策略。證明了本文路口控制策略的有效性與可靠性。

4 結(jié)論

本文基于最大團(tuán)理論提出了一種自治交叉路口控制策略。首先,對車輛在交叉路口中行駛的時空軌跡進(jìn)行建模;其次,根據(jù)車輛間的時空行駛軌跡建立車輛間的沖突關(guān)系模型,并將車輛間沖突關(guān)系抽象成圖;最后,通過在每個批處理周期內(nèi)求解沖突關(guān)系圖中最大團(tuán)的補(bǔ)集作為接受車輛預(yù)約請求集合,使得在單位時間內(nèi)更多車輛能夠通過交叉路口,達(dá)到降低車輛平均延時和提高交叉路口吞吐量的目標(biāo)。

與當(dāng)前研究成果相比,本研究的工作主要體現(xiàn)在兩個方面:①為了降低自治交叉路口控制系統(tǒng)的計(jì)算復(fù)雜度,將路口區(qū)域進(jìn)行網(wǎng)格化處理,同時將控制系統(tǒng)時間軸進(jìn)行切分,劃分成等量批處理周期;②使用最大團(tuán)理論來求解自治交叉路口控制問題,該方法自適應(yīng)能力強(qiáng),在不同車流量情況均能獲得較優(yōu)的解,能使得更多車輛安全通過交叉路口。

本文是在系統(tǒng)運(yùn)行正常和通信理想情況下進(jìn)行相關(guān)研究,沒有考慮了車輛發(fā)生故障無法移動以及通信不暢等情況,因此未來工作設(shè)計(jì)一種在無線通信環(huán)境下仍能高效運(yùn)行的路口控制策略,在更加趨近于真實(shí)交叉路口的交通環(huán)境中保證行車安全,提高自治交叉路口的通行效率。