隨機(jī)交通網(wǎng)絡(luò)約束最可靠路徑問題

潘義勇，陳 璐，孫 璐

(1.南京林業(yè)大學(xué)汽車與交通工程學(xué)院，南京210037；2.東南大學(xué)交通學(xué)院，南京210096；3.美國Catholic大學(xué) 土木工程系，華盛頓特區(qū)DC 20064，美國)

0 引言

最優(yōu)路徑問題是車輛導(dǎo)航系統(tǒng)的核心問題，現(xiàn)有的導(dǎo)航系統(tǒng)沒有考慮交通網(wǎng)絡(luò)的隨機(jī)特性和路徑選擇時的約束條件[1].一方面，交通網(wǎng)絡(luò)中行程時間具有隨機(jī)性，需要研究考慮可靠性的最優(yōu)路徑問題；另一方面，駕駛員在選擇最優(yōu)路徑時都會受到各種約束條件的限制，例如行車距離，機(jī)動車的油耗，電動汽車的蓄電能力等，因此需對隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最可靠路徑問題進(jìn)行研究[1].

目前，對隨機(jī)交通網(wǎng)絡(luò)環(huán)境下無約束最優(yōu)路徑問題研究的很多，主要有最小期望路徑問題[1]和最可靠路徑問題[2]，其中最小期望路徑問題沒有考慮由于交通網(wǎng)絡(luò)隨機(jī)特性帶來的風(fēng)險性，最可靠路徑問題考慮了路徑可靠性的路徑選擇行為.最可靠路徑問題由于其考慮可靠性的路徑目標(biāo)函數(shù)定義的不同，其最可靠路徑模型及其求解算法也是不同的，主要有：最小期望—均方差路徑，最優(yōu)期望效用路徑，最大可靠度路徑，α—可靠路徑等[2]，其中最小期望—均方差路徑最能直接反映路徑的可靠性[3]，另外，當(dāng)路徑的隨機(jī)行程時間服從正態(tài)分布時，其他幾種考慮可靠性的路徑目標(biāo)函數(shù)可以表示為期望和均方差的線性組合，本質(zhì)上也就轉(zhuǎn)化為最小期望—均方差路徑問題，因此本文采用期望—均方差為考慮可靠性的路徑目標(biāo)函數(shù).

針對隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最優(yōu)路徑問題研究的非常少，Wang等首次研究了隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最小期望路徑問題[4]，但是沒有考慮行程時間的可靠性；潘義勇等研究了考慮可靠性的隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑問題[5-6]，其路徑目標(biāo)函數(shù)定義為期望和方差的線性組合，在一定意義上反映了路徑行程時間的可靠性，并且由于期望和方差的可加性，求解該問題比較容易，但是期望值和方差不在一個量綱上，因此其求解的結(jié)果往往會有偏差.

本文在已有研究的基礎(chǔ)上，研究隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最小期望—均方差路徑，避免了上述問題，但是由于均方差的非線性和不可加性，其求解更復(fù)雜，這是本文研究的出發(fā)點.首先，定義期望—均方差為路徑的目標(biāo)函數(shù)，建立隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最可靠路徑問題數(shù)學(xué)模型；其次，討論了該問題的對偶問題；第三，采用梯度下降算法求解對偶問題，獲得原問題最優(yōu)值的上界和下界，通過迭代逼近獲得原問題的近似解；第四，編寫計算機(jī)算法程序，并針對實際交通網(wǎng)絡(luò)Sioux Falls network展開數(shù)值試驗并對計算結(jié)果進(jìn)行了分析；最后，總結(jié)了本文的研究成果及進(jìn)一步研究的方向.

1 問題描述與建模

交通網(wǎng)絡(luò)G=(N,A,X)，N(||N=n)是交通節(jié)點的集合，A(|A|=m)是邊的集合，其中邊相當(dāng)于交通網(wǎng)絡(luò)中的路段.每個節(jié)點i都有若干前節(jié)點和后節(jié)點與之連接，前節(jié)點的集合記為Φ(i)={j,(i,j)∈A} ，后節(jié)點的集合記為Φ-1(i)={k,(k,i)∈A}.邊(i,j)的2個權(quán)值設(shè)置為該路段的行程時間tij和資源消耗wij.交通網(wǎng)絡(luò)中行駛者不僅考慮行程時間，還會受到不同資源的約束，例如，電動汽車耗電量作為路段資源消耗權(quán)重，那么該電動汽車的電池總?cè)萘烤褪瞧滟Y源總消耗的上限值；機(jī)動車碳排放量作為路段資源消耗權(quán)重，政府規(guī)定的碳排放標(biāo)準(zhǔn)可以作為其資源總消耗的上限值.

