一類交通信息物理系統(tǒng)的動態(tài)路徑引導(dǎo)

陳卓然,韓定定

(復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院，上海 200433)

0 引言

近年來，隨著物聯(lián)網(wǎng)[1-2]和大數(shù)據(jù)[3-4]技術(shù)的快速發(fā)展，城市交通問題的治理方案不斷推陳出新。交通系統(tǒng)中，道路和車輛上的監(jiān)控和傳感設(shè)備收集的大量信息，經(jīng)過實時的處理和分析可用于描述道路和車輛的狀態(tài)和動態(tài)行為[5-6]，通過在線模型及時決策和規(guī)劃能充分利用交通系統(tǒng)資源、提高道路通行能力[7-9]。信息物理系統(tǒng)(Cyber-Physical Systems, CPS)[10-11]可用于管理此類大數(shù)據(jù)架構(gòu)。CPS集成了感知、計算、通信、控制等技術(shù)，實現(xiàn)了信息空間和物理空間中人、機、物、環(huán)境、信息等要素的相互映射、適時交互、相互協(xié)同，應(yīng)用范圍涵蓋了智能電網(wǎng)等能源與資源分配網(wǎng)絡(luò)、智能汽車與交通網(wǎng)絡(luò)、醫(yī)療護理、環(huán)境監(jiān)測與災(zāi)害響應(yīng)、機器人團體協(xié)作、工業(yè)自動化等眾多領(lǐng)域[12]。

可靠、有效的實時交通信息在CPS感知、計算、決策、執(zhí)行過程中的閉環(huán)流通，提高了城市交通系統(tǒng)的服務(wù)質(zhì)量，例如其關(guān)鍵服務(wù)之一的動態(tài)路徑引導(dǎo)[13-15]。動態(tài)路徑引導(dǎo)，一方面可以通過實時信息對道路中的擁堵跡象進行判斷、平衡路網(wǎng)中交通負(fù)荷[16-19]，另一方面可以考慮將Dijkstra[20]或Hart[21]等的最短路徑算法作用于實時更新的拓?fù)鋄22-23]。目前已有不少交通信息物理系統(tǒng)(Transportation CPS, TCPS)在動態(tài)路徑引導(dǎo)方面的嘗試，如利用物聯(lián)網(wǎng)技術(shù)從路段和車輛中采集和聚合實時數(shù)據(jù)并將短期交通預(yù)測與實時路徑優(yōu)化相結(jié)合，增強路段與車輛之間的協(xié)作[24]；研究由物理交通系統(tǒng)和與其相當(dāng)?shù)娜斯そ煌ㄏ到y(tǒng)組成的并行智能交通系統(tǒng)，用大量的長期迭代模擬來預(yù)測和分析預(yù)期的操作結(jié)果[25]；考慮道路長度、天氣狀況、事故等綜合成本的最小化，將路網(wǎng)建模為一個不斷更新的加權(quán)有向圖，根據(jù)時間表用綜合成本最小化策略和最快策略進行引導(dǎo)[26]。現(xiàn)有的方法往往只為單一車輛的出行推薦最優(yōu)路線，未考慮不同車輛采取相同路徑后可能會導(dǎo)致潛在的交通擁堵[27]。在實時全局交通信息已知的情況下，如何以合適的頻率對出行個體進行引導(dǎo)，如何權(quán)衡全局和個體，或許會是未來城市交通系統(tǒng)面臨的挑戰(zhàn)。

