隨機交通網(wǎng)絡最小期望-均方差路徑問題罰函數(shù)解法*

潘義勇，馬健霄

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

隨機交通網(wǎng)絡最小期望-均方差路徑問題罰函數(shù)解法*

潘義勇，馬健霄

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

為了反映交通網(wǎng)絡中考慮可靠性的路徑選擇行為，基于數(shù)學規(guī)劃理論建立隨機交通網(wǎng)絡環(huán)境下最優(yōu)路徑問題的數(shù)學模型并構造罰函數(shù)法求解該約束優(yōu)化問題。首先，在路徑目標函數(shù)中加入了均方差以反映路徑的可靠性，建立隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題的數(shù)學規(guī)劃模型；其次，引入罰函數(shù)和罰因子，把非線性約束優(yōu)化問題轉換為無約束優(yōu)化問題；第三，構造擬牛頓法求解無約束優(yōu)化問題，最終獲得原問題的精確解；最后，針對實際交通網(wǎng)絡開展了數(shù)值實驗并對數(shù)值結果進行了分析。數(shù)值結果表明：提出的算法是能獲得最優(yōu)路徑的精確解。

交通運輸工程；隨機網(wǎng)絡；最優(yōu)路徑；罰函數(shù)；擬牛頓法

0 引 言

交通網(wǎng)絡最優(yōu)路徑問題是車輛導航系統(tǒng)的核心問題[1]。交通網(wǎng)絡最優(yōu)路徑問題的建模有兩個關鍵環(huán)節(jié)，首先是建立能夠準確反映交通網(wǎng)絡耗時隨機特性的網(wǎng)絡模型，通過數(shù)據(jù)采集獲取并擬合網(wǎng)絡模型參數(shù)，實現(xiàn)網(wǎng)絡模型的數(shù)值化計算；其次是在交通網(wǎng)絡模型基礎上建立最優(yōu)路徑模型，選擇合理的路徑目標函數(shù)準確反映實際交通網(wǎng)絡路徑選擇行為。其中，前者發(fā)展已經(jīng)很成熟，隨機網(wǎng)絡[2]指網(wǎng)絡的邊的權值是服從一定概率分布函數(shù)的隨機變量，反映交通網(wǎng)絡行程時間的隨機特性。后者根據(jù)路徑目標函數(shù)所反映的路徑選擇行為主要分為最小期望路徑問題[2]和最可靠路徑問題[3-8]。最小期望路徑問題的目標是尋找起訖點之間的獲得最小期望值的路徑。最小期望路徑問題能反映考慮行程時間隨機性的路徑選擇行為，不能反映考慮可靠性的路徑選擇行為，對于風險規(guī)避的行駛者不僅關注行程時間的節(jié)省而且關注行程時間的可靠性。最可靠路徑問題針對考慮可靠性的路徑選擇行為，為了反映這一點，各種可靠性指標加入到路徑目標函數(shù)中[3-8]，直接的和間接的反映路徑行程時間的可靠性。其中以行程時間期望值與均方差之和最小為路徑目標函數(shù)最能直接反映風險規(guī)避的行駛者對路徑的可靠性的需求，稱為隨機網(wǎng)絡最小期望-均方差路徑問題[6]。

1983年R.W.HALL[5]注意到行駛者常常預留部分時間以應對出行時間的隨機性，行程時間的均值和預留時間之和稱為有效的行程時間。有效的行程時間實際上是隨機行程時間的期望值和均方差的線性組合，反映了該路徑隨機行程時間的可靠性，并以有效的行程時間為路徑目標函數(shù)定義了隨機網(wǎng)絡最可靠路徑問題。同時利用枚舉法求解隨機網(wǎng)絡環(huán)境下最可靠度路徑問題，但是該算法只是理論上的算法，不能應用于實際網(wǎng)絡。2001年S.SEN等[6]以期望值和方差之和為路徑目標函數(shù)，建立了最小期望-方差路徑問題模型，并且利用松弛算法求解了其近似解的集合。但是方差和期望值不在一個量綱上，不能直接反映路徑可靠性。相比較而言，研究的隨機網(wǎng)絡最小期望-均方差路徑問題就能克服這個問題。同時，由于均方差的不可加性和非線性，所以最小期望-均方差路徑問題的求解比最小期望-方差路徑問題要復雜。2011年T.XING等[7]討論了在隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題，構造了拉格朗日松弛算法求解了該問題的解的下界，沒有獲得該問題的精確解。2013年B.Y.CHEN等[8]基于隨機優(yōu)勢理論研究了尋找最小有效行程時間的路徑問題，考慮了隨機變量的相關性[9]，并把該問題推廣到了動態(tài)隨機網(wǎng)絡[10]，但是均假設路徑的行程時間是滿足正態(tài)分布的隨機變量，具有局限性；2015年A.KHANI等[11]給出了最小期望-方差路徑問題和最小期望-均方差路徑問題解之間的關系，并求解了最小期望-均方差路徑問題的上界。

