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

潘義勇，馬健霄

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

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

潘義勇，馬健霄

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

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

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

0 引 言

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

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

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

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

(5)

(6)

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

2 求解算法

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

2.1 罰函數(shù)

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

(7)

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

(8)

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

minf(x)+γ×g(x)

(9)

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

2.2 擬牛頓法

本節(jié)設(shè)計基于迭代算法的擬牛頓法求解無約束優(yōu)化問題(9)，擬牛頓法是求解非線性無約束優(yōu)化問題最有效的方法之一[12]。擬牛頓法和最速下降法一樣只要求每一步迭代時知道目標(biāo)函數(shù)的梯度。通過測量梯度的變化，構(gòu)造一個目標(biāo)函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這類方法大大優(yōu)于最速下降法，尤其對于大規(guī)模的問題。另外，因為擬牛頓法不需要二階導(dǎo)數(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)]；當(dāng)k=0時，Bk取單位矩陣。

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

其中：0

表1 算法1

3 數(shù)值試驗

3.1 小網(wǎng)絡(luò)

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

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

minf(x)

(12)

其中

(13)

通過構(gòu)造罰函數(shù)

(14)

上述混合非線性整數(shù)約束優(yōu)化問題轉(zhuǎn)化為下列無約束優(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)

相應(yīng)的最小期望-均方差路徑為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)絡(luò)Fig. 3 Sioux Falls network

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

從以上的計算結(jié)果可以得出以下結(jié)論：

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

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

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

4 結(jié) 語

針對交通網(wǎng)絡(luò)的隨機特性以及考慮可靠性的路徑選擇行為，基于混合整數(shù)規(guī)劃建立隨機網(wǎng)絡(luò)環(huán)境下最小期望-均方差路徑問題的數(shù)學(xué)模型。通過構(gòu)造罰函數(shù)把上述問題轉(zhuǎn)化為無約束優(yōu)化問題，構(gòu)造了基于擬牛頓法的迭代算法求解該無約束優(yōu)化問題。通過對交通網(wǎng)絡(luò)的計算驗證了該算法的正確性和可行性。該算法的提出為隨機交通網(wǎng)絡(luò)最小期望-均方差路徑問題的解決從數(shù)學(xué)規(guī)劃的角度提供了一個好的思路和有效的工具。本研究僅考慮了交通網(wǎng)絡(luò)行程時間的隨機特性，沒有考慮其動態(tài)特性，因此把筆者提出的模型推廣到動態(tài)隨機網(wǎng)絡(luò)是需要繼續(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)絡(luò)環(huán)境下自適應(yīng)最可靠路徑問題[J]. 吉林大學(xué)學(xué)報(工學(xué)版), 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)絡(luò)耗時最優(yōu)路徑[J]. 吉林大學(xué)學(xué)報 (工學(xué)版), 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]. 北京：科學(xué)出版社, 2008.

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

(責(zé)任編輯：朱漢容)

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

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

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

U491

A

1674-0696(2017)04-096-06