溫惠英 林譯峰 吳昊書 蔣晗 吳嘉彬?

(1．華南理工大學(xué) 土木與交通學(xué)院,廣東 廣州 510640;2．華南農(nóng)業(yè)大學(xué) 林學(xué)與風(fēng)景園林學(xué)院,廣東 廣州 510640)

在城市路網(wǎng)中，交通流狀態(tài)受多種因素影響，隨時間推移不斷變化，例如交通事故、信號控制、路網(wǎng)結(jié)構(gòu)、通行能力、出行規(guī)律、駕駛行為特性、交通擁堵、惡劣天氣以及自然災(zāi)害等。由于交通事件具有明顯的隨機性與突發(fā)性，難以提前預(yù)測其發(fā)生時間和地點，故交通事故的應(yīng)急救援工作不可避免地存在滯后性。因此，如何在復(fù)雜多變的城市路網(wǎng)交通環(huán)境中快速地執(zhí)行救援工作是應(yīng)急救援環(huán)節(jié)中最為關(guān)鍵的問題[1-3]。路徑規(guī)劃作為應(yīng)急救援的重要環(huán)節(jié)，影響救援行程時間長短與穩(wěn)定性。穩(wěn)定可靠的救援路徑有利于救援人員在盡可能短時間內(nèi)拯救更多的生命，及時控制事故嚴重性與影響范圍，有效降低經(jīng)濟損失。

常用的路徑規(guī)劃方法有兩種，即靜態(tài)路徑規(guī)劃和動態(tài)路徑規(guī)劃。作為經(jīng)典的路徑優(yōu)化方法，靜態(tài)路徑規(guī)劃的基本思想是在靜態(tài)交通路網(wǎng)下搜索兩點間的最短路徑。已有大量學(xué)者鉆研靜態(tài)路徑優(yōu)化方法相關(guān)理論，并取得了豐富的研究成果與實踐經(jīng)驗。多數(shù)靜態(tài)路徑規(guī)劃方法的研究是基于具體的應(yīng)用場景，解決實際問題，例如應(yīng)急救援[4-11]。在應(yīng)急救援路徑規(guī)劃中，靜態(tài)路徑優(yōu)化的應(yīng)用較為普遍，常用的方法有Dijkstra算法、蟻群算法、SPFA(Shortest Path Faster Algorithm)、雙層優(yōu)化方法等，其中最常見的是Dijkstra算法[12-14]。

在實際的城市路網(wǎng)中，路徑規(guī)劃受到動態(tài)交通環(huán)境的影響，而交通環(huán)境的演變具有顯著的時空特性。在時變特性方面，路網(wǎng)交通環(huán)境隨時間演變，受路段交通流狀態(tài)與交叉口通行規(guī)則的影響，如常發(fā)性交通擁堵、信號控制等[15-16]。在空間分布特性方面，同一時刻下同一路段不同方向或不同路段的交通流狀態(tài)差異明顯?？紤]路網(wǎng)動態(tài)交通環(huán)境對路徑規(guī)劃的影響，學(xué)者們致力于研究如何提升動態(tài)優(yōu)化方法的實時性與優(yōu)化性能，而在線優(yōu)化方法(OLRO)是解決動態(tài)路徑規(guī)劃問題的主流手段[17-18]。在線優(yōu)化方法的基本思想是基于當(dāng)前路網(wǎng)交通環(huán)境下快速尋找起終點間的最短路徑，并根據(jù)路網(wǎng)交通環(huán)境的演變實時更新剩余優(yōu)化路徑，直到車輛抵達目的地。常見的在線優(yōu)化方法有單源優(yōu)化算法、啟發(fā)式算法與機器學(xué)習(xí)算法等[19-23]。然而，OLRO方法僅考慮當(dāng)前路網(wǎng)交通環(huán)境狀態(tài)，忽略了路網(wǎng)交通環(huán)境的未來演變趨勢對路徑優(yōu)化的影響，將動態(tài)路徑規(guī)劃視為多個靜態(tài)路徑規(guī)劃在不同時間維度的簡單組合，容易導(dǎo)致多余的繞行并增加行程時間。

