基于變結(jié)構(gòu)離散動態(tài)BN的最優(yōu)交通路徑規(guī)劃

(西安工程大學 電子信息學院,西安 710048)

0 引言

隨著近年來我國的國民經(jīng)濟飛速發(fā)展，城市機動車的數(shù)量不斷增加，交通需求量也急劇增加，交通擁堵成為我國乃至全世界共同面臨的問題。但是，僅僅靠改善交通設施，成本大且效果不好。面對這一系列問題，路徑規(guī)劃算法的研究已經(jīng)變得非常重要。

車輛路徑規(guī)劃算法有兩種類型分別為靜態(tài)路徑規(guī)劃算法和動態(tài)路徑算法[1]。靜態(tài)路徑規(guī)劃就是依據(jù)某些優(yōu)化準則(如路徑距離最短，所用時間最短等)結(jié)合實際地理信息，找到一條從起始狀態(tài)到目標狀態(tài)的最優(yōu)路徑。近年來，有許多學者對靜態(tài)路徑規(guī)劃算法進行了改進，但是靜態(tài)的路徑規(guī)劃算法相對比較簡單，應用于實際的交通狀況意義不大。動態(tài)路徑規(guī)劃[2]是在靜態(tài)路徑規(guī)劃中加入實時的交通信息，得到符合要求的路徑。一些研究者基于傳統(tǒng)的路徑規(guī)劃算法對動態(tài)路徑規(guī)劃算法[3-6]進行了優(yōu)化改進，但大都解決的都是最短路徑問題。為了使駕駛者有更好的駕駛體驗，未來對路徑規(guī)劃或路徑尋優(yōu)方法的研究應更加關(guān)注駕駛者的駕駛偏好。文獻[7]提出了一種具有在線組件和離線組件的系統(tǒng)，以利用軌跡解決最小的路上時間問題。在線查詢應答組件利用路線上的停車設施來避免預測的交通擁堵并最終減少駕駛員的路上時間，而離線組件解決如何根據(jù)歷史軌跡生成道路網(wǎng)絡的速度曲線。文獻[8]提出了一種基于遺傳算法的協(xié)同優(yōu)化方法,以及一種自適應實時優(yōu)化策略,能夠為駕駛員提供燃料經(jīng)濟路線，同時使用交通數(shù)據(jù)和車輛特性來優(yōu)化車輛路線，以改善給定的預期行程時間的燃料經(jīng)濟性。這些文獻都只考慮了單一因素，沒有對影響交通路徑規(guī)劃的其他方面進行更多研究。

BN是一種類似人類思維過程的建模工具，可以對復雜系統(tǒng)的不確定性進行推理和分析。現(xiàn)實生活中，實際的路網(wǎng)是復雜多變的，對交通進行路徑規(guī)劃的問題就是解決不確定性問題。動態(tài)BN作為一個與時間序列結(jié)合的復雜因果關(guān)系網(wǎng)，在處理交通路徑規(guī)劃中的時序數(shù)據(jù)以及表達駕駛員偏好方面具有獨特的優(yōu)勢。因此，本文采用動態(tài)BN理論[9-10]，通過駕駛員偏好分析、模型結(jié)構(gòu)建立、模型參數(shù)確定等一系列工作，建立基于變結(jié)構(gòu)離散動態(tài)BN[11]的最優(yōu)交通路徑規(guī)劃模型，能夠考慮駕駛員的駕駛偏好[12]。研究結(jié)果可在動態(tài)路徑規(guī)劃的應用方面提供參考，規(guī)劃出滿足駕駛員偏好的最優(yōu)路徑。

1 變結(jié)構(gòu)動態(tài)BN

BN是基于概率推理的數(shù)學模型，可以通過有向無環(huán)圖(DAG)和條件概率表(CPTs)直觀的表達變量間的依賴關(guān)系。BN能夠通過一些變量的信息，推理得出其他變量的概率信息，可以解決不定性問題，被廣泛應用在多個領(lǐng)域。

動態(tài)BN是靜態(tài)BN結(jié)合時序發(fā)展而來的。通常由初始網(wǎng)絡和轉(zhuǎn)移網(wǎng)絡兩部分組成。一個完整的動態(tài)BN包含有限個時間片，每個時間片由一個有向無環(huán)圖和條件概率表組成。從一個時間片到另一個時間片的跨越反映了時變作用。

