基于交通時空特征的車輛全局路徑規(guī)劃算法

杜 茂，楊 林，金 悅，涂家毓

（上海交通大學 機械與動力工程學院，上海 200240， 中國）

車輛路徑問題（vehicle routing problem, VRP）的一個重要研究領域即是時間依賴型車輛路徑問題（time dependent vehicle routing problem, TDVRP）。如何為出行車輛提供可靠的全程最低行程時間或者能耗路徑依然是TDVRP問題的難點之一。

在路徑耗時方面，文獻[1-4]在研究過程中提出假設車輛的速度為定值，路段的通行時間只與道路長度相關。因此，路徑規(guī)劃過程中將通行時間問題轉(zhuǎn)換為道路長度問題。而文獻[5-9]則通過道路長度與平均車速的比值來表征道路的通行時間。這些方法計算簡單，但缺乏對實際交通動態(tài)特性的考慮，無法適應實際路網(wǎng)的運行環(huán)境。通過道路狀態(tài)劃分[10]的方法忽略了較多的交通細節(jié)信息，本質(zhì)上只能夠滿足對道路狀態(tài)的定性分析，無法滿足更多需要定量計算的要求。實例學習模型[11]根據(jù)歷史樣本數(shù)據(jù)估算當前通行時間，但其一般具有較長的時間間隔，適用于交通的長期周期性研究，而非路徑規(guī)劃。

而在出行能耗方面，瞬時計算模型[12]、基于SVM模型[13]、聚合模型[14]、回歸擬合模型[15]等方法通過獲取的瞬時車速信息提取出多種計算指標，進而對車輛在道路上的行駛能耗進行計算。然而，由于全程瞬時信息預測問題的限制，上述方法計無法展開全程最優(yōu)能耗路徑搜索。文獻[16]提出的車速-空間-時間三維搜索體系在尋優(yōu)過程缺乏對時變的路網(wǎng)參數(shù)進行更新，難以在路徑尋優(yōu)中進行準確的能耗優(yōu)化。

綜上所述，當前關于路徑時間或能耗最優(yōu)規(guī)劃依然存在以下缺點：

1) 未考慮路網(wǎng)的動態(tài)時變特性。實際的路徑規(guī)劃過程應該是在三維時空領域展開的。只將累積通行時間作為選擇路徑的參考指標之一，并未考慮搜索過程的時空化的研究更接近于二維的搜索過程，無法反映時空搜索的本質(zhì)。

2) 實現(xiàn)手段過于簡單或理想化。將道路交通狀態(tài)進行劃分或通過車輛瞬時信息計算的方法，前者限制了路徑的優(yōu)化程度，而后者則由于預測技術的限制無法有效開展全程路徑規(guī)劃。

3) 能耗最優(yōu)的路徑規(guī)劃研究尚待進一步深入。尤其對混合動力汽車，現(xiàn)有研究中能耗的計算缺少對控制策略的說明，無法判斷搜索的能耗是否最優(yōu)。

本文基于宏觀交通信息對道路的通行時間以及最優(yōu)能耗的影響因素進行了分析。建立了路徑的通行時間與PHEV最優(yōu)能耗回歸算法模型。以改進的并行A*算法為基礎構建了城市交通時空聯(lián)合的路徑搜索方法。該算法能夠在搜索過程中根據(jù)已搜索路徑的累積耗時與各道路交通特征及時更新后續(xù)道路的交通狀態(tài)，從而實現(xiàn)時空動態(tài)搜索過程。為了方便對交通本質(zhì)進行更加深入的分析，本文研究數(shù)據(jù)是通過城市交通仿真軟件SUMO對來源于開源地圖數(shù)據(jù)庫OpenStreetMap的地圖數(shù)據(jù)進行仿真得到[17-19]。

1 基于回歸擬合的通行時間計算

1.1 搜索過程的時空特征

道路的行程時間與能耗則是與道路結(jié)構（空間）以及其承載的交通（時變）同時有關的動態(tài)變量。僅僅基于距離或者交通費用最優(yōu)的路徑搜索實際上是一個無關時間變化的二維空間搜索過程，如圖1a所示。而當考慮到達時間與能耗時，其搜索過程實際上應是在三維時空領域展開的，如圖1b所示。圖1中坐標軸X和Y代表道路空間坐標，坐標Z代表時間。

圖1 二維空間搜索與三維時空搜索示意

1.2 通行時間的計算

