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

【摘要】在經(jīng)濟(jì)的發(fā)展與城市化的進(jìn)程中，道路交通網(wǎng)絡(luò)優(yōu)化問題日益突出。本文利用道路擁堵狀況的概率值與擁堵的費(fèi)用得到期望值，以此對網(wǎng)絡(luò)圖的權(quán)值賦予了一個新的定義，利用Lingo軟件求解相應(yīng)的最優(yōu)解，并結(jié)合以往的預(yù)測信息，利用貝葉斯條件概率對先驗(yàn)概率進(jìn)行修正，賦予一個新的權(quán)值，從而得到了一個更為優(yōu)化結(jié)果，考慮預(yù)測信息的獲取成本的，本文引入了情報(bào)價值來刻畫信息的效果。結(jié)果表明：當(dāng)收集信息的成本大于情報(bào)價值0.026時，選擇不收集情報(bào)，反之，則可以進(jìn)行信息收集。

【關(guān)鍵詞】最短路；道路擁堵預(yù)測；貝葉斯；情報(bào)價值

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)值之和最小，這個權(quán)值可以是出行的時間，也可以是出行的費(fèi)用。而對于權(quán)值不同的理解，又可將此類問題分為兩大類：一是將權(quán)值看作是非隨機(jī)變量，當(dāng)這個非隨機(jī)變量不隨著時間的變化時就是確定性靜態(tài)最短路，反之，如果隨著時間的變化而變化，那就是確定性的動態(tài)最短路問題。第二大類則是將權(quán)值看成是隨機(jī)變量，每個不同值的出現(xiàn)是有一定的概率的，此時在求最短路的時候就要轉(zhuǎn)換成求期望值最小。

在道路擁堵預(yù)測最短路問題的研究中，關(guān)于將權(quán)值看作是隨機(jī)變量所涉及的相關(guān)理論，前人已經(jīng)做了很多工作：Miller-Hooks E（2003）[1]把交通網(wǎng)絡(luò)圖中各個路段上的路權(quán)看作是一個與時間相關(guān)的隨機(jī)變量，將各個期望值的賦為路段的權(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ī)則。并針對整個擁堵預(yù)測過程做了系統(tǒng)的闡述。

而在求解道路交通的最短路的相關(guān)算法與理論上：黃國浪（2014）[4]提出了一種新的城市交通擁堵識別算法，并對城市交通擁堵預(yù)測中的關(guān)鍵技術(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、模型與建立與求解

本文所研究的問題是城市道路交通擁堵問題，由于道路是否擁堵是一個不確定性的因素，具有一定的概率值，而且擁堵以及不擁堵所消耗的費(fèi)用（考慮到信息成本的單位，這里統(tǒng)一使用費(fèi)用而不是時間）也是有所不同的，所以本文所建立的網(wǎng)絡(luò)圖問題是屬于第二大類別---將權(quán)值看作是隨機(jī)變量，在此，關(guān)于如何確定擁堵的概率值以及所花費(fèi)的時間來計(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ò)圖的各個路段的擁堵情況做出的預(yù)估，A1表示路段發(fā)生擁堵，A2則表示不發(fā)生擁堵，其對應(yīng)的概率值就用P（A1）與P（A2）來表示，這個概率值成為先驗(yàn)概率，根據(jù)先驗(yàn)概率以及費(fèi)用可以得出每個路段相應(yīng)的期望值，進(jìn)而得到最優(yōu)選擇的狀況下的期望值。

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

E = P（A1）× F1 + P（A2）× F2 （1-1）

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

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

則表示修正后的概率值。

此時利用上式得到的期望值就是：

E*=P（A1/x1）× F1+P（A2/x2）× F2 （1-3）

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

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

EVPI=E*TOTLE - ETOTLE–C （1-4）

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

3、算例仿真

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

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

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

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

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

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

P（x1）= P（A1）× P（x1/A1）+ P（A2）× P（x1/A2）=0.6×0.7+0.4×0.8 = 0.74

P（x2）= P（A1）× P（x2/A1）+ P（A2）× P（x2/A2）=0.6×0.3+0.4×0.2 = 0.26

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

P（A1/x1）= P（A1）× P（x1/A1）/ P（x1）= 0.6×0.7/0.74 = 0.567

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

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

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

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

由上述的公式可知E*=17.934×0.74+18.086×0.26=17.973

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

結(jié)論 ：

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

參考文獻(xiàn) ：

[1] Miller-Hooks E， Mahmassani H. Path comparisons for a priori and time-adaptive decisions in stochastic，time-varying networks[J]. European Journal of Operational Research，2003，146（1）：67-82.

[2]袁二明，李瑩，李彪.基于交通擁堵預(yù)測的交通網(wǎng)絡(luò)最短路問題的研究[J].中國管理科學(xué)，2013，S1：43-45

[3]談蔚欣.基于分類器組合的交通擁堵預(yù)測[D].福州大學(xué)，2006.

[4]黃國浪.城市交通擁堵的識別與預(yù)測[D].長安大學(xué)，2014

[5]陳允峰.利用lingo軟件解決最短路問題的兩種方法[J].信息技術(shù)與信息化，2015（10）：141-142.

[6]鄒桂芳，張培愛.網(wǎng)絡(luò)優(yōu)化中最短路問題的改進(jìn)Floyd算法[J].科學(xué)技術(shù)與工程，2011，11（28）：6875-6878.

[7]丁浩，萇道方.基于Dijkstra算法的快遞車輛配送路徑優(yōu)化[J].價值工程，2014（3）：15-18.

作者簡介：

苗軍，年齡：24，男，單位：南京財(cái)經(jīng)大學(xué)管理科學(xué)與工程學(xué)院，碩士研究生，研究方向：模式識別。