基于最大團(tuán)理論的自治交叉路口控制方法

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

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

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

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

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

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

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

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

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

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

1 問(wèn)題描述與建模

自治交叉路口控制系統(tǒng)是服務(wù)于具備完全自動(dòng)駕駛功能CAV的交叉路口控制系統(tǒng)。首先,CAV進(jìn)入交叉路口區(qū)域,開始向路側(cè)單元發(fā)送預(yù)約通過(guò)交叉路口的請(qǐng)求;其次,路側(cè)單元根據(jù)接收到的預(yù)約請(qǐng)求信息,模擬出車輛的行駛軌跡;再次,控制系統(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個(gè)二維空間小區(qū)域網(wǎng)格。劃分之后路口的第i個(gè)小區(qū)域網(wǎng)格為si,那么整個(gè)交叉路口S可以看作是由si組成的有限集合,如圖1所示。

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

(1)

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

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

(2)

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

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

(3)

從R集合中選取可以通過(guò)交叉路口的車輛請(qǐng)求集合為Rac:

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

(4)

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

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

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

(5)

2 求解算法

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

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

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

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

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

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

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

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

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

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

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

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

(1)仿真參數(shù)設(shè)定。在AIM系統(tǒng)中,設(shè)定一個(gè)雙向六車道正方形交叉路口區(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)的時(shí)間仿真步為0.02 s,時(shí)間片的劃分與仿真步保持一致,系統(tǒng)批處理周期為2 s,實(shí)驗(yàn)的執(zhí)行時(shí)間均為1 h。

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

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

(1)車輛排隊(duì)情況分析。交叉路口各個(gè)駛?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時(shí)排隊(duì)總數(shù)低于26輛;而當(dāng)λ=0.175時(shí),車輛排隊(duì)數(shù)呈增加趨勢(shì),但也維持在80輛之內(nèi),顯示出了較強(qiáng)的魯棒性。

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

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

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

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

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

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

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

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

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

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

圖6 不平衡車流下車輛平均等待時(shí)間對(duì)比

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

4 結(jié)論

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

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

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