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

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

前言

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

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

此外，對車輛通過交叉口的速度優(yōu)化也進行了廣泛的研究[9-11]。Mandava等[12]提出在通過車輛與道路設(shè)施的通信預(yù)先獲取前方交通燈信號相位和配時信息的基礎(chǔ)上，對車輛進行動態(tài)速度規(guī)劃，使車輛盡可能避免加速、減速和怠速狀態(tài)，降低車輛的油耗和尾氣排放。Rakha等[13]提出了旨在提高燃油效率的環(huán)保駕駛框架，通過車輛與道路設(shè)施的通信提前獲取交通燈信號相位和配時信息，用以調(diào)整車輛通過交叉口的策略，從而達(dá)到降低車輛油耗的目的。Butakov等[14]則結(jié)合駕駛員的偏好和習(xí)慣對車輛通過交叉口的速度進行優(yōu)化，從而降低油耗，縮短等待時間。安實等[15]提出了一種基于多級可變速度限制的信號交叉口綠色駕駛控制方法，以信號交叉口為背景，對車隊中的頭車進行速度限制。林培群等[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ù)交叉路口的通行車速計算方法。

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

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

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

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

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

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

1.2 路段行程時間計算

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

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

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

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

圖2 交通燈相位示意圖

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

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

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

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

相應(yīng)地定義當(dāng)前時刻為綠燈下一刻轉(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 車輛加速通過信號交叉口模型

車輛通過交叉路口示意圖如圖3所示。由圖可見:當(dāng)前方交通燈為綠燈狀態(tài)且綠燈剩余時間足夠時，車輛無需等待，以路段實時平均速度Vi通過交叉口；當(dāng)前方交通燈狀態(tài)為紅燈時，車輛需要等待綠燈相位的到來。通過車路協(xié)同方式(V2I)，車輛在與前方交叉口距離S時就能知道交通燈的當(dāng)前相位及其剩余時間。這樣，當(dāng)前方交通燈即將由綠燈轉(zhuǎn)變?yōu)榧t燈時，車輛可加速通過以避免交叉口的等待。假設(shè)車輛距離交叉口停止線為S時，車輛以速度Vi行駛，到達(dá)停車線的時刻為t2；車輛以加速度a1加速到最大速度Vmax行駛時，到達(dá)停車線的時刻為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)車輛加速通過前方交叉口時，須考慮車輛前方是否有車和前車與本車的車頭間距(本文中不考慮超車的情況)。本車與前車的車頭時距示意圖如圖4所示。由圖可見，本車距離前方交叉口S時加速到最大速度Vmax行駛，經(jīng)過t1時間車輛剛好駛過停車線，若前方有車且以速度Vi行駛，本車與前車的車頭間距L應(yīng)滿足:

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

圖4 本車與前車的車頭時距示意圖

車頭時距t為

1.5 車頭時距的確定

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

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

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

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

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

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

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

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

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

圖6 車頭時距概率密度分布

1.6 考慮快速通過信號交叉口的車輛等待時間

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

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

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

圖7 算例路網(wǎng)

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

1.7 實時最短路徑算法

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

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

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

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

2 仿真分析

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

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

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

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

表2 各節(jié)點交叉口信號配時表

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

圖8 威布爾概率密度曲線

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

表3 各節(jié)點交叉口等待時間s

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

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

圖9 路徑1(A?算法)

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

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

表4 不同算法所求路徑總費用

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

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

3 結(jié)論

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

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