考慮交叉口延誤的超路徑算法及其應用

杜牧青 鞠姿彥 呂晨希 李東宇 李 嘉 趙國軍

(河海大學土木與交通學院 南京 210098)

0 引 言

車輛路徑誘導系統向司機提供的最優路徑，一般是一條以行駛距離最短或者行駛時間最短為目標的簡單路徑[1].從易于實現的角度，主流車輛路徑誘導系統多采用Dijkstra算法及其改進算法(如考慮啟發信息的A*算法)實現路徑搜索功能.這類路徑算法在本質上都是單路徑算法，通常每次搜索只能得到一條最優路徑[2].但是，單一的路徑誘導并不能考慮道路狀況的不確定變化，如擁堵、交通事故的影響，容易將車流集中引導至相同的路線上，導致沿途道路交通量急劇增加形成擁堵，降低了導航系統的實用性和可信度[3].由于單路徑算法的不足，尋求有效的多路徑算法成為車輛路徑誘導領域的熱點[4].

目前，常見的多路徑生成算法可以被劃分為k-最短路徑算法和完全不相交路徑算法兩種[5].研究學者在此基礎上提出了許多改進算法.Jin等[6]研究了基于一種有約束弧的時間網絡的K條最短路徑問題.趙禮峰等[7]結合遺傳算法和模擬退火算法，提出了求解K最短路徑問題的新算法.一些學者提出采用k-最短路徑算法求取多條候選路徑供駕駛員選擇，將最后的決策權留給駕駛員[8-11]，需要進一步考慮駕駛員對每條路徑的個性化評價[12].因此，目前常用的方法是考慮駕駛員不同偏好的多路徑誘導，其本質上仍然是將不同最優目標的簡單路徑作疊加.上述多路徑算法通常不考慮網絡中延誤的不確定性，尤其是信號交叉口延誤的不確定性.且從多路徑搜索算法的原理而言，駕駛員需要在起點確定方案選擇，不能在多方案之間實現路徑的轉換(除非駕駛員在行駛過程中手動更改路線).可見考慮駕駛員偏好的多路徑到并不能夠從本質上實現回避延誤的問題.因此，如何實現多路徑誘導方案中路線的靈活轉換，是幫助駕駛員回避交通延誤的關鍵問題.

Spiess等[13]基于公交線路的客流分配模型，最早提出了超路徑的概念.在公交模型中，最優超路徑被解釋為一種最優的乘車策略，包含了起終點之間所有可以降低乘車者等車時間的公交線路集合.Bell[14]進一步考慮了道路網絡中每條路段上行程時間的不確定性，將Spiess和Florian的公交超路徑應用于道路網絡.Bell指出超路徑搜索算法是一種特殊的多路徑算法，以期望行程時間最小為目標，從實際路網中搜索出起終點之間所有可能最短路徑，納入超路徑子網中.Ma等[15]在Bell研究的基礎上，提出了加快超路徑算法的搜索速度的改進方法.然而，當前適用于道路網路的超路徑算法都未考慮交叉口延誤對期望行程時間的影響，且未考慮超路徑算法在誘導系統的應用，無法為車輛進行實用可靠的路徑誘導.

文中基于交叉口信號配時提出了一種交叉口延誤的計算方法，重新編寫了超路徑算法，用于路徑搜索.并依據超路徑算法“推薦優先綠燈相位”的特點，引入了車路協同技術完善超路徑誘導系統.通過車輛和道路的信息交互，超路徑誘導系統不斷以語音、文字、圖像、視頻等方式向駕駛者提示前方路況和應做的選擇，實現車輛在超路徑子網中靈活轉換路線，降低交叉口延誤.同時依托超路徑誘導系統可以實現流量在網絡中的合理分配，降低網絡整體車輛行程時間，優化網絡性能.

1 考慮交叉口轉向延誤的超路徑算法

1.1 超路徑搜索原理

超路徑考慮路網中延誤的不確定性，是由起終點之間所有可能最短路徑構成的集合.原始的超路徑算法，以終點作為初始搜索節點對路網中的路段逐一搜索，篩選出能降低期望行程延誤的路段，組成超路徑.超路徑搜索結果還包括每個路段在超路徑集合中被選擇的概率，該概率可作為將流量分派到超路徑集合各路段上的比例[16].本文對原始的超路徑搜索算法做出改進，對信號交叉口節點進行擴展，以路段的行駛時間與交叉口期望延誤之和最小為目標函數，得到起訖點之間的超路徑結果.

原始的超路徑算法僅考慮路段延誤的不確定性，將其解釋為離開其上游結點的延誤.當考慮交叉口轉向延誤時，離開結點的延誤將取決于車輛經過交叉口的轉向行為.由交叉口西側和北側進口道進入交叉口的車輛，在從南側和東側出口道離開時所受延誤影響會有明顯不同，即分別為右轉對應直行和直行對應左轉.兩種轉向對應的相位配時不同，所受延誤影響必然存在差異.基于此，本文在路網中對于有信號控制的交叉口節點進行擴展，克服了原始超路徑算法不能反映交叉口轉向阻抗的缺點.本文采用網絡擴展法表示交叉口的轉向行為，將交叉口的各個轉向抽象成虛擬路段，用這些路段阻抗代表交叉口轉向延誤[17].以圖1為例，對于單行車道，有四種轉向，引入四條虛擬路段；對于雙行車道，有十二種轉向，引入十二條虛擬路段.