搜索的路徑的累積消耗時間一般計算如下：

其中：τi, t為道路i在時間t時車輛的通行時間；n為道路i在整個路徑中的序號；N為路徑中道路的個數(shù)；li為道路i的長度；為車輛在時間t時通過道路i的平均車速，在實際應用中常使用可預測的宏觀交通數(shù)據(jù)來進行計算。然而，僅僅依據(jù)平均車速的方式無法保證其計算精度。

本文基于交通仿真軟件SUMO對截取的上海某一區(qū)域路網(wǎng)進行了交通仿真計算。以1 min為單位時間整理得到了宏觀交通數(shù)據(jù)。依式 (1) 計算道路的通行時間，其與車輛的實際通行時間平均百分比誤差為36.1%。由此可見，式 (1) 的計算誤差較大。其根本原因是僅僅依靠平均車速進行計算忽略了其它因素對車輛通行時間的影響。因此，本文簡化常見的交通環(huán)境如圖2所示。

圖2 簡化交通環(huán)境示意圖

由圖2可見：車輛在行駛過程中會受到當前道路（空間信息）其它車輛狀態(tài)（交通信息）以及紅綠燈狀態(tài)等因素的直接影響。而當前道路的交通狀態(tài)又會收到其鄰接道路交通狀態(tài)的影響，進而影響目標車輛的行駛狀況。影響因素有：

1) 當前道路i在第t個采樣周期的交通信息，包括平均車速以及單位長度上車輛密度ρi, t：

其中：vk為第k輛車經(jīng)過道路（或指定位置）的車速；α(t)為道路i在第t個采樣周期內(nèi)運行的車輛數(shù)量；li為道路i的長度。

2) 當前道路i的主要屬性，包括通行道路長度li、路口長度γi。

3) 道路預估通行時長τi, t（見式 (1)），以及道路的通行功率：

其中：Fk,i1與vk,i1分別為第k輛車在i1時刻的驅(qū)動力和車速。n(i1)為時間i1時刻在道路i上運行的車輛數(shù)量，Δt為采樣時長。

4) 當前道路i與下一道路j之間的紅綠燈的狀態(tài)，包括：在時間t時剩余一個周期內(nèi)綠燈時長gi, t以及非綠燈的時長ri, t。

5) 下一道路j的交通狀態(tài)，包括：平均車速以及密度其中：

上述影響因素與車輛在該道路上的通行時間之間的關聯(lián)性計算如表1所示。

表1 通行時間與各影響因素之間的關聯(lián)性

從表1來看，單獨每個影響因素與通行時間之間的關聯(lián)性都不是特別強。因此，為了增加計算的準確性，本文考慮同時采用多個影響因素來對道路的通行時間進行擬合。以徑向基函數(shù)神經(jīng)網(wǎng)絡(radical basis function，RBF)和線性神經(jīng)元組合成的廣義回歸神經(jīng)網(wǎng)絡（general regression neural network，GRNN）具有很強的非線性映射能力和學習速度。徑向基核函數(shù)的高維投射能力也使得GRNN更適合于處理多維輸入的回歸問題。因此，本文采用GRNN網(wǎng)絡來處理不同影響因素組合帶來的對通行時間的回歸效果。

表2為8種計算方案 （ID）以及每種方案計算結(jié)果（相對誤差RE以及絕對誤差MAE）。由表2可知：由于涉及到更多瞬時車速信息的計算，平均功率的加入能夠使模型獲得更好的計算精度。

由于在實際的宏觀交通系統(tǒng)中，不可能獲得某一道路未來具體的車速情況，平均功率無法直接計算得到；因此，以方案8所選因素作為GRNN網(wǎng)絡輸入，構建了計算車輛通行時間的計算模型，即：

其中： Δti,j,t為車輛在時刻t通過道路i到達道路j的通行時間；函數(shù)fT為搭建的GRNN網(wǎng)絡。式(5)與式(1)的計算差異見圖3（截取第950～1 000算例的結(jié)果）。由圖3可見：利用本文模型對不同計算樣本所計算的通行時間，均與真實值一致；能將誤差RE從利用式 (1) 所計算的36%，減小至9%。

表2 不同影響因素搭配方案

圖3 路段通行時間計算對比

2 全局最優(yōu)能耗模型

路徑的全局能耗計算模型應符合以下特點：

