考慮信號交叉口延時的最優車輛路徑規劃算法?

胡 林，鐘遠興，黃 晶，杜榮華，張 新

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

前言

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

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

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

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

1 最優車輛路徑規劃算法

1.1 路網模型構建

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

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

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

1.2 路段行程時間計算

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

將衛星導航數據與地圖進行匹配[19]，可得到每一路段dij的車輛實時速度Vij，則各路段的行程時

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

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

圖2 交通燈相位示意圖

計算交通信號燈穩態概率分布的步驟如下。

(1)確定狀態轉移概率矩陣Pij(t)

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

假設當前狀態為綠燈，記為狀態g(綠燈時長為g)，綠燈結束后轉為紅燈狀態，記為狀態r(紅燈時長為r)。當前狀態為g下一刻(經過t)狀態仍為g的概率為Pgijg(t)，即有

相應地定義當前時刻為綠燈下一刻轉為紅燈、當前為紅燈下一刻仍為紅燈和當前為紅燈下一刻轉為綠燈的概率分別為t)，(t)和t)。

式中:Pr為交通燈是紅燈狀態的穩態概率；Pg為交通燈是綠燈狀態的穩態概率。

1.4 車輛加速通過信號交叉口模型

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

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

(2)確定穩態概率P

由馬爾科夫鏈的無記憶性規律可知，穩態概率只取決于交通燈狀態轉移概率矩陣Pij，與初始狀態無關。可求得穩態概率為

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

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

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

車頭時距t為

1.5 車頭時距的確定

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

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

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

威布爾分布的概率密度函數為

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

根據不同車流對應的車頭時距分布，可得該車流產生的大于臨界間距的概率為

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

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

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

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

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

由于車輛到達交叉口的隨機性和不確定性，可假定在交通燈信號周期內的各個時刻車輛到達交叉口的概率是均等的。當前方交通燈為綠燈狀態時，車輛等待時間為0；當前方交通燈為紅燈狀態時，車輛需等到紅燈結束綠燈啟亮時才能通行，根據概率，等待時間約等于紅燈時間的一半。

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

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

圖7 算例路網

表1 算例路網中各路段長度 m

1.7 實時最短路徑算法

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

式中:g(n)為起始節點到當前節點的實際代價；h(n)為當前節點到目標節點的估計代價。

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

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

2 仿真分析

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

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

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

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

表2 各節點交叉口信號配時表

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

圖8 威布爾概率密度曲線

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

表3 各節點交叉口等待時間s

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

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

圖9 路徑1(A?算法)

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

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

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

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

圖11 仿真結果對比

3 結論

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

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