圖1 道路交叉口的擴展表示

在擴展的道路網絡中，最優超路徑問題被描述為以路段行駛時間和交叉口期望延誤之和最小為目標函數的數學優化模型，為

(1)

s.t.

(2)

pij∈[0,1],?(i,j)∈A

(3)

wi≥dij·pij,?(i,j)∈A

(4)

對于擴展的網絡，虛擬路段對應于交叉口的轉向，其最大延誤dij由信號燈周期性變化引起，令其等于該轉向的非綠燈時長.本文假設車輛在隨機時刻到達交叉口，并定義交叉口轉向ri服務頻率fri(fri=1/dri).在超路徑中，對于任意交叉口進口道節點i，可能存在多個可用的轉向ri，采用集合Ri表示該節點的全部可用轉向.進一步，定義交叉口服務頻率fi=∑ri∈Rifri，則車輛在交叉口進口道的等待時間期望wi為

(5)

式中：α∈(0,1]，α的取值取決于對交叉口信號配時的估計，在本文中假設α=1.

1.2 算法步驟

因此，本文的超路徑算法流程包括以下步驟：

步驟1指定起點r和終點s；創建路段集合L，將路網中所有路段加入集合L中；創建超路徑的路段集合H，令集合H初始為空集.初始化各變量如下：

令us=0，yr=1；

令ui=∞，?i≠s；

令yi=0，?i≠r；

令fi=0，?i∈V；pij=0，?(i,j)∈A；

當dij>0時，令fij=1/dij；當dij=0時，令fij=∞.

步驟2查找集合L中(uj+cij)最小的路段(i,j)，作為當前路段，并將其從集合L中移除.

步驟3若當前路段滿足條件ui≥uj+cij，則進入步驟4；否則，返回步驟2.

步驟4更新當前路段(i,j)的上游節點i到終點s的考慮延誤的最短行駛時間ui.

若ui=∞，fi=0，則進行如下運算：

否則，進行如下運算：

步驟5更新節點i處的組合服務頻率變量和數據，作如下運算：

fi=fi+fij

步驟6將當前路段(i,j)加入到集合H中，此時，若滿足條件L=?或uj+cij≥ur，進入步驟7；否則，返回步驟2.

步驟7求解路段及節點選擇概率：將網絡中的全部路段(i,j)，按照uj+cij的值，從大到小排序；根據排序后的順序遍歷全部路段，若路段(i,j)∈H，則進行如下運算：

否則，令pij=0.

從起點r開始，追溯到達終點s的超路徑并輸出，用于路徑誘導決策.

1.3 算例

為了進一步闡明超路徑算法的含義，采用方格網型的交通網絡并對每個節點進行編號，見圖2.以點r為起點，點s為終點，除5、16外其余為信號燈控制的節點，網絡中共含有20個節點和31條雙車道路段，并將網絡圖進行虛擬路段展開.圖3為路網中有信號控制的各交叉口的信號相位配時圖，表1為各路段的行程時間，表2為基于最大悲觀期望假設求得的各交叉口轉向的等待時間.

圖2 實例網絡圖

圖3 交叉口相位配時圖

表1 路段的行駛時間

基于最大悲觀期望假設，對于各轉向路段延誤的計算以圖2所示T型交叉口2為例進行說明.當行駛路線的前向交叉口編號為r，后續交叉口編號為3時，車輛在交叉口2時需要直行.對照圖3的相位圖，在交叉口2處的直行只屬于第一相位且在一個周期內第一相位的綠燈時間是25 s，黃燈時間是5 s，紅燈時間是60 s.由于車輛在黃燈時間和紅燈時間內停車等待，因此，確定執行通過的轉向延誤為65 s.依照這個原理，推出圖2道路網絡中所有交叉口的轉向延誤，見表2.

表2 交叉口轉向的路段延誤

按算法步驟，篩選出超路徑，并在每條路段上標注其被駕駛員選擇的概率，即誘導系統將車流量分配到各路段的比重，見圖4.

圖4 實例的路線概率圖

由路段概率得出可靠最短路徑一共有3條：①r-6-11-12-13-18-19-s，被選擇的概率為0.25；②r-6-11-16-17-18-19-s，被選擇的概率為0.25；③r-6-7-12-13-18-19-s，被選擇的概率為0.5.

算法運行獲得的三組結果見圖5.由圖5可知，在獲取的多組解中，用戶可以選擇這3條出行路徑靈活地改變行進路線，降低延誤時間.

圖5 實例的路線選擇圖

2 基于車路協同的超路徑誘導應用