綜上所述，針對隨機交通網(wǎng)絡最小期望-均方差路徑問題的建模已經(jīng)非常完善。由于該問題目標函數(shù)的不可加性和非線性，不能通過基于動態(tài)規(guī)劃的算法求解該問題?，F(xiàn)有研究都是把該問題松弛為動態(tài)規(guī)劃問題求的原問題的近似解，沒有給出原問題的精確解，而這正是本研究的目的。為了反映交通網(wǎng)絡中考慮可靠性的路徑選擇行為，基于數(shù)學規(guī)劃理論建立隨機交通網(wǎng)絡環(huán)境下最優(yōu)路徑問題數(shù)學模型并構造罰函數(shù)法求解該約束優(yōu)化問題。首先，在路徑目標函數(shù)中加入了均方差以反映路徑的可靠性，建立隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題的數(shù)學規(guī)劃模型；其次，引入罰函數(shù)和罰因子，把非線性約束優(yōu)化問題轉換為無約束優(yōu)化問題；第三，構造擬牛頓法求解無約束優(yōu)化問題，最終獲得原問題的精確解；最后，針對實際交通網(wǎng)絡開展了數(shù)值實驗并對數(shù)值結果進行了分析。

1 問題描述與建模

如果利用二進制來表示先驗路徑x∈Kod，可得

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

(1)

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

(2)

(3)

(4)

根據(jù)不同的可靠性指標，隨機網(wǎng)絡環(huán)境下最可靠路徑的定義也是不一樣的，其中以行程時間期望值與均方差之和最小為路徑目標函數(shù)最能直接反映風險規(guī)避的行駛者對路徑的可靠性的需求，筆者定義路徑的目標函數(shù)為期望值與均方差線性之和：

(5)

(6)

采用的期望值-均方差路徑目標函數(shù)為非線性函數(shù)，不具有可加性，這就增加了求解該問題的難度，相對來說，隨機網(wǎng)絡環(huán)境下最小期望-方差路徑問題由于其目標函數(shù)的線性和可加性，求解相對比較容易。下面我們構造罰函數(shù)法求解上述混合非線性整數(shù)約束優(yōu)化問題(6)的精確解。

2 求解算法

本節(jié)設計基于罰函數(shù)的擬牛頓法求解隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題，首先構造罰函數(shù)[12]把混合非線性整數(shù)約束優(yōu)化問題(6)轉化為非線性無約束優(yōu)化問題，再設計擬牛頓法求解該非線性無約束優(yōu)化問題。

2.1 罰函數(shù)

罰函數(shù)法[12]是通過求解一個或多個罰函數(shù)的極小來求解約束優(yōu)化問題的方法，罰函數(shù)法的基本思想就是通過罰函數(shù)把約束優(yōu)化問題轉換為無約束優(yōu)化問題，再對無約束優(yōu)化問題進行求解，其中罰函數(shù)的構造在該方法中起著關鍵作用。下面我們構造問題(6)的罰函數(shù)。

(7)

下面我們要把上述問題轉換為無約束優(yōu)化問題。最優(yōu)化理論中常用方法為罰函數(shù)法，通過罰函數(shù)把優(yōu)化問題中的約束條件轉化為目標函數(shù)，當約束條件滿足時目標函數(shù)最小。針對上述問題(7)定義罰函數(shù)：

(8)

因此通過罰函數(shù)可以把問題(7)轉換為無約束優(yōu)化問題(9)：

minf(x)+γ×g(x)

(9)

其中γ=1/ε≥0為罰因子，當ε→0時，無約束優(yōu)化問題的最優(yōu)解就是原問題的最優(yōu)解。

2.2 擬牛頓法

本節(jié)設計基于迭代算法的擬牛頓法求解無約束優(yōu)化問題(9)，擬牛頓法是求解非線性無約束優(yōu)化問題最有效的方法之一[12]。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標函數(shù)的梯度。通過測量梯度的變化，構造一個目標函數(shù)的模型使之足以產生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對于大規(guī)模的問題。另外，因為擬牛頓法不需要二階導數(shù)的信息，所以有時比牛頓法更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規(guī)模的優(yōu)化問題。

