考慮信號(hào)交叉口延時(shí)的最優(yōu)車輛路徑規(guī)劃算法?

胡 林，鐘遠(yuǎn)興，黃 晶，杜榮華，張 新

(1.長沙理工大學(xué)汽車與機(jī)械工程學(xué)院，長沙 410114； 2.湖南大學(xué)，汽車車身先進(jìn)設(shè)計(jì)制造國家重點(diǎn)實(shí)驗(yàn)室，長沙 410082；3.長沙理工大學(xué)，工程車輛安全性設(shè)計(jì)與可靠性技術(shù)湖南省重點(diǎn)實(shí)驗(yàn)室，長沙 410114)

前言

隨著智能交通(ITS)的發(fā)展，最短路徑規(guī)劃已成為解決道路交通擁堵和交通安全的一項(xiàng)重要途徑。同時(shí)，隨著科技的發(fā)展，車聯(lián)網(wǎng)(V2V)和車路協(xié)同(V2I)技術(shù)在提高道路交通運(yùn)輸?shù)陌踩?、環(huán)保和可靠性等方面得到了大量應(yīng)用。而在城市道路網(wǎng)中，由于信號(hào)交叉口(指設(shè)置有交通信號(hào)燈的交叉口，下同)的大量存在，進(jìn)一步加劇了交通擁堵和交通延時(shí)，并造成嚴(yán)重的環(huán)境污染。通過在車輛上安裝無線通信設(shè)備，使其能與鄰近車輛和道路基礎(chǔ)設(shè)施進(jìn)行通信，可以輔助車輛安全、環(huán)保和快速地通過交叉口。因此，在動(dòng)態(tài)路徑規(guī)劃研究中，有必要將車聯(lián)網(wǎng)和車路協(xié)同技術(shù)與交叉口的等待時(shí)間結(jié)合起來考慮。

現(xiàn)有路徑規(guī)劃中，國內(nèi)外學(xué)者對(duì)信號(hào)交叉口延時(shí)進(jìn)行了大量研究[1-4]。YANG和Miller-Hooks[5]分析了隨機(jī)時(shí)變路網(wǎng)中由于信號(hào)燈導(dǎo)致的額外延時(shí)。Khanjary等[6]提出了同步交通燈路網(wǎng)中考慮街道通行時(shí)間和綠燈等待時(shí)間的標(biāo)號(hào)設(shè)定算法。楊帆等[7]提出了信號(hào)交叉口處等待時(shí)間函數(shù)，并將其引入算法中，建立新的標(biāo)號(hào)算法。周熙陽等[8]在此基礎(chǔ)上，針對(duì)不同轉(zhuǎn)向類型構(gòu)建信號(hào)交叉口等待時(shí)間模型，提出了考慮信號(hào)交叉口轉(zhuǎn)向類型的CMTA?算法。但該算法要求確定出發(fā)時(shí)刻，預(yù)知所有交叉口交通燈的當(dāng)前相位時(shí)間點(diǎn)，假定路段行程時(shí)間固定并忽略車輛路段行駛延誤，難以實(shí)際應(yīng)用。

此外，對(duì)車輛通過交叉口的速度優(yōu)化也進(jìn)行了廣泛的研究[9-11]。Mandava等[12]提出在通過車輛與道路設(shè)施的通信預(yù)先獲取前方交通燈信號(hào)相位和配時(shí)信息的基礎(chǔ)上，對(duì)車輛進(jìn)行動(dòng)態(tài)速度規(guī)劃，使車輛盡可能避免加速、減速和怠速狀態(tài)，降低車輛的油耗和尾氣排放。Rakha等[13]提出了旨在提高燃油效率的環(huán)保駕駛框架，通過車輛與道路設(shè)施的通信提前獲取交通燈信號(hào)相位和配時(shí)信息，用以調(diào)整車輛通過交叉口的策略，從而達(dá)到降低車輛油耗的目的。Butakov等[14]則結(jié)合駕駛員的偏好和習(xí)慣對(duì)車輛通過交叉口的速度進(jìn)行優(yōu)化，從而降低油耗，縮短等待時(shí)間。安實(shí)等[15]提出了一種基于多級(jí)可變速度限制的信號(hào)交叉口綠色駕駛控制方法，以信號(hào)交叉口為背景，對(duì)車隊(duì)中的頭車進(jìn)行速度限制。林培群等[16]在分析車聯(lián)網(wǎng)環(huán)境技術(shù)特征的基礎(chǔ)上提出交叉口交通流分區(qū)控制思想(變速控制區(qū)和勻速控制區(qū))，并建立系統(tǒng)優(yōu)化的數(shù)學(xué)模型。徐彪等[17]構(gòu)建了基于DSRC的連續(xù)交叉路口通行輔助系統(tǒng)，并提出了連續(xù)交叉路口的通行車速計(jì)算方法。