為解決該問題，Hu等[24]提出了一種協(xié)同優(yōu)化方法(CEPO)，在給定的動態(tài)路網(wǎng)環(huán)境下解決路徑規(guī)劃問題。為進一步研究路網(wǎng)動態(tài)因素與不確定性對路徑規(guī)劃的影響，Wen等[25]集成CEPO和OLRO優(yōu)化特性，提出了一種定時協(xié)同優(yōu)化方法(TCEPO)，在預(yù)測路網(wǎng)狀態(tài)變化的基礎(chǔ)上，基于交通環(huán)境演變趨勢協(xié)同優(yōu)化救援路徑，并定時修正不確定性對路徑規(guī)劃造成的影響,以增強行程時間穩(wěn)定性。但是當(dāng)數(shù)據(jù)條件受限時，TCEPO的誤差會隨著計算過程的推進而增加，降低優(yōu)化效果。受TCEPO方法的啟發(fā)，文中在傳統(tǒng)A*算法框架的基礎(chǔ)上引入TCEPO模型優(yōu)化原理，基于城市路網(wǎng)交通流的動態(tài)演變和可預(yù)測性，提出了一種可擴展協(xié)同進化算法(ECEA)。該算法可用于探索城市道路交通環(huán)境變化下應(yīng)急救援路徑規(guī)劃問題的解決方案，以提高應(yīng)急救援效率及其魯棒性[26-29]。

1 城市路網(wǎng)交通環(huán)境運行特征

1.1 交叉口運行特征

為提高交叉口安全水平與通行效率，城市路網(wǎng)交叉口常配備較為先進的信號控制設(shè)施。盡管救援車輛到達信號控制交叉口時可不受信號燈約束，但其運行狀態(tài)受限于前方社會車輛在交叉口的排隊或減速行為，常被迫停車或減速，進而產(chǎn)生行程延誤[30-31]。若救援車輛通過無信號控制交叉口，則可能因減速避讓其他機動車、非機動車或行人等交通參與者而產(chǎn)生行程延誤。因此，在城市路網(wǎng)行駛過程中，救援車輛通過交叉口時產(chǎn)生的交通延誤往往難以避免且其影響不容忽視，是救援行程時間的重要組成部分。

1.2 路段交通流的時空特征

由于道路類型、地理位置、路段長度、路段限速等道路條件存在顯著差異，路網(wǎng)交通流在時間與空間分布上具備不均衡性，這種不均勻的現(xiàn)象可概括為交通流的時空分布特征。在微觀層面，該特征與駕駛員行為特性存在密切聯(lián)系，可從駕駛員行為角度進行描述與解釋[32-33]。鑒于路徑規(guī)劃效果與路網(wǎng)交通流演變息息相關(guān)，文中主要從以下3個方面對交通流演變進行剖析與定義：

(1)由于大多數(shù)城市道路未設(shè)置專用的應(yīng)急車道，救援車輛在城市路網(wǎng)中行駛時易受到周圍社會車輛的影響。不同駕駛員的駕駛行為差異化明顯，對于安全駕駛的理解存在較大偏差。部分不良駕駛行為容易擾亂交通流的穩(wěn)定運行，甚至?xí)斐陕范紊系慕煌〒矶?，是造成交通流紊流、不連續(xù)的主要原因，例如突然變道、連續(xù)換道等[34-35]。

(2)交通流時間分布差異是指同一路段的交通流在不同時間段存在的差異。例如，若某一路段受到交通擁堵影響，其車流平均速度將在短時間內(nèi)迅速下降；當(dāng)擁堵范圍與負面影響隨著時間推移而逐漸消散，其車流速度將逐漸恢復(fù)至正常。