傳統(tǒng)的約束最短路問題針對的是確定網(wǎng)絡(luò)，其中邊(i,j)的2個權(quán)值tij和wij是確定值，因此，起訖點(o,d)之間的約束最短路徑問題可以描述為0-1整數(shù)規(guī)劃問題，即

由于行程時間的隨機(jī)特性，因此邊(i,j)的權(quán)值tij為隨機(jī)變量，其期望值cij和均方差σij可以通過歷史數(shù)據(jù)獲得.針對這樣的隨機(jī)網(wǎng)絡(luò)，研究人員定義各種路徑目標(biāo)函數(shù)來反映行程時間的可靠性，其中最能直接反映行程時間可靠性的是期望—均方差路徑問題，定義路徑的目標(biāo)函數(shù)為

均方差是用來度量隨機(jī)變量和其期望值之間的偏離程度.把均方差加入到目標(biāo)函數(shù)，可有效控制偏離程度，反映了該路徑行程時間的可靠性.本文把上述確定網(wǎng)絡(luò)環(huán)境下的傳統(tǒng)約束最短路徑問題擴(kuò)展到隨機(jī)網(wǎng)絡(luò)環(huán)境下的約束最可靠路徑問題，即

Wang等首次研究了隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最小期望路徑問題[4]，但是沒有考慮行程時間的可靠性.本文采用期望值和均方差線性組合為路徑目標(biāo)函數(shù)，在目標(biāo)函數(shù)里面添加了均方差，考慮了路徑行程時間的可靠性，并且期望值和均方差在一個量綱上.但是由于均方差的非線性和不可加性，相對于文獻(xiàn)[4]的約束最優(yōu)路徑問題，大大增加了求解該問題的難度，因此討論其對偶問題，從而獲得其近似最優(yōu)解.

2 對偶問題

求解最可靠路徑問題式(6)～式(9)的精確解非常困難，本節(jié)首先通過松弛變換獲得原問題的松弛問題[7]，其次運用拉格朗日對偶理論[7]對上述約束最可靠路徑問題進(jìn)行討論，獲得原問題的對偶問題，求解其對偶問題獲得原問題最優(yōu)解的最大下界.

由于目標(biāo)函數(shù)式(6)中含有非線性函數(shù)，因此我們需要通過變換轉(zhuǎn)化該非線性，其中目標(biāo)函數(shù)式(6)等價于：

雖然增加了1個變量y，但是式(11)可以轉(zhuǎn)化為原問題的約束條件，并且根據(jù)拉格朗日松弛理論，式(11)可以轉(zhuǎn)化為不等式約束條件.

定理1[7]0≤y≤y′，其中y′是最小期望路徑的方差.

因此，隨機(jī)網(wǎng)絡(luò)環(huán)境下的約束最可靠路徑問題式(6)～式(9)可以轉(zhuǎn)化為

下面我們根據(jù)拉格朗日對偶理論推導(dǎo)出式(12)～式(15)的對偶問題，對于任意的拉格朗日罰因子μ=(μ1,μ2)≥0，和，定義拉格朗日函數(shù)為

通過整理可得

其中，

并且，

對于給定的拉格朗日罰因子μ=(μ1,μ2)≥0，其中第1個子問題是傳統(tǒng)的最短路徑問題，可以通過經(jīng)典的標(biāo)號算法求解；第2個子問題是非線性約束優(yōu)化問題，由于其目標(biāo)函數(shù)式(19)是凸函數(shù)，因此其最小值只能在區(qū)間的兩個端點處取到，因此式(20)可以通過其兩個分解的子問題簡單求解.

根據(jù)拉格朗日對偶理論，對于任意的拉格朗日罰因子μ=(μ1,μ2)≥0，式(20)是原問題式(6)～式(9)最優(yōu)值的下界，即

式中：f(x*)為原問題式(6)～式(9)的最優(yōu)值.

原問題式(6)～式(9)的對偶問題為

根據(jù)拉格朗日對偶理論，對偶問題式(21)的最優(yōu)值是松弛問題式(12)～式(15)的下界最大值.

3 求解算法

