基于貝葉斯理論道路擁堵預(yù)測的最短路問題研究

文/苗軍 南京財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院 江蘇南京 210023

1、引言

近年來交通網(wǎng)絡(luò)優(yōu)化已經(jīng)成為交通問題研究的熱點(diǎn)。而城市交通網(wǎng)絡(luò)的最短路問題的分析可以有效地緩解資源的配置問題，也越來越成為熱點(diǎn)問題，對現(xiàn)實(shí)生活中的城市道路進(jìn)行最短路分析，首先要將現(xiàn)實(shí)的城市道路網(wǎng)絡(luò)抽象化為圖論中的網(wǎng)絡(luò)圖，在確定網(wǎng)絡(luò)圖相應(yīng)的權(quán)重后按照適當(dāng)?shù)乃惴败浖M(jìn)行最短路分析，從而得到最短路問題的解。

在交通網(wǎng)絡(luò)中，最短路分析一般是指網(wǎng)絡(luò)圖中各路段的權(quán)值之和最小，這個(gè)權(quán)值可以是出行的時(shí)間，也可以是出行的費(fèi)用。而對于權(quán)值不同的理解，又可將此類問題分為兩大類：一是將權(quán)值看作是非隨機(jī)變量，當(dāng)這個(gè)非隨機(jī)變量不隨著時(shí)間的變化時(shí)就是確定性靜態(tài)最短路，反之，如果隨著時(shí)間的變化而變化，那就是確定性的動(dòng)態(tài)最短路問題。第二大類則是將權(quán)值看成是隨機(jī)變量，每個(gè)不同值的出現(xiàn)是有一定的概率的，此時(shí)在求最短路的時(shí)候就要轉(zhuǎn)換成求期望值最小。

在道路擁堵預(yù)測最短路問題的研究中，關(guān)于將權(quán)值看作是隨機(jī)變量所涉及的相關(guān)理論，前人已經(jīng)做了很多工作：Miller-Hooks E（2003）[1]把交通網(wǎng)絡(luò)圖中各個(gè)路段上的路權(quán)看作是一個(gè)與時(shí)間相關(guān)的隨機(jī)變量，將各個(gè)期望值的賦為路段的權(quán)值，進(jìn)而求得起始點(diǎn)到終點(diǎn)的最短路。袁二明等（2013）[2]通過對交通擁堵的預(yù)測來修正交通網(wǎng)絡(luò)中發(fā)生擁堵的概率分布，從而得到在交通網(wǎng)絡(luò)期望費(fèi)用值最少的最短路線，算例仿真結(jié)果表明交通擁堵預(yù)測能起到積極作用。此外，談蔚欣（2006）[3]介紹了樣本數(shù)據(jù)處理的具體過程，確定了合適的擁堵預(yù)測指標(biāo)體系，選擇了LMBP神經(jīng)網(wǎng)絡(luò)作為組合分類器的元學(xué)習(xí)算法，選用了投票法和平均法作為分類器輸出的組合規(guī)則。并針對整個(gè)擁堵預(yù)測過程做了系統(tǒng)的闡述。

而在求解道路交通的最短路的相關(guān)算法與理論上：黃國浪（2014）[4]提出了一種新的城市交通擁堵識別算法，并對城市交通擁堵預(yù)測中的關(guān)鍵技術(shù)交通流參數(shù)短時(shí)預(yù)測進(jìn)行了深入研究，建立了一種多模型融合預(yù)測方法。陳允峰（2015）[5]提出了兩種利用Lingo軟件求解的最短路方法，并給出具體的實(shí)例驗(yàn)證了其中的正確性。鄒桂芳和張培愛（2011）[6]在Gauss-Seidel迭代法思想的基礎(chǔ)上，提出了一種改進(jìn)的Floyd算法來計(jì)算任意兩點(diǎn)之間的最短路問題。丁浩和萇道方（2014）[7]利用Dijkstra算法來迅速尋找出快遞車輛配送派件過程中的最短路，并與解決該類問題常用的遺傳算法，蟻群算法進(jìn)行了比較分析。

2、模型與建立與求解

本文所研究的問題是城市道路交通擁堵問題，由于道路是否擁堵是一個(gè)不確定性的因素，具有一定的概率值，而且擁堵以及不擁堵所消耗的費(fèi)用（考慮到信息成本的單位，這里統(tǒng)一使用費(fèi)用而不是時(shí)間）也是有所不同的，所以本文所建立的網(wǎng)絡(luò)圖問題是屬于第二大類別---將權(quán)值看作是隨機(jī)變量，在此，關(guān)于如何確定擁堵的概率值以及所花費(fèi)的時(shí)間來計(jì)算期望值（權(quán)值）就顯得至關(guān)重要了，本文假設(shè)駕駛員根據(jù)自己的以往經(jīng)驗(yàn)，大概預(yù)估出所選擇的道路的擁堵的概率值。即擁堵與不擁堵的可能性。當(dāng)然，駕駛員也可以在了解交通預(yù)測的結(jié)果和以往的信息的基礎(chǔ)上，對原有的道路擁堵的可能性做出修正，修正所涉及的原理就是貝葉斯定理。下面則是建模的具體步驟：

第一步：駕駛員根據(jù)經(jīng)驗(yàn)對網(wǎng)絡(luò)圖的各個(gè)路段的擁堵情況做出的預(yù)估，A1表示路段發(fā)生擁堵，A2則表示不發(fā)生擁堵，其對應(yīng)的概率值就用P（A1）與P（A2）來表示，這個(gè)概率值成為先驗(yàn)概率，根據(jù)先驗(yàn)概率以及費(fèi)用可以得出每個(gè)路段相應(yīng)的期望值，進(jìn)而得到最優(yōu)選擇的狀況下的期望值。