綜上所述，現(xiàn)有考慮交叉口等待時(shí)間的路徑規(guī)劃研究未對(duì)車輛通過交叉口的速度進(jìn)行優(yōu)化，而聚焦于對(duì)車輛通過交叉口的速度進(jìn)行優(yōu)化的研究也未將其與全路段的路徑規(guī)劃結(jié)合起來。本文中擬將信號(hào)交叉口的等待時(shí)間和車輛加速通過交叉口結(jié)合起來，提出考慮快速通過交叉口的最短路徑規(guī)劃算法。首先，根據(jù)浮動(dòng)車數(shù)據(jù)獲取路網(wǎng)中各路段的車輛平均行駛速度。然后，建立基于馬爾科夫鏈的交通燈轉(zhuǎn)換模型，并通過車輛加速通過交叉口來考慮綠燈時(shí)間的延長，以此構(gòu)建車輛快速通過交叉口的等待時(shí)間模型。最后，結(jié)合A?算法，提出一種考慮快速通過交叉口的等待時(shí)間的改進(jìn)A?算法。

1 最優(yōu)車輛路徑規(guī)劃算法

1.1 路網(wǎng)模型構(gòu)建

在動(dòng)態(tài)分時(shí)路網(wǎng)[18]的基礎(chǔ)上構(gòu)建城市道路網(wǎng)模型，以 G＝(N，D，V，T)表征路網(wǎng)，其中 N＝{1，…，n}表示節(jié)點(diǎn)集合(即交叉口)，D＝{dij(t)｜(i，j)∈N}表示連接各節(jié)點(diǎn)之間的弧段長度，V＝{Vij(t)｜(i，j)∈N}表示各弧段的實(shí)時(shí)速度，T表示車輛從起點(diǎn)到終點(diǎn)的行程時(shí)間。城市路網(wǎng)中，車輛的行程時(shí)間主要由路段行駛時(shí)間和信號(hào)交叉口等待時(shí)間組成。節(jié)點(diǎn)i到j(luò)的行程時(shí)間包括路段dij的行駛時(shí)間和交叉口j的等待時(shí)間，如圖1所示，即有

式中:dij和Vij分別為交叉口i到交叉口j之間路段的距離和車輛平均速度；Wj為車輛在交叉口j處的等待時(shí)間。

圖1 車輛通過交叉口示意圖

1.2 路段行程時(shí)間計(jì)算

現(xiàn)在，越來越多的車輛上安裝了衛(wèi)星導(dǎo)航和無線通信設(shè)備，通過車上安裝的衛(wèi)星導(dǎo)航模塊和通信模塊，定期向信息中心發(fā)送車輛位置、速度和時(shí)間信息，對(duì)這些信息進(jìn)行分析處理可實(shí)時(shí)獲取各路段的交通流信息。假設(shè)t時(shí)刻一條道路上的浮動(dòng)車輛數(shù)為 n，每輛車的瞬時(shí)速度為 Vi(i＝1，2，…，n)，則該路段在t時(shí)刻的車輛平均速度為

將衛(wèi)星導(dǎo)航數(shù)據(jù)與地圖進(jìn)行匹配[19]，可得到每一路段dij的車輛實(shí)時(shí)速度Vij，則各路段的行程時(shí)