傳統(tǒng)的動態(tài)BN實際上是一個特殊的變結(jié)構(gòu)動態(tài)BN，變結(jié)構(gòu)動態(tài)BN可以是每個時間片上的網(wǎng)絡結(jié)構(gòu)不同，也可以是參數(shù)不相同。完全確定一個變結(jié)構(gòu)動態(tài)BN需要知道：先驗概率P(X)、狀態(tài)轉(zhuǎn)移條件概率P(Xt|Xt-1)、觀測值P(Y)。

在動態(tài)BN中，根據(jù)變量是否離散或連續(xù)，可以分為連續(xù)動態(tài)BN和離散動態(tài)BN。本文主要采用隱變量和觀測變量均離散的變結(jié)構(gòu)離散動態(tài)BN模型。

2 最優(yōu)路徑規(guī)劃方法基本思想

本文為解決交通擁堵，提高道路使用率，同時兼顧駕駛者的駕駛體驗，提出基于變結(jié)構(gòu)離散動態(tài)BN的交通最優(yōu)路徑規(guī)劃方法。具體地，首先分析影響交通路徑規(guī)劃的主要因素，鑒于駕駛員的個人偏好，本文選擇行駛時間、路況、行駛距離、出行費用4個因素作為最優(yōu)出行路徑評價指標；然后建立變結(jié)構(gòu)離散動態(tài)BN模型；接著對模型進行參數(shù)學習；最后采集數(shù)據(jù)獲得證據(jù)信息，采用基于時間窗的動態(tài)BN近似推理算法中固定窗口寬度方法[13]進行在線推理，根據(jù)實時采集到的交通信息得出最優(yōu)的交通路徑。圖1給出了本文提出方法的最優(yōu)路徑規(guī)劃方法的流程圖。

圖1 最優(yōu)路徑規(guī)劃方法的簡單流程

3 變結(jié)構(gòu)動態(tài)BN最優(yōu)交通路徑規(guī)劃模型建立與分析

3.1 影響最優(yōu)路徑選擇的因素

在交通系統(tǒng)中駕駛員是重要參與者，駕駛員在行駛中要對路徑進行選擇，對于具體的道路狀況，不同的駕駛員有不同的偏好。實際的駕駛中會有許多外界因素的干擾，使得駕駛員對于最優(yōu)路徑有多樣的選擇。綜合考慮影響駕駛員路徑選擇因素，主要有行駛距離、行駛費用、行駛時間、道路擁擠程度(路上車輛數(shù)、排隊長度)、路況(車輛行駛速度)和身體狀況等，各個因素有各自的特征與屬性。駕駛員對路徑進行選擇時會依據(jù)自身偏好，對于不同路徑選擇影響因素有不同的心理接受范圍和標準。鑒于駕駛員的個人偏好，本文選擇行駛時間、行駛距離、路況、出行費用4個因素作為最優(yōu)出行路徑評價指標。

3.2 變結(jié)構(gòu)離散動態(tài)BN模型建立

將最優(yōu)交通路徑評估指標中的各個影響路徑規(guī)劃的因素設定為單片離散動態(tài)BN中的觀測節(jié)點，同時賦予節(jié)點離散值域，建立單片離散動態(tài)BN的有向無環(huán)圖，如圖2所示。

圖2 單片離散動態(tài)BN

3.3 模型參數(shù)確定

3.3.1 參數(shù)學習

單時間片內(nèi)離散節(jié)點的初始狀態(tài)分布參數(shù)可通過統(tǒng)計方法得到，主要的是狀態(tài)轉(zhuǎn)移概率和單時間片內(nèi)的條件分布參數(shù)的確定。本文采用最大似然估計產(chǎn)生狀態(tài)轉(zhuǎn)移概率，自適應產(chǎn)生算法[14]得出條件概率。

變結(jié)構(gòu)離散動態(tài)BN可以是每一個時間片的觀測變量和隱變量個數(shù)不同，也可以是不同時間片的變量之間的條件概率不同，而參數(shù)的自適應產(chǎn)生算法就是模型變化時，能按照某種原則自動產(chǎn)生條件概率表的一種算法。

按照BN的理論，條件概率表表示的是子節(jié)點在已知父節(jié)點的狀態(tài)時的概率分布。假定存在一個節(jié)點D，有n個狀態(tài)(d1,d2,…,dn)，其子節(jié)點設為C，且有m個狀態(tài)，則條件概率表計算P(cj|di)，i=1,2,…,n，j=1,2,…,m。