本節(jié)采用梯度下降算法[7]求解對偶問題式(21).該迭代算法每次選取目標(biāo)函數(shù)的負(fù)梯度方向作為搜索方向，并且常依據(jù)目標(biāo)函數(shù)的梯度來確定搜索步長.在每次迭代步中，對于給定的μ=(μ1,μ2)≥0，通過求解式(20)獲得原問題的下界，求解最短路問題式(18)或者其K-最短路問題可以獲得原問題的上界，通過對μ=(μ1,μ2)≥0迭代不斷縮小上下界之間的差距，當(dāng)上下界之間的差小于等于理論差值時，獲得式(9)的最優(yōu)解.具體的算法步驟如下.

Step 1初始化.

設(shè)k=1，其中k是迭代步數(shù)；初始UB=+∞，LB=-∞，其中UB表示原問題式(9)的上界,LB表示原問題式(9)的下界；初始的拉格朗日罰因子μ=(μ1,μ2)≥0隨機(jī)給定.

Step 2計算下界.

Step 3計算上界.

Step 4修正拉格朗日罰因子.

首先，確定拉格朗日罰因子(μ1,μ2,μ3)修正的搜索方向，其搜索方向為拉格朗日函數(shù)關(guān)于μ=(μ1,μ2)≥0的梯度方向，即

修正拉格朗日罰因子(μ1,μ2)為

Step 5計算誤差.

4 數(shù)值試驗

本節(jié)對上述算法的可行性和正確性進(jìn)行數(shù)值驗證，采用國際標(biāo)準(zhǔn)的測試交通網(wǎng)絡(luò)Sioux Falls(SF)network[5]，如圖1所示.由于實際歷史交通數(shù)據(jù)的缺失，需要在Sioux Falls(SF)network拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，對其網(wǎng)絡(luò)邊的權(quán)值進(jìn)行數(shù)值模擬，從而獲得帶資源約束的隨機(jī)交通網(wǎng)絡(luò)，交通網(wǎng)絡(luò)中邊(i,j)的行程時間tij是隨機(jī)變量，其期望值cij和方差是確定值，分別從區(qū)間[0,20]min取隨機(jī)數(shù)給定.交通網(wǎng)絡(luò)中邊(i,j)的資源消耗wij是確定值，從區(qū)間[0,20]min取隨機(jī)數(shù)給定.上述期望值cij，方差和資源消耗wij一經(jīng)給定就固定不變.這種模擬不影響對本文提出的模型及其算法的數(shù)值驗證，本文提出的約束最可靠路徑模型及其算法不受網(wǎng)絡(luò)邊的權(quán)值設(shè)置的影響，具有普適性.

基于Matlab計算機(jī)語言編寫本文提出的算法程序，并且在Windows-10(64)工作站(two 2.00 GHz Xeon CPUs and 4G RAM)條件下運行的.為了對模型中不同參數(shù)的靈敏度進(jìn)行分析，本節(jié)對不同情形下的約束路徑問題進(jìn)行了數(shù)值實驗，并對數(shù)值結(jié)果進(jìn)行了分析.

圖1 蘇福爾斯網(wǎng)絡(luò)Fig.1 Sioux Falls network

圖2分別給出當(dāng)起迄點設(shè)置為4→15時上界UB和下界LB隨迭代次數(shù)的變化圖，其中初始參數(shù)的設(shè)置為ε?=0.05，W=60，λ=2，從圖2中可以看出，隨著迭代次數(shù)的增加，上界UB逐漸減小，下界LB逐漸增大，最終逼近于最優(yōu)值.這和算法的理論設(shè)計是一致的，驗證了本文構(gòu)造的算法的可行性和正確性.由于初始給定的上界UB=100和下界LB=-100，因此迭代開始階段下界保持LB=-100，隨著迭代次數(shù)的增加，下界LB開始增加，這證明本文推導(dǎo)的原問題的對偶問題是正確的，對偶問題的最優(yōu)解是原問題最優(yōu)解的最大的下界.

圖2 上界UB和下界LB隨迭代次數(shù)的變化圖Fig.2 The variation of upper bound UB and lower bound LB along with number of iterations

表1給出了在ε?=0.05，λ=2條件下，不同起迄點和不同的資源上限W的資源消耗，最優(yōu)值的上下界，相對誤差，以及最可靠路徑，其中W=+∞表示無資源約束條件下的模型求解.從表1中可知，起迄點1→24在不同的資源上限W=50,60約束條件下，其獲得最可靠路徑是不同的；起迄點7→19在不同的資源上限W=30,40約束條件下，其獲得最可靠路徑是不同的；起迄點2→23在不同的資源上限W=40,55約束和無約束W=+∞條件下，其獲得最可靠路徑是不同的.

