隨機交通網絡最小條件風險路徑問題

潘義勇，陳 璐，丁 袁

(南京林業大學 汽車與交通工程學院， 江蘇 南京 210037)

0 引 言

最優路徑問題是圖論的熱點研究問題之一，也是交通網絡均衡問題的核心子問題和車輛導航系統的核心問題[1]，由于交通網絡的隨機特性，傳統的最優路徑問題的建模及其求解算法難以滿足實際交通情形的需要，因此需對隨機交通網絡環境下最優路徑問題展開研究。

由于交通網絡路徑行程時間是一個隨機變量，和傳統的最短路徑問題不同，不能簡單的比較隨機變量的大小，因此研究人員基于風險理論定義不同的路徑目標函數，建立不同的隨機交通網絡環境下的最優路徑模型。最小期望路徑問題是最先提出來的模型[2]，最小期望路徑是以期望值為路徑的目標函數，沒有考慮由于交通網絡隨機特性帶來的路徑風險性。在交通實際情形中駕駛員不僅關注行程時間的期望值最少而且關注行程時間的風險性最小[3-4]，因此研究人員開始在路徑目標函數中加入風險指標，主要有：最小期望-均方差路徑問題[5-7]，最大可靠度路徑問題[8-9]，α-可靠路徑問題等[10]，最小期望-均方差路徑問題的路徑目標函數是期望值和均方差的線性組合，其優點是綜合考慮了期望值和均方差，其缺點是線性組合的比例系數需要人為設定，具有隨意性，不能統一解釋考慮風險的路徑選擇行為。最大可靠度路徑問題的路徑目標函數是可靠性理論中的重要指標：可靠度，其優點是直接反映了路徑的風險性，其缺點是需要事先設定一個期望到達終點的時間，但是現實中駕駛員一般不知道到達終點的時間。α-可靠路徑問題中的路徑目標函數是風險理論中的重要風險指標：風險值[11]，風險值不需要事先設定一個期望到達終點的時間，只需給定一個風險置信水平，在嚴格確保風險置信水平的前提下尋找期望值最小的路徑，風險值雖然反映了路徑行程時間的風險性，但是過于嚴格，不能反映實際路徑選擇中超出期望時間的容忍度，因此筆者引入風險理論中的另外一個風險指標：條件風險值，該指標優點是準確反映交通網絡中群體考慮風險的路徑選擇行為和對超出風險值的不可靠性彈性容忍的路徑選擇行為[12]。風險理論在金融學領域已經發展的相當完善，研究投資者在金融領域的投資行為，這和隨機交通網絡路徑選擇行為具有高度的相似性，交通網絡最優路徑研究可以借助現有的風險理論研究方法與結論進一步拓展改善，推動整個最優路徑導航系統理論的發展。

定義條件風險值為路徑目標函數，建立隨機交通網絡束最小條件風險路徑問題數學模型并對其求解算法展開討論。首先，為了反映交通網絡中風險規避的路徑選擇行為，引入風險理論中的條件風險值指標，建立隨機交通網絡環境下最小條件風險路徑問題數學模型，證明了路徑目標函數條件風險值的次可加性，把最小條件風險路徑問題轉化為基于路段的最小條件風險路徑問題；其次，構造基于動態規劃的標號算法求解該問題；第三，編寫計算機算法程序，并針對實際交通網絡：Sioux Falls Network展開數值試驗并對計算結果進行了分析。最后，總結了研究成果的應用性以及進一步研究的方向。

1 問題描述與建模

(1)

其中：

(2)

x={xij∈{0,1}|(i,j)∈A}

(3)

其中：xij=1表示邊(i,j)在先驗路徑x上，xij=0表示邊(i,j)不在先驗路徑x上。此時先驗路徑x上的隨機行程時間為

(4)

(5)

其中：

(6)

針對以上的路徑目標函數，隨機交通網絡環境下最小條件風險路徑問題建模為以下0～1整數規劃問題：

(7)

(8)

由于條件風險值的不可加性，公式(7)的路徑目標函數是不可加的，因此不能采用常用的基于動態規劃的標號算法求解該問題，下面我們對上述基于路徑的最小條件風險路徑問題進行松弛，證明基于路徑的條件風險值滿足次可加性。

定理1：

(9)

證明：