1.3 基于馬爾科夫鏈的交通燈模型

對(duì)于一個(gè)4相位的信號(hào)控制交叉口(周期時(shí)長為Tc)，其中每一相位所對(duì)應(yīng)行駛方向的交通燈有兩個(gè)狀態(tài)，即紅燈和綠燈狀態(tài)(為簡化計(jì)算，將黃燈時(shí)間納入紅燈狀態(tài))，如圖2所示。紅燈和綠燈交替轉(zhuǎn)換的過程可看成一個(gè)按兩態(tài)連續(xù)時(shí)間馬爾科夫鏈規(guī)律轉(zhuǎn)變的過程。下一時(shí)段交通燈的狀態(tài)與過去的情況無關(guān)，只取決于當(dāng)前狀態(tài)，具有明顯的馬爾科夫性質(zhì)。

圖2 交通燈相位示意圖

計(jì)算交通信號(hào)燈穩(wěn)態(tài)概率分布的步驟如下。

(1)確定狀態(tài)轉(zhuǎn)移概率矩陣Pij(t)

定義Xij(t)為車輛在路段(i，j)行駛時(shí)前方交通燈j的狀態(tài)。Xij(t)＝g時(shí)，車輛無需等待；Xij(t)＝r時(shí)，車輛需要等待下一周期綠燈的到來。

假設(shè)當(dāng)前狀態(tài)為綠燈，記為狀態(tài)g(綠燈時(shí)長為g)，綠燈結(jié)束后轉(zhuǎn)為紅燈狀態(tài)，記為狀態(tài)r(紅燈時(shí)長為r)。當(dāng)前狀態(tài)為g下一刻(經(jīng)過t)狀態(tài)仍為g的概率為Pgijg(t)，即有

相應(yīng)地定義當(dāng)前時(shí)刻為綠燈下一刻轉(zhuǎn)為紅燈、當(dāng)前為紅燈下一刻仍為紅燈和當(dāng)前為紅燈下一刻轉(zhuǎn)為綠燈的概率分別為t)，(t)和t)。

式中:Pr為交通燈是紅燈狀態(tài)的穩(wěn)態(tài)概率；Pg為交通燈是綠燈狀態(tài)的穩(wěn)態(tài)概率。

1.4 車輛加速通過信號(hào)交叉口模型

車輛通過交叉路口示意圖如圖3所示。由圖可見:當(dāng)前方交通燈為綠燈狀態(tài)且綠燈剩余時(shí)間足夠時(shí)，車輛無需等待，以路段實(shí)時(shí)平均速度Vi通過交叉口；當(dāng)前方交通燈狀態(tài)為紅燈時(shí)，車輛需要等待綠燈相位的到來。通過車路協(xié)同方式(V2I)，車輛在與前方交叉口距離S時(shí)就能知道交通燈的當(dāng)前相位及其剩余時(shí)間。這樣，當(dāng)前方交通燈即將由綠燈轉(zhuǎn)變?yōu)榧t燈時(shí)，車輛可加速通過以避免交叉口的等待。假設(shè)車輛距離交叉口停止線為S時(shí)，車輛以速度Vi行駛，到達(dá)停車線的時(shí)刻為t2；車輛以加速度a1加速到最大速度Vmax行駛時(shí)，到達(dá)停車線的時(shí)刻為t1，則有

圖3 車輛通過交叉口示意圖

(2)確定穩(wěn)態(tài)概率P

由馬爾科夫鏈的無記憶性規(guī)律可知，穩(wěn)態(tài)概率只取決于交通燈狀態(tài)轉(zhuǎn)移概率矩陣Pij，與初始狀態(tài)無關(guān)?？汕蟮梅€(wěn)態(tài)概率為