本文提出了基于實時全局交通信息的TCPS框架，針對動態(tài)路徑引導(dǎo)中的方式和頻率展開仿真和討論。引入強化學(xué)習(xí)中的Q-learning作為引導(dǎo)策略，通過定時獲取道路的平均通行時間作為動作的懲罰、更新Q值表、依據(jù)最大化值策略引導(dǎo)車輛來構(gòu)建感知、計算、決策、執(zhí)行中信息流通的閉環(huán)?？紤]了3種動態(tài)引導(dǎo)方式：一次性引導(dǎo)、周期性同時引導(dǎo)和周期性各自引導(dǎo)。仿真結(jié)果表明，動態(tài)引導(dǎo)相較于基于靜態(tài)拓?fù)涞淖疃搪窂皆谡w性能上有明顯提升；周期性同時引導(dǎo)和周期性各自引導(dǎo)之間差別不大，但都優(yōu)于一次性引導(dǎo)；同時，仿真發(fā)現(xiàn)引導(dǎo)過程中產(chǎn)生的博弈現(xiàn)象：車輛采取相同最優(yōu)策略會使得該策略因車輛的大量涌入失去優(yōu)勢，導(dǎo)致后續(xù)車輛采取與之不同的策略形成制約；周期性同時引導(dǎo)和周期性各自引導(dǎo)的博弈強度隨周期發(fā)生不同的變化，而整體性能未隨周期呈現(xiàn)出明顯規(guī)律。

1 交通信息物理系統(tǒng)框架

1.1 系統(tǒng)框架

交通信息物理系統(tǒng)的框架如圖1所示。在物理空間中，利用物聯(lián)網(wǎng)技術(shù)，可通過監(jiān)控和傳感設(shè)備獲取整個網(wǎng)路中道路和車輛的實時數(shù)據(jù)，如道路平均通行時間、車輛的位置和目的地等；在信息空間中，可通過對數(shù)據(jù)處理和分析來驅(qū)動模型做出決策，并與道路上車輛實時通信使其在本地更新路徑，以盡快到達目的地。

圖1 TCPS框架

基于Q-learning[28-29]的動態(tài)路徑引導(dǎo)流程如圖2所示。將車輛所在道路邊作為狀態(tài)x，下一條邊的選擇作為動作a，若下一條邊為終點則給予獎賞R，否則將其平均道路通行時間作為懲罰。為車輛的每一個目的地維護一張累計獎賞函數(shù)Q值表，用實時交通信息更新R、利用ε-貪婪策略更新Q值表、最后根據(jù)車輛的當(dāng)前位置用最大化值函數(shù)選擇最優(yōu)引導(dǎo)路徑。累計獎賞函數(shù)的更新方式如式(1)所示：

圖2 Q-learning決策流程圖

(1)

其中，x′是在狀態(tài)x執(zhí)行動作a后轉(zhuǎn)移的狀態(tài)，a′是在x′上基于策略π選擇的動作，α和γ分別為學(xué)習(xí)率和折扣因子。

定義道路的平均通行時間(Average Travel Time, ATT)為

(2)

(3)

采用不同的執(zhí)行策略和評估策略。執(zhí)行策略在訓(xùn)練中與環(huán)境互動產(chǎn)生數(shù)據(jù)，評估策略學(xué)習(xí)執(zhí)行策略產(chǎn)生的數(shù)據(jù)進行迭代優(yōu)化。執(zhí)行策略采用ε-貪婪，保證了訓(xùn)練過程的探索性，使每個動作都有可能被探索到，不容易陷入局部最優(yōu)：

(4)

π(x)=argmaxa″Q(x,a″)

(5)

1.2 仿真實現(xiàn)

仿真通過微觀交通仿真器SUMO(Simulation of Urban Mobility)[30]實現(xiàn)。SUMO用連續(xù)的笛卡爾坐標(biāo)系表示車輛位置、等時間間隔更新車輛狀態(tài)和位置，以及空間連續(xù)和時間離散[31]。實時交通信息包括車輛的目的地和當(dāng)前位置以及道路的平均通行時間的獲取、車輛的行駛路徑的改變通過控制接口(Traffic Control Interface, TraCI)實現(xiàn)。

1.2.1 路網(wǎng)和流量

仿真中道路網(wǎng)絡(luò)為一個6×3的矩形網(wǎng)絡(luò)，東西向和南北向路段長分別為200m和100m，如圖3所示。路口無信號燈、采用默認(rèn)的南北優(yōu)先。以最小時間間隔從A1B1到E1F1輸入100輛車，采用默認(rèn)的Krauss car-following模型。靜態(tài)路徑引導(dǎo)得到的最短路徑為〈A1B1 B1C1 C1D1 D1E1 E1F1〉。

圖3 規(guī)則路網(wǎng)

1.2.2 事件場景

