考慮用戶緊急程度的在途路徑誘導策略研究

白 靜，陳業華，劉一健

(燕山大學 經濟管理學院,河北 秦皇島 066004)

0 引言

隨著交通基礎設施的不斷完善以及數據傳輸、數據處理等技術的快速發展，車載路徑誘導系統的研究和應用獲得了新的契機，用戶可以通過導航系統提供的實時信息選擇較優線路。目前很多學者對基于實時信息的路徑尋優作了深入研究，其中所采用的最直觀的決策方法是尋找最短路徑，為了解決行駛時間概率分布不確定的問題，Cao等利用每條路徑上的采樣行駛時間將原始的求最短路徑問題轉換成基數最小化問題進行求解[1]。考慮到時間問題造成行駛成本具有很大的不確定性，智路平等對動態的交通行駛成本進行分類預測，并在相應的可靠性約束下利用改進的Dijkstra法作出尋優決策[2]，此外，林徐勛[3]、楊傳印[4]等也分別利用概率密度演化理論、優先隊列方法求解了行駛成本不確定的最短路徑問題[3-4]。還有學者進一步研究了當用戶對路徑選擇沒有確定性標準時的選擇模型，其中，張惠玲等人考慮了用戶的出行需求對規劃方案的影響，利用級差效益衡量用戶這一主觀感知，并作為路徑選擇的評價準則[5]。Mai[6]、Songyot[7]、Kitthamkesorn[8]等學者則分別從隨機用戶均衡的角度建立了路徑選擇模型。對交通數據的不同處理方式將誘導類型劃分成反應型及預測型二類。反應型策略根據實時的路況信息制定路徑誘導策略，Nejad[9]等設計了層級算法以處理ITS獲取的實時數據，進而計算最短路徑。此外，TomTom[10]、google[11]等企業也已著手開發車、路通訊下的路徑誘導系統。但反應型策略的特點是根據當前路況作出相應決策，而交通狀態是不斷變化的，當前的最優決策可能會將車輛轉移至相對延遲擁堵的路線，誘導效果存在隨機性。預測型策略是利用預測的信息制定誘導方案，即在決策前首先利用交通數據對未來交通狀態作預測。Lin[12]等提出了動態在途實時路徑決策方案(DEDR)，該方案引入了信任概率評價預測信息，并構建相應的多重矩陣為用戶提供路徑選擇依據。預測型誘導策略兼顧了壞天氣或突發事件造成的交通狀態不確定性，實用性更強[13-15]。

考慮目前多數文獻缺乏對突發事件造成突發擁堵的嵌入研究，而用戶面對這類包含不確定性、衍生性等特點的交通狀況所作出的反應與常態化擁堵有所區別。而且，多數誘導系統采取依據實時數據的反應性決策，在交通狀況波動較大的突發擁堵情境下具有一定滯后性，針對上述問題，本研究考慮在誘導系統中設置針對突發擁堵的導航模塊，當系統識別突發擁堵發生時，自動觸發突發擁堵導航模塊，針對擁堵狀況為用戶提供實時的在途路徑誘導策略。為提高用戶體驗進而提高用戶對誘導系統的服從率，在深入分析用戶對擁堵的個人感知特性基礎上，以感知擁堵作為路徑誘導的路徑分配限制因素，設計了基于用戶緊急程度的隨機均衡替代路線分配方案。同時，為了充分利用預測信息提高路徑尋優效率，將預測的交通信息作為誘導決策的信息支持，并提出了時變路網下改進的A*算法。

1 突發擁堵下考慮用戶緊急程度的在途路徑誘導策略

路徑誘導作為常規性的交通管理措施，能夠應用于日常交通中，特別是對于突發擁堵狀況，用戶能夠憑借誘導系統顯示的道路信息決定行駛路線。本研究設計了一個針對突發擁堵的動態在途路徑誘導方案(EPR)。突發擁堵時，誘導系統周期性執行4個程序對路線進行再分配：