值得注意的是，當(dāng)車輛加速通過前方交叉口時(shí)，須考慮車輛前方是否有車和前車與本車的車頭間距(本文中不考慮超車的情況)。本車與前車的車頭時(shí)距示意圖如圖4所示。由圖可見，本車距離前方交叉口S時(shí)加速到最大速度Vmax行駛，經(jīng)過t1時(shí)間車輛剛好駛過停車線，若前方有車且以速度Vi行駛，本車與前車的車頭間距L應(yīng)滿足:

式中:d為本車通過交叉口停止線時(shí)與前車的最小安全車距；a2為車輛的減速度，本車通過交叉口停止線后即減速至路段平均車速；D為車輛跟馳的最小車距。

圖4 本車與前車的車頭時(shí)距示意圖

車頭時(shí)距t為

1.5 車頭時(shí)距的確定

當(dāng)本車與前車的車頭時(shí)距較大時(shí)，本車可加速通過交叉口以避免停車等待；當(dāng)本車與前車的車頭時(shí)距較小時(shí)，本車不能加速通過交叉口。根據(jù)信號(hào)交叉口處的車輛到達(dá)規(guī)律[20]可知，車頭時(shí)距的分布模型有負(fù)指數(shù)模型、移位負(fù)指數(shù)模型、威布爾模型和愛爾朗模型等。本文中采用三參數(shù)的威布爾分布模型來描述車頭時(shí)距的分布。

根據(jù)威布爾分布提出的車頭時(shí)距大于等于臨界車頭時(shí)距的概率分布:

式中:P(h≥t)為相鄰兩車的車頭時(shí)距h大于或等于臨界車頭時(shí)距t的概率；α，β和γ為分布參數(shù)，α為起點(diǎn)參數(shù)，β為形狀參數(shù)，γ為尺度參數(shù)。

威布爾分布的概率密度函數(shù)為

圖5為采用MATLAB繪制的不同分布參數(shù)下的威布爾概率密度曲線。

根據(jù)不同車流對(duì)應(yīng)的車頭時(shí)距分布，可得該車流產(chǎn)生的大于臨界間距的概率為

圖5 威布爾分布概率密度曲線

通過對(duì)各交叉口的車輛到達(dá)規(guī)律進(jìn)行統(tǒng)計(jì)分析，采用MATLAB對(duì)車頭時(shí)距的分布函數(shù)進(jìn)行擬合，即可算出不同交叉口到達(dá)車流大于所需臨界間距的概率。

圖6為某交叉口特定時(shí)間段內(nèi)車頭時(shí)距的統(tǒng)計(jì)分布及其概率密度曲線，其分布參數(shù)分別為:α＝2.440，β＝2.661，γ＝0.342。

圖6 車頭時(shí)距概率密度分布

1.6 考慮快速通過信號(hào)交叉口的車輛等待時(shí)間

由于車輛到達(dá)交叉口的隨機(jī)性和不確定性，可假定在交通燈信號(hào)周期內(nèi)的各個(gè)時(shí)刻車輛到達(dá)交叉口的概率是均等的。當(dāng)前方交通燈為綠燈狀態(tài)時(shí)，車輛等待時(shí)間為0；當(dāng)前方交通燈為紅燈狀態(tài)時(shí)，車輛需等到紅燈結(jié)束綠燈啟亮?xí)r才能通行，根據(jù)概率，等待時(shí)間約等于紅燈時(shí)間的一半。

考慮當(dāng)前方交通燈即將由綠燈變?yōu)榧t燈，同時(shí)車頭時(shí)距滿足要求時(shí)，車輛可以在該綠燈相位時(shí)間內(nèi)快速通過交叉口，可理解為對(duì)綠燈時(shí)間的拓展。故可將交通燈穩(wěn)態(tài)概率(Pr，Pg)修正為(P′r，P′g)。其中 P′r和 P′g分別為

此外，車輛通過交叉口后的行駛方向可分為直行、左轉(zhuǎn)和右轉(zhuǎn)，本文中假定右轉(zhuǎn)無專用相位，故當(dāng)選擇右轉(zhuǎn)時(shí)，車輛在信號(hào)交叉口的等待時(shí)間為0。

圖7 算例路網(wǎng)