圖4 事件場景

1.2.3 引導(dǎo)方式

考慮靜態(tài)路徑引導(dǎo)和動態(tài)路徑引導(dǎo)的幾種方式：1)靜態(tài)引導(dǎo)：只根據(jù)靜態(tài)路網(wǎng)信息，用最短路徑算法生成時間最短路徑。2)一次性動態(tài)引導(dǎo)：在車輛進入路網(wǎng)時，根據(jù)該時刻實時路網(wǎng)信息，進行一次性的引導(dǎo)；3)周期性同時引導(dǎo)：按時間間隔τ，更新全局信息并對路網(wǎng)中所有車輛同時進行引導(dǎo)；4)周期性各自引導(dǎo)：從車輛各自發(fā)車時刻開始，按時間間隔τ，更新全局信息，進行單獨引導(dǎo)。

2 仿真結(jié)果

2.1 一次性動態(tài)引導(dǎo)

圖5 動態(tài)路徑引導(dǎo)

圖6 動態(tài)路徑引導(dǎo)中的博弈

經(jīng)過整個路網(wǎng)的車輛行駛距離如圖7所示。圖7中，行駛距離較長的車輛對應(yīng)采取博弈行為繞路的車輛。較長行駛距離的頻率隨著車輛編號增加，可見博弈的正反饋趨勢。

圖7 一次性動態(tài)引導(dǎo)下車輛的行駛距離

2.2 周期性動態(tài)引導(dǎo)

在2.1的路網(wǎng)基礎(chǔ)上僅保留坑洼路段、去除兩處故障擁堵，賦予道路更大的自由度。如圖8所示，博弈強度隨著路網(wǎng)的自由度變大而增強，在目的地E1F1前的交叉口E1匯聚了來自各個方向的車流。

圖8 終點前交叉口E1發(fā)生擁堵

首先考慮引導(dǎo)頻率即不同時間間隔τ對動態(tài)路徑引導(dǎo)的影響。τ越小，引導(dǎo)越頻繁；τ越大，車輛上一次引導(dǎo)的保持時間越長。受限于路網(wǎng)大小，τ>30時，在周期性同時引導(dǎo)中會出現(xiàn)尚未對車輛進行引導(dǎo)車輛就已駛?cè)肟油萋范蔚那闆r。因此取τ=1,2,3,…,30，同時引導(dǎo)和各自引導(dǎo)在不同τ下的平均行駛距離、通行時間和等待時間如圖9所示。注意到，同時引導(dǎo)和各自引導(dǎo)在τ=1時是等價的，因此兩子圖在τ=1的數(shù)值相同。

圖9 不同時間間隔τ下的平均通行時間、平均等待時間和平均行駛距離

車輛的平均行駛距離反應(yīng)了整體的博弈強度。隨著τ的增大，引導(dǎo)頻率降低，車輛維持上一次引導(dǎo)的時間變長，平均行駛距離整體呈現(xiàn)下降趨勢，博弈強度減小。其中，同時引導(dǎo)的博弈強度隨著τ的下降速度更快?？紤]到同時引導(dǎo)會使處于相同狀態(tài)即位于同一條道路上的車輛采取相同動作，當(dāng)τ較大時，同時引導(dǎo)更容易形成車隊。而引導(dǎo)一旦采取了與τ時刻前不同的動作路徑，在引導(dǎo)的早期階段一般都是博弈行為，博弈的結(jié)果是路徑經(jīng)過優(yōu)先級較高的南北向。此時同時引導(dǎo)因為產(chǎn)生車隊，在優(yōu)先級的路口更具有競爭優(yōu)勢，能夠較快通行、減少行駛距離；但產(chǎn)生的后果是會有車隊整體被更高優(yōu)先級路口的其他車隊較長時間截斷，因此即使行駛距離降低較快，但在平均通行時間和等待時間上并無明顯優(yōu)勢。各自引導(dǎo)可視為τ批次的同時引導(dǎo)，因此在引導(dǎo)頻率的兩極，即τ<13或τ>23時，不同批次的車輛實際上所處的狀態(tài)在引導(dǎo)早期階段基本相同，效果和同時引導(dǎo)相近；在τ=15左右時，各自引導(dǎo)呈現(xiàn)出對交通信息更為敏感的特性，平均行駛距離較長、平均等待時間較長，表明其充分利用了路網(wǎng)資源但又受限于路口優(yōu)先級。