(1)數據搜集及處理；

(2)交通擁堵預測；

(3)選取改變路線車輛；

(4)為被選車輛計算備選路線信息。

這里(1)、(2)采用文獻[16]提出的深度結構預測模型。EPR重點討論(3)、(4)部分。

當突發事件發生并觸發突發擁堵導航系統時，該模塊將啟動對即將進入擁堵區域車輛的確認程序，顯然，擁堵狀態下車輛的駛入將加劇交通堵塞，為避免交通進一步惡化，本研究選擇“L等級”標準，視擁堵程度科學地選擇合理位置車輛并誘導其更改行駛路線。具體來說，L作為設定的誘導區域范圍值，即選擇在交通流逆方向上距離事發路段為L內的部分車輛進行路徑誘導，假定L=2，車輛選擇的方法如圖1所示。其中，系統識別Sc路段為突發擁堵狀態，以Sc為中心沿車流流入方向劃出2級路段，分別為S1，S2，并依次圈定S1及S2中需更改路線車輛。車輛選擇的方法如圖1所示。

圖1 車輛選擇過程Fig.1 Vehicle selection process

選出需更改路線的車輛后，利用改進A*算法計算前k條次優路徑，同時為其分配備選路線。

1.1 時變路網下的改進A*算法

考慮到突發擁堵下的路徑誘導對時效性要求更高，本研究采用具有高效、直接特性的搜索算法A*算法求解最短路徑。在交通網絡中，行駛成本具有很大的不確定性，對于不同時間點，行駛成本會存在較大差異，特別是發生突發性擁堵時，會進一步增加行駛成本。因此，本研究采用具有時間依賴的A*算法結構，并通過改進A*算法中行駛時間的表達，采用交通流預測信息與歷史信息表示未來的行駛時間。

A*算法作為典型的啟發式算法，通過路徑代價點的評估函數指引尋優行為的前進方向。假設從s點出發，終點為d，A*算法的目標就是找到s→d的最佳路徑。搜索過程分為兩個階段：(1)判斷邁出一步(出發點s到節點vi)的行駛成本，記為g(vi)，本研究用行駛時間表示。(2)節點vi到終點d所需直接步數(本研究指最優路徑行駛時間評估函數)，記為h(vi)。令評估函數f(vi)表示為：

f(vi)=g(vi)+h(vi)。

(1)

通過計算并存儲f(vi)，找到各方向中使f(vi)最小的路徑即可。其中，在具有時間依賴的A*算法中，假定出發時間點t，去往節點k的評估函數為h=h(k,t)≥0。

設計科學的評估函數有助于有效、快速地尋找到最短路徑。時變網絡中路段的行駛成本并非固定值，常見方法是利用實時路況信息或者歷史數據求取行駛成本，而突發事件會造成交通狀態急速改變，利用現有狀態信息計算得到的路徑尋優結果甚至可能不再符合未來短期內交通狀態，因此本研究在時間依賴的A*算法基礎上利用預測信息改進評估函數h(vi)的表達，更精確地求解最短路徑。

令d(v,w,t)為在時間t出發從點v到點w的最短行駛時間；令L為路網中的節點集合，且l∈L；令Tl={t1,t2,…,tp}為在節點l處的p個時間采樣點，且t1

(2)

(3)

式中，ti為在節點vi處的時間;e(vi,vj)為路段e，其中，vi和vj為連接路段e的兩個交叉口，且vi≠vj;r(l,k)為當次出行中從點l去往點k的無環路徑集合。vi至vj路段的預測有效性消散率為：

(4)

式中，ε為預測有效性的消散比例，考慮未來過遠時間的交通流隨機性較大，因此預測的精度會隨時間的增長而降低，為確保采用的預測信息是有效的，本研究將消散率分為3個階段；第1階段為時間δ內(處在vi處時間為δ)，因為可以保證足夠預測精度，完全采用預測信息計算行駛時間；第2階段為時間δ到預測時間段t1內，采用平均速度預測與歷史信息結合協同計算行駛時間；第3階段預測時間段之后，由于預測精度不高，完全根據歷史信息計算行駛時間。結合預測信息的評估函數h(v,t)表示為：