(10)

(11)

(12)

(13)

其中：

Z3=E[t～ij|∑(i,j)∈At～ijxijVaRα(∑(i,j)∈At～ijxij),t～ij>VaRα(t～ij)]1=E[t～ij|∑(i,j)∈At～ijxij>VaRα(∑(i,j)∈At～ijxij),t～ij>VaRα(t～ij)]

定理1表明：一方面，隨機交通網絡環境下基于路徑的最小條件風險路徑問題的目標函數不具有可加性，因此基于路徑的最小條件風險路徑不滿足Bellman準則[13]，不能通過基于動態規劃的算法來解決該問題；另一方面，路段的條件風險值之和是路徑的最小條件風險值的上界。因此我們可以把路段的條件風險值之和作為路徑的目標函數，構造基于路段的最小條件風險路徑問題模型。

定義2：(基于路段的最小條件風險路徑)給定風險置信水平α，x*是基于路段的最小條件風險路徑當且僅當x*=argmin{∑(i,j)∈ACVaRα(t～ij)xij,?x}。

針對以上的路徑目標函數，基于路段的最小條件風險路徑問題建模為下列混合非線性整數約束優化問題：

minf′(x)=∑(i,j)∈ACVaRα(t～ij)xij=

∑(i,j)∈AEt～ij|t～ij>VaRα(t～ij)xij

(14)

s.t{∑(i,j)∈Axij-∑(j,i)∈Axji={1, i=o

0, i∈N-(o,d)

-1, i=d

xji∈{0,1}, ?(i,j)∈A

(15)

由于基于路段的最小條件風險路徑問題的目標函數的可加性，也就表明基于路段的最小條件風險路徑的任意子路徑都是基于路段的最小條件風險子路徑，滿足動態規劃的Bellman準則，因此我們可以通過基于動態規劃的算法來解決該問題。

2 求解算法

本節構造基于動態規劃的標號算法求解基于路段的隨機交通網絡最小條件風險路徑問題，標號算法是一種求解動態規劃問題的最常用算法，具體的程序算法見表1。

表1 基于動態規劃的標號算法

步驟1：初始化。給起點o∈N標上永久標號P標號：P(o)=0，其余各點標上臨時T標號：T0(j)=+∞，表示從o∈N到o∈N最短路權為0，從o∈N到各點的最短路權的上界為+∞。

步驟2：修正臨時標號。設i是前一輪標號(第K-1輪標號)剛得到P標號的點，則對所有沒有得到P標號的點進行新的一輪標號(第K輪)。考慮所有與i相鄰并沒有標上P標號的點j，修改j的T標號為：

TK(j)=min[T(j),P(i)+CVaRα(t～ij)]

(16)

式中：T(j)為第K輪標號前Vj點已取得的T標號。

步驟3：修正永久標號。在所有的T標號中，尋找一個最小的T標號TK(j0)方式為

TK(j0)=min[TK(j)]

(17)

給點Tj0標上P標號，即：

P(j0)=TK(j0)

(18)

步驟4：判定算法終止。若N中已沒有T標號點，則算法結束，否則轉入步驟2。

3 數值試驗

通過MATLAB計算機語言編寫基于動態規劃的標號算法求解上述隨機交通網絡環境下最小條件風險路徑問題，并且在Windows-10 (64) 工作站(two 2.00 GHz Xeon CPUs and 4G RAM )條件下運行的。Sioux Falls Network是國際常用的交通測試網絡，其拓撲結構如圖1。

圖1 蘇福爾斯網絡

為了仿真交通網絡行程時間的隨機特性，設定交通網絡中每個路段的行程時間服從正態分布t～ij～N(μij,σ2ij)，不同的概率分布的設定不影響數值試驗對本文的模型和算法的正確性和可行性的驗證，本文的隨機交通網絡最小條件風險路徑模型對網絡中每個路段行程時間的概率分布是沒有限制的，具有普適性。網絡中每條邊的期望值μij從區間[0,20]等概論隨機取得，每條邊的方差σ2ij從區間[0,10]等概率隨機取得，根據條件風險值的定義，可以求得每個路段(i,j)的條件風險值為

CVaRα(t～ij)=E[t～ij|t～ij>VaRα(t～ij)]=μij+

k(α)σij

(19)

其中：k(α)={2π[exp(erf-1(2α-1)]22(1-α)}-1，erf(z)=2π∫z0e-t2dt。求在此隨機網絡環境下任意起點到任意終點的基于路段的最小條件風險路徑。

表2給出了在風險置信水平α=0.5條件下，不同起迄點之間的最小條件風險路徑和最小條件風險值。表3給出了不同風險置信水平條件下，起迄點13→8之間的基于路段的最小條件風險路徑和最小條件風險值。表4給出了不同風險置信水平條件下，起迄點2→23之間的最小條件風險路徑和最小條件風險值。從計算結果可以得出以下結論：

1)表2顯示在風險置信水平α=0.5條件下，不同起迄點之間的期望值、條件風險值和基于路段的最小條件風險路徑是不同的，表3顯示起迄點13→8在不同風險置信水平條件下，其求解的基于路段的最小條件風險路徑及其期望值、條件風險值是不同的，表4顯示起迄點2→23在不同置信水平條件下，其求解的基于路段的最小條件風險路徑及其期望值、條件風險值是不同的。由此可以看出，在相同的風險置信水平條件下，起迄點之間的基于路段的最小條件風險路徑是不同的，在不同風險置信水平條件下，相同的起迄點之間的基于路段的最小條件風險路徑是不同的，風險置信水平條件對路徑的選擇具有重大的影響，這符合實際交通網絡考慮風險性的路徑選擇行為的情形。

表2 不同起迄點之間的最小條件風險路徑和最優值(α=0.5)

表3 不同置信水平條件下最小條件風險路徑和最優值(13→8)

2)表2～表4顯示了不同情形下獲得基于路段的最小條件風險路徑的條件風險值，并相應的計算了給路徑的期望值，通過比較可以看出，獲得的最優路徑的條件風險值都比該路徑的期望值要大，這符合風險理論中關于條件風險值的定義，也反映了交通網絡中群體考慮風險的路徑選擇行為和對超出風險值的不可靠性彈性容忍的路徑選擇行為。

表4 不同置信水平條件下最小條件風險路徑和最優值(2→23)

3)表3～表4顯示在相同的起迄點之間，風險置信水平對最優路徑的選擇是有影響的，在起迄點13→8之間，當α=0.2,0.4,0.5,0.8時，其獲得最優路徑都是不同的，并且隨著風險置信水平的增大，其相應的最優路徑的條件風險值也是增加的，同樣在起迄點2→23之間，當α=0.3,0.5,0.8時，其獲得最優路徑也是不同的，其相應的最優路徑的條件風險值也是增加的。一方面，在實際交通網絡中由于駕駛員不同的風險規避的要求，駕駛員選擇的路徑也是不同的；另一方面，隨著風險置信水平的提高，駕駛員對交通網絡中對路徑行程時間超出風險值的不可靠性彈性容忍的期望值提高，這符合實際交通網絡的路徑選擇行為。