隱節(jié)點的各個狀態(tài)，總是在其子節(jié)點集合中，需要找出其相關(guān)節(jié)點和不相關(guān)節(jié)點。已知隱節(jié)點的某一狀態(tài)，可以找出其相關(guān)節(jié)點的最偏好狀態(tài)和最不偏好狀態(tài)，將相關(guān)節(jié)點的狀態(tài)按從大到小順序排列，條件概率表可采用負1次、負2次或者負高次冪的形式構(gòu)成。即：

圖3 離散動態(tài)BN結(jié)構(gòu)模型

或：

(1)

按照該觀測節(jié)點的重要性從小到大排列，條件概率表可以用正高次冪的形式構(gòu)成。例如：

(2)

而對于隱節(jié)點狀態(tài)的不相關(guān)節(jié)點，也存在一定的偏好。一般采用一次冪的形式形成條件概率表，即:

(3)

(4)

3.3.2 變結(jié)構(gòu)動態(tài)BN推理

在一個動態(tài)BN的結(jié)構(gòu)和參數(shù)都已知的情況下，獲得證據(jù)信息后，就可以對網(wǎng)絡進行在線推理。本文采取的是基于時間窗的動態(tài)BN近似推理算法中固定窗口寬度方法[來進行在線推理，根據(jù)實時采集到的交通信息得出最佳的交通路徑。

推理需要兩個過程，分別為濾波操作Filtering(tn+1)和平滑操作Smoothing(tm)。其中，tn+1和tm分別為第n+1個時間片和第m個時間片。濾波是在所有給定的證據(jù)條件下，計算當前狀態(tài)的后驗概率分布P(Xt|y1:t)。平滑是在所有給定的證據(jù)條件下，計算過去某一狀態(tài)的后驗概率，即對某個滿足1≤k

假設存在一個已知的時間邊界tT,設到目前為止觀測序列的長度為n。算法從n=1開始，并不斷地從動態(tài)環(huán)境中得到觀測值。假設第tn個時間片進入了時間窗，則執(zhí)行以下操作：1)若n

圖4 新證據(jù)被添加時的時間窗操作方法

4 仿真實驗

本文的仿真用C++語言編程實現(xiàn)，在CPU頻率為1.90 GHz，內(nèi)存為4.00 GB的計算機上運行得到結(jié)果。

4.1 實例分析

收集西安某地區(qū)的交通信息，將實際交通路網(wǎng)轉(zhuǎn)化成有向圖來模擬交通路徑圖，如圖5所示，駕駛員偏好選擇路徑距離較短且路況較好。

圖5 西安某地交通路徑示意圖

根據(jù)圖5所示的交通路徑信息，駕駛者從起始點S到目標節(jié)點D，把駕駛的道路按時序分為6個時間片，節(jié)點1到節(jié)點2為一個時間片，2到3分為一個時間片，依次劃分。前三個時間片中，每個時間片隱節(jié)點都有三個狀態(tài)，即有上路徑、中路徑和下路徑可選擇，后三個時間片每個時間片有上路徑和下路徑可選擇。

依據(jù)駕駛員偏好，選擇路徑距離和路況兩個因素作為評價指標，構(gòu)建的基于變結(jié)構(gòu)離散動態(tài)BN的最優(yōu)路徑?jīng)Q策模型，如圖6所示。隱變量X狀態(tài)為該時刻可選路徑的條數(shù)，前三個時間片的有三條路徑可以選擇，后三個時間片有兩條路徑可以選擇。

在構(gòu)建的模型中，先驗概率是對初始時刻隱節(jié)點狀態(tài)的分布估計。本文采用最大似然估計進行參數(shù)學習，得到路徑選擇類型的先驗概率為P(x1,x2,x3)=(0.3,0.4,0.3),x1,x2,x3分別代表隱藏節(jié)點的三個狀態(tài)，即上、中、下路徑。采用變結(jié)構(gòu)動態(tài)BN的參數(shù)的自適應產(chǎn)生算法，自動生成各個時間片的條件概率，如表1，表2所示。

狀態(tài)轉(zhuǎn)移概率時間片之間的條件概率，可以根據(jù)統(tǒng)計學規(guī)律得出，如表3所示。P(Xt+1|Xt)表示第t個時間片到第t+1個時間片的狀態(tài)轉(zhuǎn)移概率，t={1,2,…,6}。