1) 全局能耗具有最優(yōu)性。從理論上保證計算的全局能耗最優(yōu)（或者接近最優(yōu)）是能耗最優(yōu)路徑搜索的基礎。也是為出行車輛提供最具有節(jié)油潛力的路線的基礎。

2) 輸入?yún)?shù)具有可獲取性。由于是時空領域的全局搜索，必須要考慮模型輸入?yún)?shù)在未來能夠預測或者有效獲取。

基于此，本文提出一種基于宏觀交通信息來計算未來規(guī)劃的路徑的全局能耗的方法。為了能夠減少其它因素（例如駕駛習慣不同、能量管理策略）對節(jié)能效果帶來的影響，依據(jù)動態(tài)規(guī)劃（dynamic programming，DP）方法對車輛的全程最優(yōu)油耗進行了計算。具體車型參數(shù)及計算方法見文獻[20]中的雙離合并聯(lián)汽車。由于車輛的DP油耗為全程指標，路徑上每一個道路的交通狀態(tài)都會對其產(chǎn)生影響；因此，本文選取了能夠反映路徑全局特征信息的8個參數(shù)：

參數(shù)1行程距離。路徑的累積行駛距離為

其中： 為道路編號，I為路網(wǎng)中道路的數(shù)量。

參數(shù)2總能耗。路徑中所有道路的通行能耗的和為

其中：為道路的通行功率。 Δti,j,t為在時間t時通過道路i到達道路j的通行時間。

參數(shù)3平均能耗。路徑通行能耗的平均值為

參數(shù)4總功率。路徑中所有通行功率的和為

參數(shù)5平均功率。路徑通行功率的平均值為

參數(shù)6總耗時。路徑通行時間累積值為

參數(shù)7平均耗時。路徑通行時間的平均值為

參數(shù)8平均車速。車輛經(jīng)過路徑上所有道路時的道路車速的平均值為

上述參數(shù)以及DP油耗之間的關聯(lián)性計算結(jié)果如表4所示。

表4 各參數(shù)以及DP油耗之間的關聯(lián)性

由表4可知：各個參數(shù)與DP油耗之間的關聯(lián)性比較明顯，且不同的參數(shù)之間又存在一定的關聯(lián)性。為了簡化影響因素的表征，本文引入了因子分析法（factor analysis, FA）來對這些變量之間的內(nèi)部關系進行分析。經(jīng)過分析，各個參數(shù)在不同的公共因子上的載荷分布具有明顯的差異性。依據(jù)結(jié)果，得到3個主要公共因子：時間因子、距離因子、速度因子。鑒于多因子回歸的方式，本文同樣以GRNN網(wǎng)絡為基礎，依據(jù)各個參數(shù)在3個公共因子上載荷分布大小， 組成3種方案，進行仿真計算；結(jié)果如表5所示。

表5 3種參數(shù)組合方案計算結(jié)果

由表5可知：隨著輸入?yún)?shù)數(shù)量的增加，準確度緩慢降低。這表明：增加在相同公共因子上同樣具有較高載荷分布的參數(shù)的個數(shù)，并不能夠為回歸模型帶來更高的計算精度，反而對回歸計算帶來了更多的干擾。考慮計算精度以及模型的復雜性，采用方案1的參數(shù)，搭建GRNN網(wǎng)絡，對DP油耗進行回歸擬合處理，計算如下：

其中：Fk為擬合得到的路徑的全局DP油耗；函數(shù)fE為GRNN網(wǎng)絡。

3 基于并行A*的時空全局搜索算法

在得到道路的通行時間以及全程最優(yōu)能耗計算方法后，基于路徑搜索算法即可進行最優(yōu)路徑的搜索。在常用的搜索算法中，A*算法由于啟發(fā)項的加入使其具有結(jié)構簡單、計算速度快等優(yōu)點，且從理論上其能夠得到最優(yōu)搜索結(jié)果；因此，該算法在眾多領域得到了廣泛的應用。針對出行車輛的最優(yōu)路徑規(guī)劃，假設道路個數(shù)為k的路徑的當前道路為i，下一搜索道路為j，則A*算法的懲罰函數(shù)可以定義為：

其中：α1、α2、α3、α4分別為行程時間、行程距離、DP油耗、啟發(fā)項等指標的懲罰系數(shù)；η0= 0，L0= 0，F(xiàn)k= 0；hi為啟發(fā)項，為當前搜索道路i與終點道路之間的距離；函數(shù)g(x)為歸一化函數(shù)；Xmax與Xmin分別為參數(shù)樣本的最大與最小值。