車路協同基于無線通信、傳感探測等技術獲取車輛和道路信息，通過車車、車路通信進行信息交互和共享，實現車輛與基礎設施之間智能協同與配合[18].車路協同系統由智能交通管理系統、智能通信系統、智能車輛子系統和智能路側系統四個部分組成[19-20].智能交通管理系統處理由智能車輛子系統和智能路側系統獲取的信息，計算超路徑子網中包含的各轉向對應的時間，具體分為以下兩種情況：

分析比較出時間最短的轉向，并推薦給駕駛員.從而保證車輛在交叉口處始終選擇優先綠燈相位，最小化交叉口等待延誤.圖6為車路協同系統的構架，圖7為依托車路協同技術的超路徑誘導系統的信息交互原理.

圖6 車路協同系統構架圖

圖7 車路協同信息交互

車輛在實際路況中行駛，超路徑誘導系統將進行如下誘導.在出發前，車輛路徑誘導系統為駕駛員篩選出圖4的超路徑子網，首先推薦駕駛員沿路段r-6行駛.具體流程如下.

步驟1當車輛行駛接近交叉口6的通信范圍時，路側系統檢測到車輛駛入，獲取該車輛前直行車輛數Q1直=40輛、直行車流速度v1直=60 km/h、直行車輛流率q直=3 600輛/h、左轉車輛數Q1左=30、左轉車流速度v1左=50 km/h、左轉車輛流率q左=3 000輛/h、該交叉口信號燈當前相位狀態信息，將這些信息傳輸給管理系統.

步驟2智能車輛子系統從多路徑誘導方案中獲得在當前交叉口的轉向策略集合S和車輛當前位置，S包括直行和左轉，并將這些信息傳輸至智能交通管理系統.

步驟3計算車輛到直行和左轉的停車線時間.

最后，根據判斷條件t左>t直，向智能車輛子系統遞直行轉向.

步驟3車輛子系統顯示路徑推薦，車輛接收直行指令，車輛會提前變道，駛離交叉口.

圖8為車路協同誘導示意.駕駛員依據圖5三組行駛路線進行靈活的路線轉換.行駛至下一個路口時，超路徑誘導系統繼續根據“推薦優先綠燈相位”的原則，從超路徑子網中搜索路徑推薦給駕駛員，直至行駛至目標點.全部交叉口誘導示意圖見圖9.

圖8 車路協同誘導示意圖

圖9 完整交叉口誘導示意圖

由此可見，在以超路徑算法為依托的車輛路徑誘導系統中，駕駛員在交叉口可以靈活變換行車路線，達到降低交叉口延誤的效果，從而實現“可靠最短”的出行目的.

基于1.3提出的超路徑搜索算法，并應用上述車輛誘導方法，從網絡總體流量角度分析超路徑誘導方案的優點.假設某時段內共計100名駕駛員從起點r行駛至終點s.分別沿超路徑算法篩選出來的三條路徑(見圖5)和時間最短的唯一路徑行駛，統計出車輛在交叉口的延誤情況，見表3.其中，車輛依據圖4的選擇比例計算結果，分配在超路徑中.

表3 超路徑和單路徑延誤時間對比

由表3的結果表明，在路網中應用超路誘導系統，可降低21.9%的總體平均延誤.由此可見，采用超路徑誘導策略，可以實現流量在網絡中的合理分配，達到網絡整體車輛行程時間最短的目的.

3 結 束 語

本文基于交叉口信號配時提出了一種交叉口等待時間的計算方法，并用于超路徑搜索.基于最大悲觀期望假設利用信號配時方案求得交叉口各轉向最大等待時間，進一步通過線性組合求出車輛在交叉口等待期望，避免了處理大量數據，加快了路徑誘導方案的搜索速度.在路徑誘導方面，提出了在車路協同環境下實現對優先綠燈相位的判斷的解決方案，進一步完善了超路徑誘導系統，達到了優先推薦綠燈相位的目的.

對于個體而言，駕駛員可以通過誘導系統在超路徑子網中靈活改變行駛路線，實現達到降低行程延誤的目的.對于整體網絡而言，超路徑基于交叉口服務頻率來合理分配路段車流量，降低整體網絡的車輛行駛時間，提升交通網絡性能，會產生巨大的經濟效益.隨著人們對個性化出行需求的增多，超路徑誘導系統可引入相應的需求因子變更目標函數，在提高網絡性能的同時，實現對用戶的個性化誘導.同時，本文通過完善車路協同技術的判斷機制，實現了車路協同技術與超路徑誘導系統的結合，將在有效降低駕駛員行程延誤和完善智能交通誘導體系上發揮巨大作用.

本文基于信號配時計算車輛在交叉口的等待時間時，存在兩個假設條件：①最大悲觀期望假設，假設車輛在交叉口每個轉向的等待時間是紅燈加黃燈時間；②獨立性假設，假設車輛可選擇的相位相互獨立，計算在交叉口的期望等待時間時將各轉向等待時間線性組合.這兩個假設較為理想，可能會導致與實際情況存在一定偏差.今后的研究將上述假設條件做進一步完善，使得超路徑搜索結果更加貼合實際路網情況.