為了求解無約束優(yōu)化問題(9)，擬牛頓法的基本思想是每次迭代xk，使得其趨向于最優(yōu)值點x*，f(xk)+γ×g(xk)隨著k的增大而更接近最優(yōu)值f(x*)+γ×g(x*)，并且近似誤差隨著k的增大而減小， 其每次迭代的公式為

xk+1=xk+akpk，

(10)

(11)

其中:sk=xk+1-xk,yk=▽[f(xk+1)+γ×g(xk+1)]-▽[f(xk)+γ×g(xk)]；當k=0時，Bk取單位矩陣。

ak為滿足以下Wolfe條件[8]的迭代步長：

其中：0

表1 算法1

3 數(shù)值試驗

3.1 小網(wǎng)絡

圖1 隨機網(wǎng)絡Fig. 1 Stochastic network

該隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題建模為下列混合非線性整數(shù)約束優(yōu)化問題：

minf(x)

(12)

其中

(13)

通過構造罰函數(shù)

(14)

上述混合非線性整數(shù)約束優(yōu)化問題轉化為下列無約束優(yōu)化問題：

minf(x)+γ×g(x)

(15)

其中罰因子γ=1×107。

通過MATLAB計算機語言編寫擬牛頓算法Algorithm 1求解上述無約束優(yōu)化問題，并且在Windows-10 (64) 工作站(two 2.00 GHz Xeon CPUs and 4G RAM)條件下運行的，計算獲得的最優(yōu)值點和最優(yōu)值分別為

x=(x12,x13,x23,x25,x34,x46,x54,x56)=(1.0,-0.0,1.0,-0.0,1.0,1.0,0.0,-0.0)

相應的最小期望-均方差路徑為1→2→3→4→6，該路徑的期望值與均方差線性和為54.549 1，具體路徑如圖2。

圖2 最小期望-均方差路徑Fig. 2 Mean-standard deviation shortest path

3.2SiouxFallsnetwork

通過MATLAB計算機語言編寫擬牛頓算法Algorithm 1求解上述無約束優(yōu)化問題，并且在Windows-10 (64) 工作站(two 2.00 GHz Xeon CPUs and 4G RAM)條件下運行的，求得的最優(yōu)路徑如圖4中虛線所示。

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

圖4 最小期望-均方差路徑Fig. 4 Mean-standard deviation shortest path

從以上的計算結果可以得出以下結論：

第一，筆者提出的罰函數(shù)法能夠求解隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題的精確解，獲得確定最優(yōu)路徑和最優(yōu)解，能直接反饋給駕駛員最優(yōu)路徑和行程時間。相比較而言，已有的算法求解都是近似解，獲得的是最優(yōu)路徑的集合和最優(yōu)解的上下界，并且最優(yōu)路徑的集合規(guī)模會隨著問題規(guī)模增大而增大，限制了其在實際路徑導航中的應用。

第二，通過罰函數(shù)把隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題轉化為無約束優(yōu)化問題。當罰因子γ得取值足夠大時，無約束優(yōu)化問題的最優(yōu)解等于原問題的解，兩個問題是等價關系。另一方面，無約束優(yōu)化問題的求解方法已經(jīng)很成熟了，對于大規(guī)模問題都有很好的計算效率。所以筆者提出了求解最小期望-均方差路徑問題很好的一個思路。

第三，通過罰函數(shù)把隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題轉化為無約束優(yōu)化問題。其中無約束優(yōu)化問題的求解算法已經(jīng)研究得很成熟，在優(yōu)化軟件中采用較多，這有利于我們進一步利用現(xiàn)有軟件實現(xiàn)最可靠路徑的導航應用研究。

4 結 語

針對交通網(wǎng)絡的隨機特性以及考慮可靠性的路徑選擇行為，基于混合整數(shù)規(guī)劃建立隨機網(wǎng)絡環(huán)境下最小期望-均方差路徑問題的數(shù)學模型。通過構造罰函數(shù)把上述問題轉化為無約束優(yōu)化問題，構造了基于擬牛頓法的迭代算法求解該無約束優(yōu)化問題。通過對交通網(wǎng)絡的計算驗證了該算法的正確性和可行性。該算法的提出為隨機交通網(wǎng)絡最小期望-均方差路徑問題的解決從數(shù)學規(guī)劃的角度提供了一個好的思路和有效的工具。本研究僅考慮了交通網(wǎng)絡行程時間的隨機特性，沒有考慮其動態(tài)特性，因此把筆者提出的模型推廣到動態(tài)隨機網(wǎng)絡是需要繼續(xù)研究的課題。