(3)交通流空間分布差異是指同一時刻下不同路段或同一路段的不同方向車流平均速度存在的偏差。一般而言，市中心區(qū)域車流較多，交通負荷較大，對應(yīng)路段上的交通流速度相對較低。相對而言，城市郊區(qū)車流密度與道路負荷較小，交通流運行速度相對較高。

2 ECEA算法

2.1 目標函數(shù)

在城市路網(wǎng)中，交叉口被視為連接多條路段的“節(jié)點”。盡管節(jié)點間的路段長度固定，但其交通環(huán)境隨時間動態(tài)演變，影響車輛群行駛快慢。車輛通過某一路段的行車時間由路段長度、交通流狀態(tài)與駕駛員特性等多種因素共同決定。換言之，距離最短的路徑不一定等同于行程時間最短的路徑。由于城市應(yīng)急救援對出行時效性具有嚴格的要求，故行程時間最小化是應(yīng)急救援路徑規(guī)劃的主要目標，而非行駛距離最小。其目標函數(shù)可用下式表達：

minC=f(O,D,R*)

(1)

式中，C表示救援行程時間，R*表示求解的優(yōu)化路徑，f是計算路徑R*行程時間的函數(shù)，O表示路徑R*的起點，D表示路徑R*的終點。

2.2 參數(shù)定義

為方便理解本文所涉及參數(shù)的含義，表1列出了本文部分參數(shù)及其實際含義。

表1 參數(shù)及其含義Table 1 List of symbols and meanings

2.3 基本原理

本文所提ECEA算法原理包括兩部分：一是搜索并確定車輛行駛的下一目標節(jié)點，二是隨車輛行駛更新路徑。如圖1所示，ECEA算法通過預(yù)測路網(wǎng)交通環(huán)境狀態(tài)的變化計算子路徑，根據(jù)子路徑篩選車輛行駛的下一目標節(jié)點；當(dāng)車輛到達目標節(jié)點時，ECEA算法將根據(jù)路網(wǎng)交通環(huán)境的變化對子路徑進行修正和更新，直至車輛到達終點。

圖1 ECEA算法基本原理Fig.1 Illustration of the basic idea for the proposed ECEA

圖1中，子路徑的計算與下一目標節(jié)點推導(dǎo)由ECEA算法中節(jié)點的F值確定，即：

F(i)=G(i)+H(i)

(2)

式中，G(i)表示從當(dāng)前位置到節(jié)點i的移動代價，H(i)表示從節(jié)點i到終點的估算代價。在尋找下一目標節(jié)點的過程中，ECEA算法比較當(dāng)前位置節(jié)點搜索范圍內(nèi)所有備選節(jié)點的F值，通過計算當(dāng)前位置節(jié)點與F值最小的備選節(jié)點間的子路徑，推導(dǎo)并行駛至下一目標節(jié)點，并隨車輛行駛實時更新路網(wǎng)交通環(huán)境，不斷迭代更新子路徑。若終點在搜索范圍內(nèi)，則通過回溯方法得到完整的優(yōu)化路徑。因此，ECEA算法不僅具有根據(jù)實時修正路網(wǎng)交通環(huán)境演變的特性，還考慮了未來路網(wǎng)交通環(huán)境演變趨勢對路徑規(guī)劃的影響，進而實現(xiàn)救援路徑與路網(wǎng)交通環(huán)境的協(xié)同優(yōu)化。

2.4 算法步驟

2.4.1 優(yōu)化流程