(5)

其中

(6)

表示在時間t之前從l到v的最近出發采樣時間點。

由評估函數h(v,t)的定義可得，h(d,t)≡0，h≥0。下面證明改進A*算法能找到最優解的充分條件，即評估函數需滿足FIFO準則以及三角條件。

定理1式(5)、式(6)表示的評估函數符合FIFO準則，同時符合三角條件。

(7)

顯然，為了證明t1+h(k,t1)≤t2+h(k,t2)，只需證明下面的不等式

(8)

三角條件：給定任意路段e(v,w)，在時間節點t，要證明h(v,t)≤ce(t)+h(w,t+ce(t))，令tw=t+ce(t)，則等價于證明

t+h(v,t)≤tw+h(w,tw)，

(9)

(10)

顯然，為了證明式(9)，只需證明

(11)

證畢

1.2 考慮用戶緊急程度的路徑分配模型

當最優路徑發生突發擁堵時，為避免發生路徑誘導導致的“移堵”現象，本研究為被選車輛分別在各自前k條次優路徑中按一定概率隨機地分配路線。路徑誘導的誘導效率很大程度上受用戶的服從率影響，而當用戶擁有良好的體驗時，其服從路徑誘導方案的意愿更強烈，因此本研究在選擇概率中加入用戶對擁堵的感知因素，從提高用戶體驗層面出發，制定路徑誘導策略。

(12)

(13)

(14)

道路擁堵狀況給不同行程的用戶帶來的心理感知不盡相同，例如，即將到達終點的用戶相對于處在行程起始階段的用戶其緊急程度存在差異，相應地，對擁堵的感知也互不相同。本研究考慮令更緊急的用戶以更高的概率選擇較快捷路線，從而提高全體用戶的整體體驗，特引入2種“緊急函數”以表示用戶緊急程度：

絕對緊急函數：ACI=RemTT-RFFTT，

相對緊急函數：RCI=ACI/RFFTT。

其中，RemTT為擁堵出現后原始行程剩余行駛時間；RFFTT為無擁堵下原始行程剩余行駛時間；ACI為受擁堵影響距終點需額外花費的時間(即用戶的直接緊急程度)；RCI為受擁堵影響距終點需額外花費的時間與原始行程中剩余路程所需時間比值(用戶的間接緊急程度)。

(15)

式中RCIn為用戶車輛Vn的相對緊急程度系數。

(16)

為了更清晰地描述路徑分配流程，誘導過程所處路網如圖2所示。

圖2 誘導過程所處路網Fig.2 Road network in guidance process

當用戶車輛V5被選中更改路線，假設p6,5→p5,8→p8,7→p7,4為第1最短路線，車輛V5選擇該路線增加的感知效用為:

(17)

假設p6, 5→p5, 2→p2, 1→p1, 4為第2最短路線，車輛V5選擇該路線增加的感知效用為：

(18)

由于路段Pc出現擁堵，包含該路段的行程行駛時間極易更高，但在路徑分配時，Pc仍有機會包含在備選路線中并依據分配模型參與選擇過程，當Pc處于較擁堵的交通狀況時，備選路線中更可能排除Pc，縱然存在包含Pc的路線，車輛被分配到該路線的可能性也較低。但是當Pc處僅是微弱擁堵時，那么備選路線包含Pc甚至被分配到該路線的可能性就比較高，這種情況下若禁止交通在Pc處通行也將浪費交通資源。

1.3 考慮用戶緊急程度的在途路徑誘導方案實施過程

假設路網區域G，原始路線H′，擁堵閾值為δ，在當前時刻t，車輛選擇系數l，替換路徑數量為k，實施過程如下：