DP油耗計算需要引入全局因素（例如整條路徑的平均車速），這將導致整個搜索過程變得更為復雜。除距離外的其它參數(shù)均無法參與啟發(fā)值hi的計算，這些參數(shù)的計算過程更接近于Dijstrla算法。而Dijstrla搜索算法的遍歷本質(zhì)屬性會影響算法的搜索效率。假如啟發(fā)項的懲罰系數(shù)過小，那么計算耗時將非常長；而假如啟發(fā)項的懲罰系數(shù)過大，那么搜索得到的路徑效果可能會無法得到有效保證。本文提出以距離為基礎指標，同時搜索多條路徑的搜索方法。具體步驟為：

步驟1以累積距離與啟發(fā)距離的加權和計算代價函數(shù)：

其中，β為啟發(fā)距離權重。

步驟2根據(jù)當前道路的到達時間ηk更新其交通狀態(tài)，包括道路車速、密度、紅綠燈信息。

步驟3通過式(5)計算當前道路的通行時間 Δti,j,t并計算新路徑的行程時間ηk+1=ηk+ Δti,j,t。更新道路個數(shù)、平均耗時、行程距離、平均車速，同時依據(jù)式（14）計算新路徑的DP油耗Fk+1。

步驟4若當前道路為終點道路，則執(zhí)行步驟 (5)，否則，依據(jù)A*算法，重復步驟1—步驟3。

步驟5按照距離最短依次計算n（例如1 000）條不同路徑。

步驟6在所得的路徑集合中，分別選擇DP油耗、行程時間或者行程距離最小路徑，為滿足不同指標最優(yōu)的路徑。

傳統(tǒng)的A*算法中每次都是選擇當前最優(yōu)點進行新一輪的搜索。然而，由于需要搜索多條路徑，為了加快整個搜索過程，本文選取當前的最優(yōu)點以及其后一定數(shù)量的次最優(yōu)點同時進行新一輪的搜索。其中，次最優(yōu)點選擇為除去最優(yōu)點后依據(jù)懲罰函數(shù)從小到大而得到的一定數(shù)目的點。改進的并行A*搜索算法的搜索過程示意圖，如圖4所示。

圖4 改進的多點并行A*搜索算法示意圖

每次都選擇當前最優(yōu)點與多個次最優(yōu)點進行新的搜索，這種并行的計算方式使得部分次最優(yōu)點成為新的最優(yōu)點的所需迭代次數(shù)減少了。并行搜索點數(shù)量的增加可能會導致下一搜索點數(shù)量的成倍增長。考慮到實際計算開銷問題，基于改進的多點并行A*搜索算法的過程需要優(yōu)化2個參數(shù)：啟發(fā)項懲罰系數(shù)以及A*算法單次搜索數(shù)量。本文選取了不同的參數(shù)組合進行了仿真計算。計算結(jié)果顯示：

1) 搜索算法的計算耗時與啟發(fā)項懲罰系數(shù)以及單次搜索數(shù)量具有較強的關系。由于影響著啟發(fā)值在懲罰函數(shù)中的占比，整體上計算耗時隨著懲罰系數(shù)的增加而快速降低；而雖然并行多次計算能夠縮短非最優(yōu)點達到最優(yōu)點的迭代次數(shù)；但是過高的單次搜索數(shù)量也會增加算法耗時；因此搜索耗時隨著單次搜索數(shù)量的增加呈現(xiàn)先降低后增加的情況。

2) 啟發(fā)項懲罰函數(shù)越大，說明啟發(fā)值在懲罰函數(shù)占比越大；懲罰函數(shù)的最優(yōu)值會受到啟發(fā)值的更多的影響，進而降低其它指標的最優(yōu)表征能力； 最優(yōu)DP油耗、行程時間、行程距離等指標，整體上呈現(xiàn)隨著啟發(fā)項懲罰系數(shù)的增加而增加。同時，單次搜索數(shù)量越大意味著越多的次最優(yōu)點與最優(yōu)點具有同等地位，算法在本質(zhì)上越接近于Dijstrla算法。在這種情況下，啟發(fā)值對懲罰函數(shù)的影響越小。故而最優(yōu)路徑的DP油耗、行程時間、行程距離等指標，隨著單次搜索數(shù)量的增加而降低。