ECEA算法的優(yōu)化流程如圖2所示。步驟1到步驟7表示在預(yù)測路網(wǎng)交通環(huán)境條件下篩選最佳下一目標節(jié)點的過程；步驟8到步驟12給出了救援車輛行駛至下一目標節(jié)點的實際運算過程。步驟1初始化變量；步驟2標定路網(wǎng)起點為當(dāng)前節(jié)點；步驟3根據(jù)當(dāng)前節(jié)點和設(shè)定的搜索層數(shù)，通過備選節(jié)點搜索模塊篩選出所有的備選節(jié)點np；步驟4運用式(2)計算步驟3中所有備選節(jié)點np的F值，然后回溯推導(dǎo)得到路徑R(nc,np)，拼接R(Oc,nc)與R(nc,np)形成完整路徑R(Oc,np)，并通過對比更新機制操作Olist：若np不在Olist中，則將np加入Olist，并將F(np)記錄為Fm(np)；若np已經(jīng)在Olist中，則通過式(3)判斷是否需要更新Fm(np)。

圖2 ECEA算法步驟Fig.2 Algorithm steps of ECEA

(3)

式中，F(xiàn)m(np)表示節(jié)點np原有的F值，F(xiàn)(np)表示節(jié)點np在當(dāng)前步驟計算得到的F值。若F(np)

2.4.2F值計算模塊

由式(2)可知，F(xiàn)值由G值和H值組成。為了有效篩選最佳的下一目標節(jié)點，本文中引入波紋擴散算法(RSA)協(xié)同路網(wǎng)交通環(huán)境變化，推導(dǎo)當(dāng)前節(jié)點與備選節(jié)點之間的G(i)值，優(yōu)化G(i)值的計算過程。作為一種新興的算法，RSA算法在計算路網(wǎng)兩點間的移動代價時有速度快、精度高等優(yōu)勢，其協(xié)同優(yōu)化機制與路網(wǎng)交通環(huán)境演變高度契合，具體運算過程如圖3所示。

圖3 RSA算法運算流程圖Fig.3 Flowchart of ripple spread algorithm

圖3中，T=0表示當(dāng)前時間單元，k=n(n=1,2,…,6)表示在當(dāng)前時刻下往后預(yù)測的第n個時間單元。路網(wǎng)節(jié)點存在4種狀態(tài)，即未激活、等待、已激活和死亡，且所有節(jié)點初始狀態(tài)均為未激活。k=1時，波紋從起點處激活向四周鄰近節(jié)點擴散。k=2時，從1號起點激發(fā)的波紋到達4號節(jié)點并將其激活，波紋繼續(xù)向鄰近未被激活的節(jié)點擴散。k=3時，1號節(jié)點波紋激活2號節(jié)點后產(chǎn)生新的波紋，新生波紋在2號節(jié)點停留一段時間，模擬車輛到達交叉口的排隊行為，進入等待狀態(tài)。k=4時，2號節(jié)點轉(zhuǎn)為激活狀態(tài)，其波紋向鄰近節(jié)點擴散，并激活未被其他波紋訪問過的節(jié)點。k=5時，波紋抵達3號節(jié)點，因其所有鄰近節(jié)點均被波紋訪問過，故停止激發(fā)新的波紋，轉(zhuǎn)變?yōu)樗劳鰻顟B(tài)。波紋的擴散過程隨著時間推移不斷進行，其擴散速度與動態(tài)演變的路網(wǎng)交通環(huán)境協(xié)同變化。k=6時，從6號節(jié)點激發(fā)的波紋到達終點，終止波紋擴散過程，并從終點開始回溯該波紋遍歷節(jié)點的記錄，得到起點與終點節(jié)點間的最優(yōu)路徑。

引入RSA算法優(yōu)化G值，計算式為：

(4)

式中，t表示在預(yù)測道路交通環(huán)境下從節(jié)點nc到節(jié)點np所需要經(jīng)歷的時間單元數(shù)，T表示救援車輛到達節(jié)點nc時所處的時間單元，CT|T+k(nc,np)表示在預(yù)測時間單元T+k內(nèi)通過路段(nc,np)所需的行程時間。G值從起點開始不斷迭代計算，該過程與道路交通環(huán)境協(xié)同演變，起點O的G值為0，即G(O)=0。