(2)若#Pcon>0，選擇其中預測信息顯示最擁堵的路段p∈Pcon;

(3)尋找與路段p相距l的近鄰路段Pnei，同時找出位于路段p′(p′∈Pnei)且原始路線包含路段p的車輛，所有選中車輛表示為Ω；

(4)根據2.1節中改進A*算法為車輛集合Ω中的車輛vn(vn∈Ω)計算前k條最短路線H=[h1,h2,…,hk]；

(7)令hi作為車輛vn的新路線，按順序為選中車輛分配hi；

(8)更新路網信息，將已討論路段從集合Pcon剔除，即Pcon∶Pcon=Pcon-p；

(9)當討論完成全部擁堵路段后(#Pcon==0)，得到新路網G。

總的EPR流程如圖3所示。

圖3 基于用戶緊急程度的在途誘導方案流程Fig.3 Flowchart of en-route guidance scheme based on user urgency

2 算例分析

2.1 試驗設置

試驗以SUMO15.0作為仿真服務器，通過SUMO可以實現城市交通的微觀模擬以及在線交互等功能。在SUMO平臺對擁堵控制誘導策略進行仿真的流程如圖4所示。

圖4 誘導方案仿真流程Fig.4 Simulation process of guidance scheme

仿真開始前，從OpenStreetMap中下載1個OSM格式的地圖，本研究以秦皇島市某區部分區域為背景，其路網結構如圖5所示。

圖5 路網結構實例Fig.5 Examples of road network

SUMO本身無法處理.osm文件，需要SUMO自帶的Netconvert轉換格式，同時通過Netedit對生成的net路網作進一步處理，比如移除非機動車、輕軌軌道等，最后，使用Trafficmodeler生成車輛軌跡。路網性質設定如表1所示。

路網設置完成后開始對策略仿真、分析。突發擁堵的程度受造成擁堵的事件類型影響，通常按大小將事件劃分為4個級別，本研究分別為各級別事件設定相應的仿真環境，如表2所示。

表1 仿真路網特性Tab.1 Characteristics of simulated road network

表2 仿真環境設置Tab.2 Settings of simulation environment

為確保對誘導策略的機制效果作準確的評估分析，本研究選擇3種具有不同評估方向的評估指標：(1)到達車輛平均行駛時間。反應全區域路網的交通運行情況，可以實時評估突發擁堵的動態誘導成效。(2)擁堵路段數量。從全局角度直觀地顯示誘導成效。(3)用戶完成行程數目。從用戶立場評估誘導策略，完善評價體系。

2.2 仿真評估結果及分析

對EPR誘導效果仿真過程中，采用Webster周期公式設置信號燈配時。設置5個突發事件點，發生路段(均為路段中)、事件程度隨機選擇。出于比較分析的原因，事件發生時間均設定為仿真開始后第200 s。經過反復大量試驗，得到EPR相關參數設定如表3所示。

表3 EPR相關參數Tab.3 Parameters of EPR

(1)用戶服從率對EPR的作用。試驗構建了4種具有不同車流量的環境，分別在各環境中仿真了EPR在不同用戶服從率下的誘導成效，并通過平均行駛時間進行衡量，仿真結果如圖6所示。

圖6 服從率對誘導效果的作用Fig.6 Influence of compliance rate on guidance effect

由圖6可以看出，相對于無任何路徑誘導(以服從率為0表示)，任何服從率下的EPR誘導策略均能夠減少用戶的平均行駛時間，并且提高用戶服從率能夠更顯著減少用戶的平均行駛時間，提高誘導效率。

(2)EPR的誘導效率評估。仿真試驗設置服從率為70%，交通流量水平為2 000，分別從擁堵路段數量、到達車輛數量兩方面對EPR誘導成效進行評估，并與DTA策略[17]、DUA策略[18]以及無路徑誘導干預的原始交通狀態作比較，其中，DUA策略采用的實時信息通過仿真實時獲取(非預測信息)。試驗結果如圖7所示，圖7(a)為4種作用方式下擁堵路段數量隨時間的增減過程，圖7(b)為4種作用方式下到達車輛數量增減過程。

圖7 仿真過程中的評估指標Fig.7 Evaluation indicators during simulation process

圖7顯示，無路徑誘導干預的原始交通中，突發事件發生后事件路段開始發生擁堵，并且擁堵迅速向其他路段蔓延，擁堵持續較長時間后逐漸顯現消退跡象。對于有路徑誘導干預的幾種作用方式，EPR策略及DUA策略下，突發事件造成事件路段出現擁堵，但由于兩種策略為用戶車輛提供了較科學的路徑選擇信息，避免了信息不對稱造成的擁堵蔓延。相對于DUA策略，EPR策略以更快的速度誘導疏散了擁堵車輛，由于其利用了預測的路段速度進行路徑尋優，有效防止了車輛轉移至相對延遲擁堵的路線，而DUA完全依賴檢測的實時數據作出決策，造成了移堵。DTA在抑制擁堵擴散方面缺少優勢，但可以較好地調控整體路網的交通均衡狀態。在不同車流量下，對EPR策略與DTA策略、DUA策略以及無路徑誘導干預的原始交通進行仿真，幾種作用方式下的到達車輛平均行駛時間對比結果如圖8所示。

圖8 不同交通流量的平均行駛時間Fig.8 Mean travel time under different traffic volumes

圖8顯示，在低車流量下，EPR策略誘導效果最佳，在高車流量下，EPR誘導成效稍遜于DTA，優于DUA并且明顯優于無誘導干預的原始交通。

(3)EPR時效性評估。在途路徑誘導系統根據動態的交通狀態為用戶提供路徑選擇信息，對時效性要求較高，仿真試驗通過對事件發生后600 s內EPR策略更新所需CPU時間的平均值對其時效性進行評估，并與其他兩種策略作對比，不同車流量下幾種策略的平均CPU時間如圖9所示。

圖9 不同車流量下的CPU時間Fig.9 CPU time for different traffic volumes

圖9顯示，EPR策略更新的平均CPU時間在3種策略中最少，DTA以系統最優的均衡狀態為路徑分配準則，趨于理想化，時效性最差，DUA選取常見的最短路徑尋優方式，代表了當前大多數誘導系統的時效性，因為EPR差別化計算最短路徑，且選擇搜索效率優異的改進A*算法，因此時效性高于DUA。

3 結論

突發擁堵的突發性及隨機性使用戶無法在出發前做出路徑選擇，當最優路徑被預測出發生突發擁堵時，為避免發生路徑誘導導致的“移堵”現象，本研究為被選車輛分別在各自前k條次優路徑中按一定概率隨機地分配路線。為提高用戶對誘導方案的服從率進而提升誘導效率。本研究在備選路線隨機均衡選擇模型中加入用戶對擁堵的感知因素，提出了以感知擁堵作為路徑誘導的路徑分配限制因素，并構建了行駛時間感知效用算法。同時，通過改進A*算法估價函數中的評估函數，將路段平均速度預測與歷史平均回歸模型結合計算行程時間，從而實現了考慮時間依賴性的實時最短路徑尋優。仿真結果表明，提高用戶的誘導服從率有助于提升突發擁堵下的誘導疏散效率。誘導疏散效果與現有幾種算法相比，所提在途路徑誘導策略在兼顧計算效率前提下，在不同車流量水平下，均可以為用戶車輛提供較科學的路徑選擇信息，避免信息不對稱造成的擁堵蔓延，同時，由于其利用了預測的路段速度進行路徑尋優，進而避免了移堵現象的發生。

本研究提出的路徑誘導策略以預測模型得到的預測信息作為誘導依據之一，如何利用當前研究熱點車聯網技術實現的車車通信、車路通信所產生的共享信息，實現近似路網均衡的路徑誘導策略是一個應用型很強的研究方向。