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

1、引言

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

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

在道路擁堵預(yù)測最短路問題的研究中，關(guān)于將權(quán)值看作是隨機變量所涉及的相關(guān)理論，前人已經(jīng)做了很多工作：Miller-Hooks E（2003）[1]把交通網(wǎng)絡(luò)圖中各個路段上的路權(quán)看作是一個與時間相關(guān)的隨機變量，將各個期望值的賦為路段的權(quán)值，進而求得起始點到終點的最短路。袁二明等（2013）[2]通過對交通擁堵的預(yù)測來修正交通網(wǎng)絡(luò)中發(fā)生擁堵的概率分布，從而得到在交通網(wǎng)絡(luò)期望費用值最少的最短路線，算例仿真結(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ù)測進行了深入研究，建立了一種多模型融合預(yù)測方法。陳允峰（2015）[5]提出了兩種利用Lingo軟件求解的最短路方法，并給出具體的實例驗證了其中的正確性。鄒桂芳和張培愛（2011）[6]在Gauss-Seidel迭代法思想的基礎(chǔ)上，提出了一種改進的Floyd算法來計算任意兩點之間的最短路問題。丁浩和萇道方（2014）[7]利用Dijkstra算法來迅速尋找出快遞車輛配送派件過程中的最短路，并與解決該類問題常用的遺傳算法，蟻群算法進行了比較分析。

2、模型與建立與求解

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

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

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

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

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

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

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

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

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

3、算例仿真

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

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

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

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

圖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路段為例，下一步要進行的是利用貝葉斯公式來計算一下修正概率。

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

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

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

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

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

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

當(dāng)該路段預(yù)測擁堵時，其期望的費用值為 E1-3= P（A1/x1）× F1+P（A2/x1）×F2=0.567×10+0.433×8=9.134，此時在計算最小的總期望費用時，只需要將1-3路段的權(quán)值從9.2改為9.134即可，這樣就得到了最優(yōu)的總期望費用：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)的期望費用為18.086；對應(yīng)的最優(yōu)路線也是依然沒有變化。

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

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

結(jié)論：

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