在實際行駛時，G值根據(jù)預(yù)測路網(wǎng)交通環(huán)境數(shù)據(jù)推導(dǎo)得到，與實際G值存在偏差。因此，在確定下一節(jié)點后，ECEA算法基于實際路網(wǎng)交通環(huán)境數(shù)據(jù)迭代更新G值。

H值的計算式為：

(5)

式中，L(np,D)表示從節(jié)點np至終點D的直線距離；Vave表示暢通路段車流的平均行駛速度。H值的計算可參考A*算法原理，此處不作贅述。

2.4.3 備選節(jié)點搜索模塊

由ECEA算法優(yōu)化流程可知，在計算G值時，首先需要根據(jù)當(dāng)前節(jié)點位置和搜索層數(shù)搜索所有備選節(jié)點np。假設(shè)集合M用于記錄G(i)值計算過程中搜索范圍內(nèi)的所有備選節(jié)點，令l表示G(i)的搜索層數(shù)。在ECEA算法中，l≥1，如圖4所示。搜索過程需要滿足以下條件：

圖4 不同搜索層數(shù)的備選節(jié)點Fig.4 Candidate nodes of different search levels

(1)在搜索開始前，將當(dāng)前節(jié)點加入到M中，并將其標記為已被搜索過的節(jié)點，隨后進行第1層搜索。

(2)在每一層的搜索中，ECEA搜索的對象是在上一層搜索中所得到的集合M中的所有備選節(jié)點，基于上一層備選節(jié)點迭代搜索鄰接節(jié)點，若鄰接節(jié)點未被遍歷搜索，則將其視為新增節(jié)點。

(3)每一層搜索結(jié)束后，更新集合M中的所有備選節(jié)點。將集合M中的所有原有備選節(jié)點移除，再把該層搜索得到的新增節(jié)點加入到集合M，并令l的值增加1。當(dāng)l值達到預(yù)設(shè)值時，集合M中所有節(jié)點均為該層的備選節(jié)點，即G(i)值的計算對象。

3 實驗分析

本文在矩形區(qū)域內(nèi)隨機均勻設(shè)置N個節(jié)點生成城市路網(wǎng)拓撲結(jié)構(gòu)，路徑起點為路網(wǎng)左下角，終點為路網(wǎng)右上角。仿真路網(wǎng)規(guī)模分為4類，即N∈{400，900,1 600，2 500}。為模擬城市道路交通實際運行環(huán)境，提出以下3種假設(shè)：

(1)交叉口的運行特征決定了救援車輛通過交叉口時會產(chǎn)生行程延誤。令d(i)表示節(jié)點i的延誤，取值范圍為[20,60]，單位為s。當(dāng)波紋到達節(jié)點i時，需要等待d(i)時間，其行程時間隨之增加。

(2)城市路網(wǎng)交通擁堵隨著時間推移分為擴散和消散兩個過程。每隔10～15個節(jié)點設(shè)置一個交通擁堵中心點(簡稱“中心點”)，即擁堵源頭。擁堵范圍隨時間推移而擴散，中心點的鄰接節(jié)點逐漸成為擁堵節(jié)點，并不斷擴散傳遞擁堵狀態(tài)，此時節(jié)點延誤是暢通狀態(tài)下的兩倍。當(dāng)擁堵區(qū)域擴張至一定規(guī)模時，擁堵開始消散，擁堵區(qū)域由外向內(nèi)逐層收縮至中心點為止。

如圖5所示，黃色區(qū)域表示城市路網(wǎng)的擁堵區(qū)域，根據(jù)擁堵的變化方向，在同一時刻下，區(qū)域1和區(qū)域4正在擴散，表示擁堵正在不斷傳遞；區(qū)域2和區(qū)域3正在收縮，表示擁堵正在逐漸消散。