[1] FARAHANI R Z, MIANDOABCHI E, SZETO W Y, et al. A review of urban transportation network design problems[J].EuropeanJournalofOperationalResearch, 2013, 229(2)：281-302.

[2] GAO S, CHABINI I. Optimal routing policy problems in stochastic time-dependent networks[J].TransportationResearchPartB：Methodological, 2006, 40(2)：93-122.

[3] 潘義勇, 孫璐. 隨機交通網(wǎng)絡環(huán)境下自適應最可靠路徑問題[J]. 吉林大學學報(工學版), 2014，44(6)：1622-1627.

PAN Yiyong ，SUN Lu. Adaptive reliable shortest path problem in stochastic traffic network[J].JournalofJilinUniversity(EngineeringandTechnologyEdition), 2014，44(6)：1622-1627.

[4] 潘義勇, 馬健霄, 孫璐. 基于可靠度的動態(tài)隨機交通網(wǎng)絡耗時最優(yōu)路徑[J]. 吉林大學學報 (工學版), 2016，46(2)：412-417.

PAN Yiyong，MA Jianxiao, SUN Lu. Optimal path in dynamic network with random link travel times based on reliability[J].JournalofJilinUniversity(EngineeringandTechnologyEdition), 2016，46(2)：412-417.

[5] HALL R W. The fastest path through a network with random time-dependent travel times[J].TransportationScience, 1986, 20(3)：182-188.

[6] SEN S, PILLAI R, JOSHI S, et al. A mean-variance model for route guidance in advanced traveler information systems[J].TransportationScience, 2001, 35(1)：37-49.

[7] XING T, ZHOU X. Finding the most reliable path with and without link travel time correlation：a lagrangian substitution based approach[J].TransportationResearchPartB：Methodological, 2011, 45(10)：1660-1679.

[8] CHEN B Y, LAM W H K, SUMALEE A, et al. Finding reliable shortest paths in road networks under uncertainty[J].NetworksandSpatialEconomics, 2013, 13(2)：123-148.

[9] CHEN B Y, LAM W H K, SUMALEE A, et al. Reliable shortest path finding in stochastic networks with spatial correlated link travel times[J].InternationalJournalofGeographicalInformationScience, 2012, 26(2)：365-386.

[10] CHEN B Y, LAM W H K, SUMALEE A, et al. Reliable shortest path problems in stochastic time-dependent networks[J].JournalofIntelligentTransportationSystems, 2014, 18(2)：177-189.

[11] KHANI A, BOYLES S D. An exact algorithm for the mean-standard deviation shortest path problem[J].TransportationResearchPartB：Methodological, 2015, 81：252-266.

[12] 袁亞湘. 非線性優(yōu)化計算方法[M]. 北京：科學出版社, 2008.

YUAN Yaxiang.NonlinearOptimizationMethod[M]. Beijing：Science Press, 2008.

(責任編輯：朱漢容)

Penalty Function Algorithm for Solving the Mean-Standard Deviation Shortest Path Problem in Stochastic Traffic Network

PAN Yiyong，MA Jianxiao

(College of Automobile and Traffic Engineering, Nanjing Forestry University, Nanjing 210037, Jiangsu, P. R. China)

In order to reflect route choice behavior considering the reliability in traffic network, a mathematic model of shortest path problem in stochastic network was developed based on the mathematical programming and a penalty function algorithm was constructed to solve the constrained optimization problem. Firstly, a mathematical model of mathematical programming was established to reflect the reliable shortest path selection in stochastic network through defining the standard deviation as the part of the objective function; Secondly, the nonlinear constrained optimization problem was transformed into unconstrained optimization problem through introduction of penalty function and penalty factor; Thirdly, a quasi-Newton method is developed to solve the proposed problem; Finally, numerical experiments was carried out on the actual traffic network and the numerical results were analyzed. Numerical results show that the proposed algorithm is able to get exact solution of the optimal path.

traffic and transportation engineering; stochastic network; optimal path; penalty function; quasi-Newton method

10.3969/j.issn.1674-0696.2017.04.17

2016-03-15；

2016-05-18

國家自然科學基金青年基金項目(51508280)；南京林業(yè)大學高學歷人才基金項目(GXL2014031)；江蘇省高等學校大學生創(chuàng)新創(chuàng)業(yè)訓練計劃項目(201610298037Z)

潘義勇(1980—)，男，安徽安慶人，博士，主要從事交通網(wǎng)絡研究方面的研究。E-mail：uoupanyg@163.com。

U491

A

1674-0696(2017)04-096-06