4)筆者提出的標號算法能夠求解隨機網絡環境下基于路段的最小條件風險路徑問題的精確解，獲得最優路徑和其相應的最小條件風險值，能直接反饋給駕駛員，求解算法已經研究的很成熟，在優化軟件中采用較多，這有利于我們進一步利用現有軟件實現考慮風險性的最優路徑的導航應用研究。

4 結 語

針對交通網絡中群體考慮風險的路徑選擇行為和對超出風險值的不可靠性彈性容忍的路徑選擇行為，建立了隨機交通網絡環境下最小條件風險路徑問題數學模型，證明了路徑目標函數條件風險值的次可加性，把最小條件風險路徑問題轉化為基于路段的最小條件風險路徑問題，構造基于動態規劃的標號算法求解該問題，通過數值試驗驗證了該模型和算法的正確性和可行性。提出的隨機交通網絡環境下最小風險路徑模型能更準確的反映交通網絡中風險規避的路徑選擇行為，豐富了車輛導航系統的路徑選擇情形。提出的基于動態規劃的標號算法是求解隨機交通網絡最小條件風險路徑問題的有效算法，可以很好地應用在車輛導航系統。本研究假設隨機網絡中邊的隨機變量之間是相互獨立的，沒有考慮隨機變量的相關性，考慮相關性的隨機網絡環境下約束最優路徑問題需要進一步研究。