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

文/苗軍 南京財經大學管理科學與工程學院 江蘇南京 210023

1、引言

近年來交通網絡優化已經成為交通問題研究的熱點。而城市交通網絡的最短路問題的分析可以有效地緩解資源的配置問題，也越來越成為熱點問題，對現實生活中的城市道路進行最短路分析，首先要將現實的城市道路網絡抽象化為圖論中的網絡圖，在確定網絡圖相應的權重后按照適當的算法及軟件進行最短路分析，從而得到最短路問題的解。

在交通網絡中，最短路分析一般是指網絡圖中各路段的權值之和最小，這個權值可以是出行的時間，也可以是出行的費用。而對于權值不同的理解，又可將此類問題分為兩大類：一是將權值看作是非隨機變量，當這個非隨機變量不隨著時間的變化時就是確定性靜態最短路，反之，如果隨著時間的變化而變化，那就是確定性的動態最短路問題。第二大類則是將權值看成是隨機變量，每個不同值的出現是有一定的概率的，此時在求最短路的時候就要轉換成求期望值最小。

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

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

2、模型與建立與求解

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

第一步：駕駛員根據經驗對網絡圖的各個路段的擁堵情況做出的預估，A1表示路段發生擁堵，A2則表示不發生擁堵，其對應的概率值就用P（A1）與P（A2）來表示，這個概率值成為先驗概率，根據先驗概率以及費用可以得出每個路段相應的期望值，進而得到最優選擇的狀況下的期望值。

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

由上述的公式的到了各個路段的出行費用的期望值，將該期望值設為權值，利用Lingo軟件可以求解相應的最優解，即最小的總期望值ETOTLE，同時也能得到相應的最優交通路線。

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

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

這樣就得到了修正后的出行費用的期望值，同樣以E＊代替E得到新的權值，利用Lingo得出最優的路徑和最小的總期望值E＊TOTLE 。

第三步：在上面兩個步驟的基礎上，本文可以用情報價值來判斷是否應該做出預測，即：

其中C表示獲得以往的預測信息所耗費的成本，當EVPI＞0的時候，說明預測所帶來的收益是大于不預測帶來的收益的，我們認為預測是有用的，反之，如果EVIS≤0的時候，就沒有必要進行預測了，因為這時候的預測成本超過了預測所帶來的收益。

3、算例仿真

圖1 某區域道路的網絡圖

簡單地將某個地區的道路交通路線抽象為上述的交通網絡圖。每個路段的擁堵情況以及相應的費用如表1所示：

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

利用Lingo軟件得到圖2所示的結果：

圖2 最短路線問題的運行結果

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

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

表2 對于1-3路段預測擁堵情況的準確度

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

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

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

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

這里我們就可以對1--3路段重新賦予新的權值（期望費用）：

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

而該路段預測不擁堵的時候，E1-3= P（A1/x2）× F1+P（A1/x2）× F2=9。286，此時交通網絡的最優的期望費用為18.086；對應的最優路線也是依然沒有變化。

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

因此，當進行預測的成本C大于18-17.973=0.026時，收集信息的成本是大于進行預測的所節約的費用，此時可以選擇放棄預測，否則，可以進行預測。

結論：

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