圖5 擁堵區(qū)域變化示意圖Fig.5 Congestion evolution process in network(N=400)

(3)道路交通環(huán)境變化體現(xiàn)為各路段車流平均速度的動態(tài)演變。在各時間單元內(nèi)生成各路段的平均速度，且路段初始平均速度V0服從N(40,5)的正態(tài)分布模型，取值范圍為[20,60]，單位:km/h。令時間單元T的長度為60 s。根據(jù)城市路網(wǎng)交通流的時空特征，隨著時間單元的推移，各路段平均速度在[-4,4]km/h范圍內(nèi)隨機變化。若路段處于擁堵狀態(tài)，路段平均速度將下降至[0,5]km/h的范圍。

3.1 實驗1 算法搜索層數(shù)優(yōu)化分析

為了探索搜索層數(shù)對路徑規(guī)劃優(yōu)化性能的影響，實驗1以N=400路網(wǎng)為例，選取搜索層數(shù)范圍為[1,10]，并忽略預(yù)測誤差對優(yōu)化結(jié)果的影響。實驗所用計算機的參數(shù)如下：CPU處理器型號為Intel(R)Core(TM)i5-6500U，內(nèi)存為4 GB，操作系統(tǒng)為Windows 64bit。搜索層數(shù)優(yōu)化分析結(jié)果如圖6所示。

由圖6(a)可知，搜索層數(shù)較小時，行程時間隨著搜索層數(shù)的增加呈現(xiàn)快速下降的趨勢，當(dāng)搜索層數(shù)增加到5層時，行程時間最??；5層之后，繼續(xù)增加搜索層數(shù)，行程時間無明顯變化。由圖6(b)可知，隨著搜索層數(shù)的增加，算法運算時間基本上處于平緩波動狀態(tài)。根據(jù)ECEA的計算原理可知，計算時間的決定因素有二：一是優(yōu)化次數(shù)，二是遍歷備選節(jié)點所需時間。當(dāng)搜索層數(shù)增加時，一方面，下一目標節(jié)點的選擇范圍擴大，遍歷時間增加；另一方面，優(yōu)化次數(shù)可能會減小。因此，ECEA算法的計算時間與搜索層數(shù)無明顯正或負相關(guān)性。為提高算法優(yōu)化性能，降低運算負荷，本文選取算法搜索層數(shù)為5，用于實驗2與實驗3的計算。

圖6 ECEA不同搜索層數(shù)的性能分析(N=400)Fig.6 Performance analysis of different search levels for ECEA(N=400)

3.2 實驗2 無預(yù)測誤差下的算法性能分析

隨著計算機科學(xué)的快速發(fā)展，路網(wǎng)交通環(huán)境演變趨勢或多或少可利用交通流預(yù)測算法進行預(yù)測。為凸顯ECEA算法在城市路網(wǎng)的優(yōu)化性能，選擇TCEPO、A*算法與Dijkstra算法作為對比算法，其中TCEPO是協(xié)同優(yōu)化方法，A*算法與Dijkstra算法是在線優(yōu)化方法。圖7給出了ECEA、TCEPO、A*算法與Dijkstra算法在無預(yù)測誤差時不同路網(wǎng)下20次測試的平均計算結(jié)果。tTT表示行程時間,min;tCT表示運算時間,s;lPL表示路徑長度,km;δTD表示行程延誤,min。

δTD的計算方法如式(6)所示，Vd表示城市道路設(shè)計行駛速度，本文取Vd=60 km/h。

(6)

由圖7(a)可知，在tTT方面，ECEA優(yōu)于TCEPO、A*算法與Dijkstra算法。ECEA輸出路徑的行程時間比TCEPO短8.48%～30.9%,比A*短18.74%～43.3%，比Dijkstra算法短22.46%～35.18%。

