潘義勇，陳 璐，丁 袁

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

0 引 言

最優(yōu)路徑問題是圖論的熱點研究問題之一，也是交通網(wǎng)絡(luò)均衡問題的核心子問題和車輛導(dǎo)航系統(tǒng)的核心問題[1]，由于交通網(wǎng)絡(luò)的隨機(jī)特性，傳統(tǒng)的最優(yōu)路徑問題的建模及其求解算法難以滿足實際交通情形的需要，因此需對隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最優(yōu)路徑問題展開研究。

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

定義條件風(fēng)險值為路徑目標(biāo)函數(shù)，建立隨機(jī)交通網(wǎng)絡(luò)束最小條件風(fēng)險路徑問題數(shù)學(xué)模型并對其求解算法展開討論。首先，為了反映交通網(wǎng)絡(luò)中風(fēng)險規(guī)避的路徑選擇行為，引入風(fēng)險理論中的條件風(fēng)險值指標(biāo)，建立隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最小條件風(fēng)險路徑問題數(shù)學(xué)模型，證明了路徑目標(biāo)函數(shù)條件風(fēng)險值的次可加性，把最小條件風(fēng)險路徑問題轉(zhuǎn)化為基于路段的最小條件風(fēng)險路徑問題；其次，構(gòu)造基于動態(tài)規(guī)劃的標(biāo)號算法求解該問題；第三，編寫計算機(jī)算法程序，并針對實際交通網(wǎng)絡(luò)：Sioux Falls Network展開數(shù)值試驗并對計算結(jié)果進(jìn)行了分析。最后，總結(jié)了研究成果的應(yīng)用性以及進(jìn)一步研究的方向。

1 問題描述與建模

(1)

其中：

(2)

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

(3)

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

(4)

(5)

其中：

(6)

針對以上的路徑目標(biāo)函數(shù)，隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最小條件風(fēng)險路徑問題建模為以下0～1整數(shù)規(guī)劃問題：

(7)

(8)

由于條件風(fēng)險值的不可加性，公式(7)的路徑目標(biāo)函數(shù)是不可加的，因此不能采用常用的基于動態(tài)規(guī)劃的標(biāo)號算法求解該問題，下面我們對上述基于路徑的最小條件風(fēng)險路徑問題進(jìn)行松弛，證明基于路徑的條件風(fēng)險值滿足次可加性。

定理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表明：一方面，隨機(jī)交通網(wǎng)絡(luò)環(huán)境下基于路徑的最小條件風(fēng)險路徑問題的目標(biāo)函數(shù)不具有可加性，因此基于路徑的最小條件風(fēng)險路徑不滿足Bellman準(zhǔn)則[13]，不能通過基于動態(tài)規(guī)劃的算法來解決該問題；另一方面，路段的條件風(fēng)險值之和是路徑的最小條件風(fēng)險值的上界。因此我們可以把路段的條件風(fēng)險值之和作為路徑的目標(biāo)函數(shù)，構(gòu)造基于路段的最小條件風(fēng)險路徑問題模型。

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

針對以上的路徑目標(biāo)函數(shù)，基于路段的最小條件風(fēng)險路徑問題建模為下列混合非線性整數(shù)約束優(yōu)化問題：

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)

由于基于路段的最小條件風(fēng)險路徑問題的目標(biāo)函數(shù)的可加性，也就表明基于路段的最小條件風(fēng)險路徑的任意子路徑都是基于路段的最小條件風(fēng)險子路徑，滿足動態(tài)規(guī)劃的Bellman準(zhǔn)則，因此我們可以通過基于動態(tài)規(guī)劃的算法來解決該問題。

2 求解算法

本節(jié)構(gòu)造基于動態(tài)規(guī)劃的標(biāo)號算法求解基于路段的隨機(jī)交通網(wǎng)絡(luò)最小條件風(fēng)險路徑問題，標(biāo)號算法是一種求解動態(tài)規(guī)劃問題的最常用算法，具體的程序算法見表1。

表1 基于動態(tài)規(guī)劃的標(biāo)號算法

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

步驟2：修正臨時標(biāo)號。設(shè)i是前一輪標(biāo)號(第K-1輪標(biāo)號)剛得到P標(biāo)號的點，則對所有沒有得到P標(biāo)號的點進(jìn)行新的一輪標(biāo)號(第K輪)?？紤]所有與i相鄰并沒有標(biāo)上P標(biāo)號的點j，修改j的T標(biāo)號為：

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

(16)

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

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

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

(17)

給點Tj0標(biāo)上P標(biāo)號，即：

P(j0)=TK(j0)

(18)

步驟4：判定算法終止。若N中已沒有T標(biāo)號點，則算法結(jié)束，否則轉(zhuǎn)入步驟2。

3 數(shù)值試驗

通過MATLAB計算機(jī)語言編寫基于動態(tài)規(guī)劃的標(biāo)號算法求解上述隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最小條件風(fēng)險路徑問題，并且在Windows-10 (64) 工作站(two 2.00 GHz Xeon CPUs and 4G RAM )條件下運行的。Sioux Falls Network是國際常用的交通測試網(wǎng)絡(luò)，其拓?fù)浣Y(jié)構(gòu)如圖1。

圖1 蘇福爾斯網(wǎng)絡(luò)

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

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。求在此隨機(jī)網(wǎng)絡(luò)環(huán)境下任意起點到任意終點的基于路段的最小條件風(fēng)險路徑。

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

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

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

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

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

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

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

4)筆者提出的標(biāo)號算法能夠求解隨機(jī)網(wǎng)絡(luò)環(huán)境下基于路段的最小條件風(fēng)險路徑問題的精確解，獲得最優(yōu)路徑和其相應(yīng)的最小條件風(fēng)險值，能直接反饋給駕駛員，求解算法已經(jīng)研究的很成熟，在優(yōu)化軟件中采用較多，這有利于我們進(jìn)一步利用現(xiàn)有軟件實現(xiàn)考慮風(fēng)險性的最優(yōu)路徑的導(dǎo)航應(yīng)用研究。

4 結(jié) 語

針對交通網(wǎng)絡(luò)中群體考慮風(fēng)險的路徑選擇行為和對超出風(fēng)險值的不可靠性彈性容忍的路徑選擇行為，建立了隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最小條件風(fēng)險路徑問題數(shù)學(xué)模型，證明了路徑目標(biāo)函數(shù)條件風(fēng)險值的次可加性，把最小條件風(fēng)險路徑問題轉(zhuǎn)化為基于路段的最小條件風(fēng)險路徑問題，構(gòu)造基于動態(tài)規(guī)劃的標(biāo)號算法求解該問題，通過數(shù)值試驗驗證了該模型和算法的正確性和可行性。提出的隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最小風(fēng)險路徑模型能更準(zhǔn)確的反映交通網(wǎng)絡(luò)中風(fēng)險規(guī)避的路徑選擇行為，豐富了車輛導(dǎo)航系統(tǒng)的路徑選擇情形。提出的基于動態(tài)規(guī)劃的標(biāo)號算法是求解隨機(jī)交通網(wǎng)絡(luò)最小條件風(fēng)險路徑問題的有效算法，可以很好地應(yīng)用在車輛導(dǎo)航系統(tǒng)。本研究假設(shè)隨機(jī)網(wǎng)絡(luò)中邊的隨機(jī)變量之間是相互獨立的，沒有考慮隨機(jī)變量的相關(guān)性，考慮相關(guān)性的隨機(jī)網(wǎng)絡(luò)環(huán)境下約束最優(yōu)路徑問題需要進(jìn)一步研究。