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

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

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

1、引言

近年來交通網(wǎng)絡(luò)優(yōu)化已經(jīng)成為交通問題研究的熱點(diǎn)。而城市交通網(wǎng)絡(luò)的最短路問題的分析可以有效地緩解資源的配置問題，也越來越成為熱點(diǎn)問題，對(duì)現(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)用。而對(duì)于權(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ù)測(cè)最短路問題的研究中，關(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]通過對(duì)交通擁堵的預(yù)測(cè)來修正交通網(wǎng)絡(luò)中發(fā)生擁堵的概率分布，從而得到在交通網(wǎng)絡(luò)期望費(fèi)用值最少的最短路線，算例仿真結(jié)果表明交通擁堵預(yù)測(cè)能起到積極作用。此外，談蔚欣（2006）[3]介紹了樣本數(shù)據(jù)處理的具體過程，確定了合適的擁堵預(yù)測(cè)指標(biāo)體系，選擇了LMBP神經(jīng)網(wǎng)絡(luò)作為組合分類器的元學(xué)習(xí)算法，選用了投票法和平均法作為分類器輸出的組合規(guī)則。并針對(duì)整個(gè)擁堵預(yù)測(cè)過程做了系統(tǒng)的闡述。

而在求解道路交通的最短路的相關(guān)算法與理論上：黃國(guó)浪（2014）[4]提出了一種新的城市交通擁堵識(shí)別算法，并對(duì)城市交通擁堵預(yù)測(cè)中的關(guān)鍵技術(shù)交通流參數(shù)短時(shí)預(yù)測(cè)進(jìn)行了深入研究，建立了一種多模型融合預(yù)測(cè)方法。陳允峰（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ù)測(cè)的結(jié)果和以往的信息的基礎(chǔ)上，對(duì)原有的道路擁堵的可能性做出修正，修正所涉及的原理就是貝葉斯定理。下面則是建模的具體步驟：

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

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

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

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

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

則表示修正后的概率值。

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

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

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

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

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

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

3、算例仿真

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

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

利用Lingo軟件得到圖2所示的結(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ì)算一下修正概率。

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

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ù)測(cè)擁堵且實(shí)際就是擁堵的概率為：

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

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

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

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

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

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

結(jié)論 ：

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

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

[4]黃國(guó)浪.城市交通擁堵的識(shí)別與預(yù)測(cè)[D].長(zhǎng)安大學(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].價(jià)值工程，2014（3）：15-18.

作者簡(jiǎn)介：

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