表1 算例路網(wǎng)中各路段長度 m

1.7 實(shí)時(shí)最短路徑算法

A?算法[21]是求解最短路徑最有效的直接搜索方法，它通過構(gòu)造啟發(fā)式函數(shù)來尋找從起點(diǎn)到終點(diǎn)代價(jià)最小的節(jié)點(diǎn)。對(duì)于節(jié)點(diǎn)n的估價(jià)函數(shù)的一般形式為

式中:g(n)為起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的實(shí)際代價(jià)；h(n)為當(dāng)前節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的估計(jì)代價(jià)。

對(duì)A?算法進(jìn)行拓展，在A?算法的基礎(chǔ)上考慮快速通過交叉口的等待時(shí)間，得到的估價(jià)函數(shù)為

式中:f(j)為弧節(jié)點(diǎn)j的估計(jì)代價(jià)；g(j)為從初始弧節(jié)點(diǎn)到達(dá)弧節(jié)點(diǎn)j的實(shí)際代價(jià)；g(i)為從初始弧節(jié)點(diǎn)到達(dá)弧節(jié)點(diǎn)i的實(shí)際代價(jià)；dij為路段(i，j)的長度；Vij為路段(i，j)的平均車速；Wj為信號(hào)交叉口j的等待時(shí)間；D(j)為弧節(jié)點(diǎn)j到目標(biāo)節(jié)點(diǎn)的歐式距離；Vmax為路網(wǎng)最高限速值。

2 仿真分析

首先，設(shè)計(jì)一個(gè)簡單路網(wǎng)來闡述本文算法的實(shí)現(xiàn)過程。該路網(wǎng)包含了25個(gè)交叉口和40條路段，如圖7所示，算例設(shè)置如下。

(1)路網(wǎng)的40條路段均為雙向通行，路網(wǎng)的最高限速為60km/h，各路段長度如表1所示。路網(wǎng)中各路段車輛的平均通行速度實(shí)時(shí)更新，圖中黑色路段(7-8，8-13，17-18 和18-19)代表擁堵路段，其平均通行速度為25km/h，灰色路段(9-14)為基本暢通路段，其平均通行速度為35km/h，其余路段為暢通路段，平均通行速度為45km/h。

(2)試驗(yàn)車輛與各交叉口的交通燈進(jìn)行通信，通信距離設(shè)為200m，車輛在該距離范圍內(nèi)可獲取前方交通燈的實(shí)時(shí)相位及其剩余時(shí)間。

(3)交叉口各信號(hào)相位相互獨(dú)立、已知且固定，部分交叉口信號(hào)配時(shí)參數(shù)如表2所示。

表2 各節(jié)點(diǎn)交叉口信號(hào)配時(shí)表

(4)交叉口的到達(dá)車流符合分布參數(shù)為α＝2.2，β＝2.5和γ＝1.7的威布爾分布，其概率密度曲線如圖8所示。

圖8 威布爾概率密度曲線

根據(jù)本文中提出的算法計(jì)算所得路徑為:21-16-11-6-1-2-3-4-5，路徑包含了7個(gè)交叉口，其中一個(gè)右轉(zhuǎn)，6個(gè)直行，路段總長為4.65km。由各信號(hào)交叉口的相位配時(shí)參數(shù)可計(jì)算出各交通燈紅燈、綠燈狀態(tài)的穩(wěn)態(tài)分布概率，當(dāng)信號(hào)燈即將由綠燈變?yōu)榧t燈時(shí)，位于信號(hào)交叉口距離S范圍內(nèi)的車輛可加速到最大限速通過交叉口，結(jié)合所需車頭時(shí)距的概率可求出當(dāng)前交通燈的綠燈拓展時(shí)間，進(jìn)而求出車輛在各個(gè)信號(hào)交叉口的等待時(shí)間，如表3所示。最后，將交叉口等待時(shí)間加上路段行駛時(shí)間可得到車輛通過路徑的總時(shí)間為535.9s。