表1 不同資源總量約束條件下最優(yōu)路徑和最優(yōu)值(1→24)Table 1 The optimal path and the optimal value under different resources constraint(1→24)

由此可以看出：

(1)有資源約束和無資源約束條件下，相同的起迄點之間的最可靠路徑是不同的，有約束和無約束條件下隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最可靠路徑問題具有根本性的不同；

(2)資源約束上限W的取值不同，求解獲得的最可靠路徑和最優(yōu)值也是不同的，資源約束條件對路徑的選擇具有重大的影響，這符合實際交通網(wǎng)絡(luò)最可靠路徑選擇情形；

(3)本文提出的基于對偶理論的近似算法能夠求解隨機(jī)網(wǎng)絡(luò)環(huán)境下約束最可靠路徑問題，獲得最可靠路徑和最優(yōu)解，這有利于我們進(jìn)一步利用現(xiàn)有軟件實現(xiàn)最可靠路徑的導(dǎo)航應(yīng)用研究.

5 結(jié)論

針對交通網(wǎng)絡(luò)中約束條件下考慮可靠性車輛路徑選擇問題，建立了隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最可靠路徑問題數(shù)學(xué)模型，并討論了其對偶問題，采用梯度下降算法求解對偶問題，獲得原問題最優(yōu)值的上界和下界，通過迭代逼近獲得原問題的近似解，針對交通網(wǎng)絡(luò)展開數(shù)值試驗，驗證了該模型和算法的正確性和可行性.相比較于已有模型，本文提出的模型能同時反映交通網(wǎng)絡(luò)的隨機(jī)特性，路徑約束條件的影響及路徑選擇的可靠性，更符合實際交通網(wǎng)絡(luò)路徑選擇情形，本文提出的基于對偶理論的近似求解算法是一個有效的算法.數(shù)值試驗結(jié)果表明：在隨機(jī)交通網(wǎng)絡(luò)環(huán)境下，無約束和有約束條件下求解的最可靠路徑是不同的；不同的資源約束條件下求解的最可靠路徑也是不同的，資源約束條件對交通網(wǎng)絡(luò)中最可靠路徑的選擇有很大的影響.本文只考慮了交通網(wǎng)絡(luò)的隨機(jī)特性，沒有考慮其動態(tài)特性，考慮動態(tài)隨機(jī)網(wǎng)絡(luò)環(huán)境下約束最可靠路徑問題需要進(jìn)一步研究.

參考文獻(xiàn)：

[1]GAO S,CHABINI I.Optimal routing policy problems in stochastic time-dependent networks[J].Transportation Research Part B:Methodological,2006,40(2):93-122.

[2]WU X,NIE Y M.Modeling heterogeneous risk-taking behavior in route choice:A stochastic dominance approach[J].Transportation Research Part A,2011(45):896-915.

[3]KHANI A,BOYLES S D.An exact algorithm for the mean-standard deviation shortest path problem[J].Transportation Research Part B:Methodological,2015(81):252-266.

[4]WANG L,YANG L,GAO Z.The constrained shortest path problem with stochastic correlated link travel times[J].European Journal of Operational Research,2016,255(1):43-57.

[5]潘義勇,馬健霄.基于可靠性的隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑問題研究[J].東南大學(xué)學(xué)報(自科版),2017(6):1263-1268.[PAN Y Y,MA J X.The constrained shortest path problem in stochastic traffic network based on the reliability[J].Journal of Southeast University(Natural Science Edition),2017(6):1263-1268.]

[6]潘義勇,馬健霄,孫璐.基于可靠度的動態(tài)隨機(jī)交通網(wǎng)絡(luò)耗時最優(yōu)路徑[J].吉林大學(xué)學(xué)報(工學(xué)版),2016,46(2):412-417.[PAN Y Y,MA J X,SUN L.Optimal path in dynamic network with random link travel times based on reliability[J].Journal of Jilin University(Engineering and Technology Edition),2016,46(2):412-417.]

[7]XING T,ZHOU X.Finding the most reliable path with and without link travel time correlation:A Lagrangian substitution based approach[J].Transportation Research Part B:Methodological,2011,45(10):1660-1679.