由圖7(b)可知，在tCT方面，ECEA最長，TCEPO次之。隨著路網(wǎng)規(guī)模的擴大，4種算法的計算時間逐漸增加。盡管ECEA的計算時間最大，但并不影響ECEA規(guī)劃路徑的應(yīng)用可行性。

由圖7(c)可知，在lPL方面，TCEPO最短，ECEA次之。其中，ECEA比A*算法短了7.07%～25.37%，比Dijkstra算法短了4.81%～19.15%。

圖7 4種算法在無預(yù)測誤差時不同路網(wǎng)下的計算結(jié)果Fig.7 Average results of four algorithms under different networks without predicted errorECEA TCEPO A*Dijkstra

由圖7(d)可知，在δTD方面，ECEA最小，比TCEPO降低17.65%～51.48%，比A*算法降低26.9%～54.55%，比Dijkstra算法降低33.33%～48.05%。

3.3 實驗3 不同預(yù)測誤差下的算法性能分析

盡管各類先進的交通流預(yù)測算法層出不窮，但其預(yù)測結(jié)果難以達到絕對精確。為清晰表示路段車流平均速度預(yù)測值與實際值之間的關(guān)系，引入速度預(yù)測誤差參數(shù)φ，則有：

VT+k(i,j)=VT|T+k(i,j)×(1+φ)

(5)

式中，VT+k(i,j)表示路段(i,j)在時間單元T+k的路段車流平均速度實際值；VT|T+k(i,j)表示路段(i,j)在預(yù)測時間單元T|T+k的路段車流平均速度預(yù)測值。圖8分別給出了4種算法在不同預(yù)測誤差下20次運算的平均結(jié)果(φ=[ 0.05,0.1])。

圖8 4種算法在不同預(yù)測誤差下的平均結(jié)果Fig.8 Average results of four algorithms under different predicted error φ

由圖8可知，在考慮預(yù)測誤差的情況下，ECEA在行程時間和行程延誤方面仍優(yōu)于TCEPO及其它兩種在線優(yōu)化方法，在運算時間上雖為最長，在路徑長度上要優(yōu)于A*算法和Dijkstra算法。盡管ECEA在φ=0時優(yōu)化效果最小，但始終保持降低20%左右的行程時間。這主要是因為ECEA每次達到目標節(jié)點時自動更新路網(wǎng)交通數(shù)據(jù)，重新規(guī)劃剩余路徑，以修正累積的預(yù)測誤差。且隨著預(yù)測誤差的增加，ECEA的優(yōu)化幅度總體上逐漸增加。例如，相比于TCEPO，在φ=0時，ECEA縮短了20.5%的行程時間，當(dāng)φ=0.05時，優(yōu)化幅度達到23.65%，φ=0.10時優(yōu)化幅度達到27.35%。這說明ECEA對于預(yù)測誤差的包容性更好，在不同的預(yù)測誤差下，能夠始終保持較好優(yōu)化性能。

圖9是4種算法分別在不同預(yù)測誤差條件下運算輸出20次tTT結(jié)果的分布狀況。ECEA穩(wěn)定性優(yōu)于TCEPO、A*算法和Dijkstra算法，且所有運算結(jié)果在較小范圍內(nèi)波動。且隨著路網(wǎng)規(guī)模的擴大，ECEA優(yōu)化效果明顯。由此可見，ECEA在城市道路交通環(huán)境動態(tài)演變下優(yōu)化路徑的抗干擾能力更強，更適合應(yīng)對城市道路交通環(huán)境中難以預(yù)測的突發(fā)狀況。

圖9 4種算法在不同路網(wǎng)規(guī)模的行程時間穩(wěn)定性對比Fig.9 Comparative results of travelling time reliability for four algorithms on different road network scales

4 討論