在同一天時間內(nèi)，每條路徑的交通流量都是在不斷變化的，并且區(qū)別很大。而在短時間內(nèi)，每條路徑上的變化一般不會太大，故本文僅選擇某一個時間段進行研究。取K1和K2時刻，觀測6個時間片的路徑距離(km)和路段平均速度(km/h)，如表4所示。

離散化處理表4中的觀測數(shù)據(jù)，采用基于時間窗的近似推理算法進行推理，得到K1、K2時刻最優(yōu)交通路徑?jīng)Q策結(jié)果如分別為表5、表6所示。

圖6 變結(jié)構(gòu)離散動態(tài)BN的最優(yōu)路徑?jīng)Q策模型

tP(Y11|X)P(Y41|X)P(Y12|X)P(Y42|X)P(Y13|X)P(Y43|X)N M FC H YN M FC H YN M FC H Y10.55,0.27,0.180.75,0.22,0.030.17,0.33,0.500.18,0.27,0.550.17,0.33,0.500.18,0.27,0.5520.17,0.33,0.500.18,0.27,0.550.74,0.18,0.080.75,0.22,0.030.17,0.33,0.500.18,0.27,0.5530.17,0.33,0.500.18,0.27,0.550.17,0.33,0.500.18,0.27,0.550.85,0.12,0.030.75,0.22,0.03

表2 后三個時間片條件概率表

表3 狀態(tài)轉(zhuǎn)移概率表

表4 觀測數(shù)據(jù)表

表5 K1時刻最佳交通路徑?jīng)Q策結(jié)果

表6 K2時刻最佳交通路徑?jīng)Q策結(jié)果

在表5中，前三個時間片每一列數(shù)據(jù)依次為選擇上、中、下路徑的概率值，取這3個概率值中的最大值所對應的路徑作為該時間片上決策出的路徑。后三個時間片每一列數(shù)據(jù)依次為選擇上、下路徑的概率值，取這2個概率值中的最大值所對應的路徑作為該時間片上決策出的路徑。通過分析仿真結(jié)果，可以看出路徑選擇是(中、上、下、下、下、下)，記為S1。根據(jù)表6，可以得知在不同時刻對同一路段要求距離最短且路況好的路徑選擇是(上、下、下、下、下、下) ，記為S2。表5和表6決策的路徑不一致，由此說明路徑的選擇與距離和路況有關(guān)，路況信息在不斷變化，決策出的路徑也在變化。

4.2 本文提出方法與Dijkstra算法仿真結(jié)果比較

根據(jù)表4的觀測數(shù)據(jù)，采用Dijkstra算法決策出的路徑為(中、中、上、上、下、上)，記為S3。

將本文提出方法在K1時刻和K2時刻與Dijkstra算法分別進行比較，如表7所示。

表7 仿真結(jié)果比較

從表7可以得出，如果在K2時刻采用K1時刻的路徑S1，行駛時間比K2時刻的路徑S2所用時間更長。表明本文所提方法可以根據(jù)實時路況信息決策出更短的路徑。

由表7可知，Dijkstra算法在K1和K2時刻決策出的路徑相同，盡管決策的路徑距離最短，但不能考慮路況的變化。而本文提出的基于變結(jié)構(gòu)離散動態(tài)BN交通最優(yōu)路徑規(guī)劃方法結(jié)合了實時的路況信息，所以決策出的路徑不同，不一定最短。在K1和K2時刻，本文方法規(guī)劃的路徑的行駛時間都比Dijkstra算法更短。因此，本文所提的最優(yōu)路徑規(guī)劃算法能夠快速有效的根據(jù)實時信息對路徑進行在線最優(yōu)規(guī)劃。

5 結(jié)束語

本文提出了基于變結(jié)構(gòu)離散動態(tài)BN的交通最優(yōu)路徑規(guī)劃方法，建立適合于實際路網(wǎng)的變結(jié)構(gòu)離散動態(tài)BN模型，結(jié)合實例，成功地將動態(tài)BN應用到交通路徑規(guī)劃中。計算結(jié)果不但驗證了變結(jié)構(gòu)離散動態(tài)BN具有良好的交通路徑規(guī)劃能力，也驗證了變結(jié)構(gòu)離散動態(tài)BN基于實時信息的強大更新能力。在現(xiàn)實生活中，實際的路網(wǎng)是非常復雜的，本文提出的算法更適合稀疏的網(wǎng)絡，進一步的研究工作將面向稠密復雜路網(wǎng)探討最優(yōu)路徑規(guī)劃。