表3 各節(jié)點(diǎn)交叉口等待時(shí)間s

為仿真真實(shí)場(chǎng)景，本文中通過開源地圖Open-StreetMap下載長沙市某片區(qū)地圖作為算例路網(wǎng)，該路網(wǎng)包含路段65條，節(jié)點(diǎn)40個(gè)。采用Visual C++6.0對(duì)算法進(jìn)行編程實(shí)現(xiàn)，并通過城市交通仿真軟件SUMO[22]進(jìn)行仿真。

使用傳統(tǒng)A?算法所得路徑如圖9中虛線所示，路徑包括7個(gè)交叉口，其中1個(gè)左轉(zhuǎn)，1個(gè)右轉(zhuǎn)，5個(gè)直行，路段總長為3.42km，通行所用時(shí)間為453.6s。根據(jù)本文中提出的改進(jìn)A?算法計(jì)算所得路徑如圖10中虛線所示，路徑包含了8個(gè)交叉口，其中1個(gè)左轉(zhuǎn)，3個(gè)右轉(zhuǎn)，4個(gè)直行，路段總長為3.74km，通行所用時(shí)間為433.7s。

圖9 路徑1(A?算法)

圖10 路徑2(改進(jìn)A?算法)

由表4可以看出，改進(jìn)A?算法得到的路徑長度比A?算法長9.4%，但得到的行駛時(shí)間卻比A?算法減少了4.4%。

表4 不同算法所求路徑總費(fèi)用

選取不同的起點(diǎn)和終點(diǎn)進(jìn)行多次仿真，得到A?算法和改進(jìn)A?算法仿真結(jié)果，如圖11所示。由圖可見，考慮快速通過交叉口等待時(shí)間的改進(jìn)A?算法所得路徑的通行時(shí)間明顯短于A?算法。這是因?yàn)閭鹘y(tǒng)A?算法側(cè)重于考慮路段通行時(shí)間，而本文中提出的考慮快速通過交叉口的改進(jìn)A?算法則兼顧了考慮交叉口的等待時(shí)間，并通過車路協(xié)同的方式在車輛接近交叉口時(shí)優(yōu)化其速度，使其快速通過交叉口，減少車輛在交叉口的等待時(shí)間。

圖11 仿真結(jié)果對(duì)比

3 結(jié)論

本文中提出了考慮快速通過信號(hào)交叉口的車輛最短路徑規(guī)劃算法。通過構(gòu)建基于馬爾科夫鏈的交通信號(hào)燈模型，考慮前方交通燈即將由綠燈轉(zhuǎn)變?yōu)榧t燈，同時(shí)車頭時(shí)距大于臨界閾值時(shí)，車輛加速通過交叉口，在此基礎(chǔ)上結(jié)合A?算法，提出了考慮信號(hào)交叉口等待時(shí)間的改進(jìn)A?算法。算例驗(yàn)證表明，相比傳統(tǒng)的A?算法，該算法所計(jì)算出的路徑更優(yōu)，耗時(shí)更短。本文中提出的算法適用于交通燈密集的城市道路網(wǎng)，且路段交通燈越密集，該算法的優(yōu)越性越明顯。不過，算法也存在一定的局限性，在不同時(shí)間段內(nèi)信號(hào)交叉口的到達(dá)車流具有明顯的差異。在交通流高峰時(shí)間段內(nèi)，車流密集，車頭時(shí)距小，車輛加速通過交叉口的概率也小。

后續(xù)研究中，須進(jìn)一步考慮4個(gè)方面的問題:(1)考慮信號(hào)交叉口干線協(xié)調(diào)，對(duì)相鄰交叉口的相位差進(jìn)行協(xié)調(diào)控制；(2)考慮不同時(shí)間段的交通流分布，進(jìn)一步分析交通流影響下的車頭時(shí)距，提高算法的精確性；(3)考慮路段最大限速和車輛加速度對(duì)交叉口綠燈拓展延時(shí)的影響；(4)在交通流大的情況下，須考慮車輛排隊(duì)的延時(shí)。