為了進一步比較4種引導(dǎo)方式，通過路網(wǎng)中車輛數(shù)量和到達車輛的平均行駛時間這兩個指標(biāo)進行對比。取τ=5，10，15，20，25，結(jié)果如圖10所示。在兩個指標(biāo)上，動態(tài)路徑引導(dǎo)都明顯優(yōu)于靜態(tài)路徑引導(dǎo)如圖10a，10b所示，能夠明顯減少路網(wǎng)中車輛數(shù)量，降低所有車輛通過路網(wǎng)的用時。此外，如圖10c，10d所示，到達車輛的平均行駛時間呈上升趨勢，意味著車輛在交叉口的等待是影響其通過路網(wǎng)用時的主要因素之一。

圖10 路網(wǎng)中車數(shù)和到達車輛平均行駛時間隨仿真時間的變化趨勢

最后，為了進一步探究周期性引導(dǎo)兩種方式與一次性引導(dǎo)的區(qū)別，比較了靜態(tài)引導(dǎo)、一次性引導(dǎo)以及兩種周期性引導(dǎo)τ=15按車輛到達次序的總通行時間、等待時間和非等待時間，結(jié)果如圖11所示。圖11a中靜態(tài)引導(dǎo)的車輛全體經(jīng)過了坑洼路段，總通行時間與非等待時間重合，整個過程車流沒有停滯，但前60輛車的用時不斷增加，說明車隊在行駛過程中會受到駕駛員差異的影響。圖11b～11d中，非等待時間均處于[100,200]區(qū)間內(nèi)，說明當(dāng)車輛運動時，基本上以較快速度行駛，其通行時間差異主要由等待時間引起。一次性引導(dǎo)中，最后到達的一部分車輛都經(jīng)歷了長時間等待，即圖8所示的目的地前的擁堵；而周期性引導(dǎo)通過基于實時交通信息的多次引導(dǎo)能緩解這部分潛在的擁堵，但也在一定程度上造成了提前的小規(guī)模長時間等待。另外，如圖11d所示，各自引導(dǎo)的等待時間呈現(xiàn)多個尖峰，說明有個別車輛經(jīng)歷了長時間的等待，成為引導(dǎo)過程中的信息敏感性對出行個體帶來的不穩(wěn)定性的犧牲品。

圖11 總通行時間、等待時間及非等待時間與到達次序的關(guān)系

3 結(jié)論

本文提出了基于實時交通數(shù)據(jù)的交通信息物理系統(tǒng)框架，對利用實時交通信息的動態(tài)路徑引導(dǎo)的策略和頻率進行了研究。仿真結(jié)果表明，相對基于拓?fù)湫畔⒌撵o態(tài)引導(dǎo)，動態(tài)引導(dǎo)策略具有優(yōu)勢，能夠明顯地提升道路通行能力，更充分地利用路網(wǎng)資源。然而，在不同的動態(tài)引導(dǎo)策略中，對路網(wǎng)中所有車輛進行高頻率的引導(dǎo)，相對更長周期的引導(dǎo)并不具有明顯優(yōu)勢；周期性引導(dǎo)能夠在一定程度上緩解一次性引導(dǎo)中潛在的擁堵問題；各自引導(dǎo)和同時引導(dǎo)兩種策略在引導(dǎo)頻率較高和較低時具有一定相似性，而在引導(dǎo)頻率處于中間范圍時，各自引導(dǎo)策略的博弈強度更大。系統(tǒng)仿真實驗對路網(wǎng)設(shè)置和框架中路徑引導(dǎo)策略的選取較為簡單，后續(xù)可以考慮在真實路網(wǎng)中選用更復(fù)雜的一系列引導(dǎo)方案進行驗證。此外，將引導(dǎo)頻率與道路網(wǎng)絡(luò)特征相結(jié)合，將是本研究的一個很好的延續(xù)。