綜合考慮指標優(yōu)化以及計算耗時，本文選擇啟發(fā)項懲罰系數(shù)β= 1.4，單次搜索數(shù)量為200的參數(shù)組合。

4 仿真試驗分析

本文中SUMO仿真采用的城市交通地圖結(jié)構如圖5所示。SUMO軟件仿真過程主要包括設置.route文件（車輛出行路徑文件）以及.sumocfg文件（仿真系統(tǒng)文件）。前者文件主要用來在仿真之前規(guī)定每輛車的起終點道路以及具體行駛路徑，后者文件則是對仿真過程以及仿真結(jié)果記錄等方面進行設置。

圖5 仿真地圖道路結(jié)構

本文的仿真試驗采用多輛車同時出行的方式來構成該路網(wǎng)上的宏觀交通數(shù)據(jù)。在.route文件設置方面，依據(jù)SUMO系統(tǒng)默認的最短路徑進行規(guī)劃，出行車輛的起點道路與終點道路依據(jù)地圖隨機選擇。依據(jù)SUMO系統(tǒng)的仿真原則設定了車輛出行間隔時間。該時間是指SUMO系統(tǒng)在路網(wǎng)中產(chǎn)生一個隨機起終點出行車輛的間隔時間，即系統(tǒng)仿真期間新車輛介入路網(wǎng)的間隔時間設置為1 s。車輛動力性參數(shù)，例如最大加、減速度等，均采用SUMO默認值。.sumocfg文件的設置參數(shù)為：

1) 仿真開始時間：0 s；

2) 仿真結(jié)束時間：104s；

3) 仿真時間步長：1 s；

4) 仿真記錄參數(shù)包括：系統(tǒng)時間、車速、所處道路、所處位置以及該道路對應的紅綠燈狀態(tài)等信息。

仿真結(jié)束后，提取仿真記錄參數(shù)，得到每輛車的行駛數(shù)據(jù)，進而得到每條道路在指定宏觀采樣時間內(nèi)的交通狀態(tài)。具體計算方法如第2、3小節(jié)所述。其中，提取部分道路的交通流量與平均車速信息如圖6-7所示，圖中不同顏色的柱體代表不同道路。

圖6 道路平均交通流量

圖7 道路平均車速

為了對本文提出的基于動態(tài)時空特征的全局車輛路徑規(guī)劃算法進行驗證，本文進行了以下對比計算。基于城市路網(wǎng)交通具有動態(tài)變化的特性，為出行車輛提供時空領域的全局路徑規(guī)劃必然離不開對交通參數(shù)的預測。本文主要是針對路徑通行時間以及全程最優(yōu)能耗的研究，重點不在預測算法上面；為了保證測試的合理性，首先假設未來交通參數(shù)均是已知，然后在此基礎上為其添加不同信噪比數(shù)據(jù)來模擬實際應用中對交通參數(shù)的預測值。通過文獻調(diào)研發(fā)現(xiàn)，當前的交通信息預測算法的精度會隨著預測時長的增長而下降。預測時長在5～50 min的預測誤差為10%～20%[21]。為了保證測試過程的合理性，本文分別添加平均百分比誤差為0%、10%、15%、20%的噪聲來生成測試交通信息數(shù)據(jù)。本文添加的噪聲為Gauss白噪聲，符合正態(tài)分布。具體添加方式為：

1) 將交通信息數(shù)據(jù)通過標準化轉(zhuǎn)換為均值為0，方差為1的正態(tài)分布數(shù)據(jù)。

2) 信噪比公式，計算噪聲在指定相對誤差ε下的信噪比為：

得到信噪比后，產(chǎn)生指定噪聲。本算法中搜索路徑集合大小為300，計算機配備有主頻為3.0 GHz的i-7處理器，內(nèi)存16 GB。

對比算法方面，本文基于A*算法分別構建了在時空領域和空間領域搜索的2種對比算法。稱前者為對比算法1，后者為對比算法2。對比算法1與對比算法2均為基于A*的搜索算法。2種算法的步驟為：

步驟1初始化當前道路信息，對于對比算法2而言，路徑搜索過程中的交通信息保持不變，均采用當前時刻所有道路各自的值。對于對比算法1而言，需要基于當前時刻以及歷史時刻的交通數(shù)據(jù)對，來路網(wǎng)未來交通信息進行預測，將預測信息視為其后續(xù)路徑搜索交通信息。

步驟2類似于式（15），2種算法采用的懲罰函數(shù)為

