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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 模型參數(shù)確定

3.3.1 參數(shù)學(xué)習(xí)

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

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

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

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

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

或：

(1)

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

(2)

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

(3)

(4)

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

4.1 實(shí)例分析

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

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

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

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

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

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

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

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

圖6 變結(jié)構(gòu)離散動(dòng)態(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 后三個(gè)時(shí)間片條件概率表

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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