對于任意一路段，設(shè)其在擁堵時(shí)的費(fèi)用記為F1，在不擁堵的狀況下的費(fèi)用是F2，則其在路段中的期望值是：

由上述的公式的到了各個(gè)路段的出行費(fèi)用的期望值，將該期望值設(shè)為權(quán)值，利用Lingo軟件可以求解相應(yīng)的最優(yōu)解，即最小的總期望值ETOTLE，同時(shí)也能得到相應(yīng)的最優(yōu)交通路線。

第二步：由于上一步獲得的信息不完全準(zhǔn)確，我們要對先驗(yàn)概率進(jìn)行修正，這就用到了貝葉斯公式來對上述的概率進(jìn)行進(jìn)一步的修正：

此時(shí)利用上式得到的期望值就是：

這樣就得到了修正后的出行費(fèi)用的期望值，同樣以E＊代替E得到新的權(quán)值，利用Lingo得出最優(yōu)的路徑和最小的總期望值E＊TOTLE 。

第三步：在上面兩個(gè)步驟的基礎(chǔ)上，本文可以用情報(bào)價(jià)值來判斷是否應(yīng)該做出預(yù)測，即：

其中C表示獲得以往的預(yù)測信息所耗費(fèi)的成本，當(dāng)EVPI＞0的時(shí)候，說明預(yù)測所帶來的收益是大于不預(yù)測帶來的收益的，我們認(rèn)為預(yù)測是有用的，反之，如果EVIS≤0的時(shí)候，就沒有必要進(jìn)行預(yù)測了，因?yàn)檫@時(shí)候的預(yù)測成本超過了預(yù)測所帶來的收益。

3、算例仿真

圖1 某區(qū)域道路的網(wǎng)絡(luò)圖

簡單地將某個(gè)地區(qū)的道路交通路線抽象為上述的交通網(wǎng)絡(luò)圖。每個(gè)路段的擁堵情況以及相應(yīng)的費(fèi)用如表1所示：

上表中的每個(gè)路段的權(quán)值E可由公式（1-1）計(jì)算出來，這樣就得到了初步的權(quán)值矩陣。

利用Lingo軟件得到圖2所示的結(jié)果：

圖2 最短路線問題的運(yùn)行結(jié)果

上述的結(jié)果表明最小的期望值是18，由X（1，3） X（3，6）取值為1，其他的取值為0可以推出該路線：為1→3→6。

此時(shí)，通過表1觀察到1-3和2-3的路段的擁堵概率是最大的（為0。6），即最有可能發(fā)生擁堵，不妨以1-3路段為例，下一步要進(jìn)行的是利用貝葉斯公式來計(jì)算一下修正概率。

表2 對于1-3路段預(yù)測擁堵情況的準(zhǔn)確度

由貝葉斯全概率公式，可以得出1-2路段中的預(yù)測擁堵以及不擁堵的概率：

可以求得，1-3路段中預(yù)測擁堵且實(shí)際就是擁堵的概率為：

同理可知其他的情況，如下表所示：

表3 擁堵情況修正后的概率值

這里我們就可以對1--3路段重新賦予新的權(quán)值（期望費(fèi)用）：

當(dāng)該路段預(yù)測擁堵時(shí)，其期望的費(fèi)用值為 E1-3= P（A1/x1）× F1+P（A2/x1）×F2=0.567×10+0.433×8=9.134，此時(shí)在計(jì)算最小的總期望費(fèi)用時(shí)，只需要將1-3路段的權(quán)值從9.2改為9.134即可，這樣就得到了最優(yōu)的總期望費(fèi)用：17.934；相應(yīng)的路線依然不變，還是1→3→6。

而該路段預(yù)測不擁堵的時(shí)候，E1-3= P（A1/x2）× F1+P（A1/x2）× F2=9。286，此時(shí)交通網(wǎng)絡(luò)的最優(yōu)的期望費(fèi)用為18.086；對應(yīng)的最優(yōu)路線也是依然沒有變化。

由上述的公式可知E＊=17.934×0.74+18.0 86×0.26=17.973

因此，當(dāng)進(jìn)行預(yù)測的成本C大于18-17.973=0.026時(shí)，收集信息的成本是大于進(jìn)行預(yù)測的所節(jié)約的費(fèi)用，此時(shí)可以選擇放棄預(yù)測，否則，可以進(jìn)行預(yù)測。

結(jié)論：

本文用修正的概率公式對網(wǎng)絡(luò)圖的路線進(jìn)行改進(jìn)，結(jié)果表明，在收集信息的成本超過0.026的時(shí)候，情報(bào)價(jià)值小于收集信息所需要的成本，預(yù)測反而不如不預(yù)測。而當(dāng)收集信息的成本小于0.026時(shí)，則可以進(jìn)行預(yù)測分析以獲取更大的利益。本文通過貝葉斯預(yù)測以及信息的價(jià)值與成本之間的關(guān)系，對是否進(jìn)行預(yù)測做出了完整的解釋，當(dāng)然，本文也有許多不足之處：一是在改變權(quán)值時(shí)，最小的總期望費(fèi)用是隨之改變的，而最優(yōu)的路線也是可以變化的，這里并沒有考慮在內(nèi)；二是沒有考慮到實(shí)際路況的復(fù)雜程度，比如說紅綠燈、駕駛員的移動(dòng)偏好等因素，而只是利用最簡單的網(wǎng)絡(luò)圖來抽象實(shí)際的情況，這將是以后研究的重要方向。