隨機(jī)交通網(wǎng)絡(luò)最小條件風(fēng)險(xiǎn)路徑問(wèn)題

潘義勇，陳 璐，丁 袁

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

0 引 言

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

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

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

1 問(wèn)題描述與建模

(1)

其中：

(2)

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

(3)

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

(4)

(5)

其中：

(6)

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

(7)

(8)

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

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

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

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

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

2 求解算法

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

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

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

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

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

(16)

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

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

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

(17)

給點(diǎn)Tj0標(biāo)上P標(biāo)號(hào)，即：

P(j0)=TK(j0)

(18)

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

3 數(shù)值試驗(yàn)

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

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

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

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)境下任意起點(diǎn)到任意終點(diǎn)的基于路段的最小條件風(fēng)險(xiǎn)路徑。

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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