其中：τi, t與fi, t分別為道路i的通行時間與能耗；α1、α2、α3、α4的取值決定搜索算法對不同指標優(yōu)化的重視程度，當取值（1, 0, 0, 0）以及（0, 0, 1, 0）時，分別代表按照累積通行時間最優(yōu)以及累積能耗最優(yōu)進行路徑規(guī)劃。

步驟3更新開放集合與歷史集合，選擇當前開放集合中的最優(yōu)道路（懲罰函數(shù)最小）的鄰接道路作為新的當前道路進行計算。

步驟4對比算法1根據(jù)當前道路的到達時間更新其交通狀態(tài)。2種對比算法均采用式(1)與式(7)分別計算當前道路的通行時間與能耗。

步驟5若當前道路為終點道路，則結(jié)束搜索過程，得到最優(yōu)路徑。否則依據(jù)A*算法重復步驟2—步驟5。

具體試驗過程為：

1) 選擇測試車輛，以其出發(fā)時間為起點時間，以其出發(fā)道路為起點道路。

2) 基于宏觀交通未來預測，分別根據(jù)上述3種方法規(guī)劃測試車輛起點到終點的路徑。

3) 根據(jù)規(guī)劃的路徑，更新原.route文件中測試車輛的路徑，再次通過SUMO進行車輛行駛仿真。

4) 整理得到對應規(guī)劃路徑下的車輛行駛數(shù)據(jù)。

理論最低能耗的路徑是車輛實際能耗降低的基礎。本文根據(jù)行駛結(jié)果采用DP算法計算得到車輛的行駛油耗來進行3種算法的車輛能耗比較。3種算法基于能耗最優(yōu)路徑得到的DP油耗與基于時間最優(yōu)路徑得到的行程時間（t）的計算結(jié)果，如圖8所示。

為比較算法的計算效率，圖9和圖10所示為幾種算法的搜索耗時對比；其中對比算法2與本文提出的全局搜索算法對應的曲線，參考左側(cè)坐標軸，對比算法1曲線，參考右側(cè)坐標軸。

表6所示為本文提出的算法規(guī)劃的最優(yōu)能耗路徑與最短時間路徑相對其它兩種算法的優(yōu)化效果。表7所示為相比其它2種算法的搜索效率的提升效果。

表 6 本文算法規(guī)劃的最優(yōu)能耗路徑帶來的能耗下降效果

表7 搜索算法效率的提升效果

圖8 3種算法計算結(jié)果對比圖

圖9 測試算法的最優(yōu)能耗路徑搜索耗時

圖10 測試算法的最短時間路徑搜索耗時

可見，相較于對比算法，本文提出的基于動態(tài)時空特征的全局路徑規(guī)劃算法能夠獲得更優(yōu)的能耗優(yōu)化或者時間優(yōu)化路徑，可降低車輛能耗11%以上或縮短行車時間13%以上。這是由于本文方法綜合考慮了道路通行時間以及全程最優(yōu)能耗的影響因素，提高了道路通行時間與能耗模型的計算精度，同時采用了針對時變環(huán)境的時空聯(lián)合搜索方法。

在搜索耗時方面，對比算法1完全在時空領域進行搜索，維數(shù)增多帶來了巨大的搜索耗時；對比算法2則僅僅是在二維空間領域進行搜索，具有最快的搜索速度；本文采用的搜索算法由于是并行計算，且每次搜索僅僅考慮距離指標，能夠加快搜索速度，在能夠獲得更優(yōu)路徑的同時，與對比算法2耗時差并不是很大；因此，本文提出的基于動態(tài)時空特征的全局路徑規(guī)劃算法能夠更加有效地優(yōu)化出行車輛的路徑選擇。

5 結(jié) 論

為科學合理的路徑規(guī)劃，本文基于當前的宏觀交通信息對道路的通行時間以及能耗的影響因素進行了分析。依據(jù)回歸方法構建了計算道路通行時間以及針對混合動力汽車的路徑全程能耗的計算方法。以改進的并行A*算法為基礎，構建了城市交通時空聯(lián)合領域的路徑搜索方法。對提出的算法進行了對比驗證。

結(jié)果顯示：本文提出的方法能夠在可接受時間內(nèi)為出行車輛提供更加合理的路徑規(guī)劃，相比依據(jù)平均車速與道路功率的計算方法，可降低車輛能耗11%以上或縮短行車時間13%以上。