在行程時間方面，ECEA要優(yōu)于TCEPO、A*算法和Dijkstra算法。這主要是因為ECEA的協(xié)同優(yōu)化機制能夠提前避開擁堵區(qū)域，避免不必要的繞行，從而減少行駛過程中所遭遇的擁堵延誤。此外，相比于TCEPO，ECEA優(yōu)化間隔短、搜索范圍大，能夠在盡可能獲取最佳下一目標節(jié)點的同時有效控制預(yù)測優(yōu)化和協(xié)同計算過程中的誤差。基于在線優(yōu)化的傳統(tǒng)方法在每一步計算時，僅考慮當(dāng)前時刻的路網(wǎng)狀態(tài)規(guī)劃救援路徑，忽略未來路網(wǎng)交通環(huán)境演變對路徑規(guī)劃造成的干擾，尤其是在應(yīng)對擁堵演變方面存在嚴重的時滯性，得到的結(jié)果是僅在當(dāng)前時刻下的最優(yōu)解。

在運算時間方面，ECEA在不同路網(wǎng)規(guī)模中的計算時間均為最長，且隨著路網(wǎng)規(guī)模的擴大而增加。這主要是因為較大的搜索范圍使得ECEA每一子步驟均需計算更多的節(jié)點，且需同時兼顧道路交通環(huán)境演變。盡管ECEA每次計算時間相對較長，但因計算時間遠小于每次運算優(yōu)化的時間間隔，故不影響其應(yīng)用實時性。

在路徑長度方面，ECEA比其他兩種在線優(yōu)化算法短，而比TCEPO長。這主要是因為ECEA能在到達擁堵區(qū)域前做出正確的繞路決策，或在即將消散的擁堵區(qū)域選擇暫時等待，從而避免冗余的繞行。此外，ECEA是根據(jù)節(jié)點位置來進行優(yōu)化的，優(yōu)化次數(shù)較多，因而優(yōu)化路徑的長度比TCEPO長，但是在行程時間上有明顯縮短。

在行程延誤方面，ECEA要優(yōu)于TCEPO、A*算法和Dijkstra算法，這主要是因為ECEA的行程時間最短，且其路徑長度相對較短，僅次于TCECO。因此，在行駛速度相同的情況下，ECEA的行程延誤最小。

5 結(jié)語

本文提出一種可擴展協(xié)同優(yōu)化算法(ECEA)規(guī)劃救援路徑，以縮短應(yīng)急救援行程時間。ECEA考慮了城市車輛運行特性與交通環(huán)境演變，使路徑優(yōu)化步驟與交通環(huán)境演變協(xié)同進行，減少交通擁堵等因素對路徑規(guī)劃的影響，并動態(tài)調(diào)整救援路徑。

文中ECEA的搜索層數(shù)越大，其優(yōu)化路徑的行程時間越小。當(dāng)搜索層數(shù)為5時，行程時間最小且趨于平穩(wěn)。在行程時間方面，ECEA優(yōu)于TCEPO、A*算法和Dijkstra算法，比TCEPO短8.48%～33.22%，比A*短18.74%～46.4%,比Dijkstra算法短22.46%～38.1%。在運算時間方面，雖然ECEA略大于其他算法，但在可接受范圍內(nèi)，不影響其在實際應(yīng)用中的實時性。在路徑長度方面，TCEPO最短，ECEA次之，比A*算法短7.07%～26.85%，比Dijkstra算法短4.81%～19.15%。在行程延誤方面，ECEA優(yōu)于TCEPO、A*算法和Dijkstra算法，比TCEPO低17.65%～53.5%，比A*算法低26.9%～57%,比Dijkstra算法低32%～51.5%。最后，在考慮預(yù)測誤差的情況下，ECEA依然能夠保持良好的優(yōu)化性能，呈現(xiàn)強魯棒性。

為進一步提升ECEA算法性能，下一步工作擬從以下兩方面開展：(1)通過改善算法的邏輯框架和完善數(shù)據(jù)結(jié)構(gòu)，縮短ECEA的運算時間；(2)與更多算法做對比，驗證ECEA算法的有效性和可靠性。