潘義勇 馬健霄

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

基于可靠性的隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑問題

潘義勇 馬健霄

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

為了仿真交通網(wǎng)絡(luò)中資源約束條件下的路徑選擇行為,建立了隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑問題數(shù)學(xué)模型并進(jìn)行求解．采用期望-方差為路徑目標(biāo)函數(shù),將約束最優(yōu)路徑問題建模為混合非線性整數(shù)約束優(yōu)化問題,構(gòu)造基于線性規(guī)劃的分支定界算法以求解該問題．針對Sioux Falls網(wǎng)絡(luò)展開數(shù)值試驗(yàn),將無資源約束和不同資源約束條件下的交通網(wǎng)絡(luò)最優(yōu)路徑計(jì)算結(jié)果進(jìn)行比較分析．試驗(yàn)結(jié)果表明:無資源約束和有資源約束條件下交通網(wǎng)絡(luò)中相同起迄點(diǎn)之間的最優(yōu)值和最優(yōu)路徑是不同的;在不同資源上限的約束條件下,相同起迄點(diǎn)之間的最優(yōu)值和最優(yōu)路徑也是不同的,約束上限值與最優(yōu)值成反比例關(guān)系．交通網(wǎng)絡(luò)中資源約束條件對最優(yōu)路徑的選擇具有重大影響．

智能交通;隨機(jī)網(wǎng)絡(luò);最優(yōu)路徑;資源約束;可靠性;分支定界

交通網(wǎng)絡(luò)耗時(shí)最優(yōu)路徑問題是智能交通系統(tǒng)路徑誘導(dǎo)子系統(tǒng)的核心問題[1]．鑒于行程時(shí)間的隨機(jī)性,通常將該問題轉(zhuǎn)化為隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最優(yōu)路徑問題．但是人們在選擇行程時(shí)間最短路徑的同時(shí)對其他資源是有約束的,例如行車距離、機(jī)動(dòng)車的油耗、電動(dòng)汽車的蓄電能等,因此需對資源約束條件下隨機(jī)交通網(wǎng)絡(luò)最優(yōu)路徑問題展開研究．

約束最優(yōu)路徑問題是運(yùn)籌學(xué)重要研究方向之一．1966年Joksch[2]首次提出了約束最優(yōu)路徑問題,在最優(yōu)路徑問題的基礎(chǔ)上對路徑權(quán)值設(shè)定了一個(gè)上限約束條件,雖然約束最優(yōu)路徑問題比最優(yōu)路徑問題只增加了一些約束條件,但是其求解要復(fù)雜得多,不能直接通過標(biāo)號算法求解．約束最優(yōu)路徑問題主要的求解算法有動(dòng)態(tài)規(guī)劃算法、標(biāo)號設(shè)定算法、拉格朗日松弛算法、分支定界算法以及智能算法等[3]．后續(xù)大部分研究工作集中在此類問題的算法改進(jìn)上,該問題由于其普適性獲得了廣泛應(yīng)用,但是其針對的是確定性網(wǎng)絡(luò),網(wǎng)絡(luò)中邊的權(quán)值是確定值,這種設(shè)定無法反映交通網(wǎng)絡(luò)的耗時(shí)隨機(jī)特性[4-5]．目前,關(guān)于隨機(jī)交通網(wǎng)絡(luò)環(huán)境下最優(yōu)路徑問題的研究較多[6],針對約束最優(yōu)路徑問題的研究則相對較少．Wang等[7]將約束最優(yōu)路徑問題擴(kuò)展到隨機(jī)交通網(wǎng)絡(luò),定義路徑的目標(biāo)函數(shù)為行程時(shí)間的期望值．然而,最小期望值的路徑不能保證方差最小,沒有考慮可靠性,可能該路徑的風(fēng)險(xiǎn)很大,對于風(fēng)險(xiǎn)規(guī)避的行駛者是不可取的．大量實(shí)證研究結(jié)果表明,行駛者不僅關(guān)注行程時(shí)間的節(jié)省,而且關(guān)注行程時(shí)間的可靠性[8-10]．但國內(nèi)外鮮有文獻(xiàn)對基于可靠性的隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最優(yōu)路徑問題及其求解算法展開討論．

本文首先定義了最小期望-方差路徑,以反映路徑行程時(shí)間的可靠性,建立了隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最優(yōu)路徑問題的數(shù)學(xué)模型;然后,構(gòu)造了基于線性規(guī)劃的分支定界算法,以求解該問題;最后,編寫計(jì)算機(jī)算法程序,針對實(shí)際交通網(wǎng)絡(luò)(Sioux Falls網(wǎng)絡(luò))展開數(shù)值試驗(yàn),并對計(jì)算結(jié)果進(jìn)行分析．

1 問題描述與建模

1.1 隨機(jī)交通網(wǎng)絡(luò)

1.2 路徑目標(biāo)函數(shù)

利用二進(jìn)制來表示先驗(yàn)路徑x∈Kod可得

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

(1)

式中,xij=1表示邊(i,j)在先驗(yàn)路徑x上;xij=0表示邊(i,j)不在先驗(yàn)路徑x上．此時(shí),先驗(yàn)路徑x上的行程時(shí)間為

(2)

(3)

(4)

最小期望路徑問題不能反映路徑行程時(shí)間的可靠性．Sen 等[11]和Khani等[12]將路徑目標(biāo)函數(shù)看作期望值和方差的線性組合,考慮了路徑行程時(shí)間的可靠性,定義最優(yōu)路徑為最小期望-方差路徑．方差是用來度量隨機(jī)變量和其期望值之間的偏離程度,期望值最小不能保證該條路徑的方差也最小,極端情況下該條路徑的期望值最小,但是其方差是最大的．將方差加入到目標(biāo)函數(shù)中,可有效控制該偏離程度,在一定程度上反映了該路徑行程時(shí)間的可靠性．參考文獻(xiàn)[11],將路徑目標(biāo)函數(shù)定義為期望值和方差的線性和,即

(5)

式中,λ為可靠性系數(shù),反映了行駛者對風(fēng)險(xiǎn)的容忍程度,與行駛者的置信水平α∈[0,1]有關(guān)系,α>0.5表示風(fēng)險(xiǎn)規(guī)避行為,α=0.5表示風(fēng)險(xiǎn)中性行為,α<0.5表示愿意冒風(fēng)險(xiǎn)行為．在已知行程時(shí)間滿足正態(tài)分布的前提下,λ的理論取值范圍為[0,∞),當(dāng)λ=0時(shí),該問題退化為最小期望路徑問題．

1.3 約束條件

任意路徑x={xij∈{0,1}|(i,j)∈A}必須滿足如下的網(wǎng)絡(luò)平衡條件:

(6)

xij∈{0,1} ?(i,j)∈A

(7)

交通網(wǎng)絡(luò)中行駛者不僅考慮行程時(shí)間,還會受到不同資源的約束,例如對于電動(dòng)汽車,其耗電量為路段資源消耗權(quán)重,因此它的電池總?cè)萘渴瞧滟Y源總消耗的上限值．對于機(jī)動(dòng)車,其碳排放量為路段資源消耗權(quán)重,碳排放總量是其資源總消耗的上限值[13]．

K種資源在任意路徑x={xij∈{0,1}|(i,j)∈A}上總的資源消耗必須小于上限Wk(k=1,2,…,K),即

(8)

1.4 數(shù)學(xué)模型

針對上述路徑目標(biāo)函數(shù)和約束條件,將基于可靠性的隨機(jī)交通網(wǎng)絡(luò)環(huán)境下約束最優(yōu)路徑問題建模為如下的混合非線性整數(shù)約束優(yōu)化問題:

(9)

s.t.

Wang 等[7]提出的隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑模型只考慮將路徑的目標(biāo)函數(shù)作為期望值,沒有考慮路徑行程時(shí)間的可靠性．本文將期望值和方差的線性組合作為路徑目標(biāo)函數(shù),并在其中添加了方差,考慮了路徑行程時(shí)間的可靠性,但是相對于文獻(xiàn)[7]的約束最優(yōu)路徑問題,增加了求解難度．下面將采用分支定界算法來求解混合非線性整數(shù)約束優(yōu)化問題(9)．

2 求解算法

分支定界法是一種求解整數(shù)規(guī)劃問題的最常用算法,不但可以求解純整數(shù)規(guī)劃,還可以求解混合整數(shù)規(guī)劃問題[14]．具體算法步驟如下:

① 將問題(9)的整數(shù)約束(7)松弛為非線性約束,即

0≤xij≤1 ?(i,j)∈A

將問題(9)轉(zhuǎn)化為松弛線性規(guī)劃問題,即

(10)

s.t.

對問題(10)進(jìn)行求解．如果求出的最優(yōu)解是原問題(9)的可行解,那么這個(gè)解就是原問題(9)的最優(yōu)解,計(jì)算結(jié)束．如果求出的最優(yōu)解不是原問題(9)的可行解,例如某一個(gè)xkl不是整數(shù),則轉(zhuǎn)到步驟②,并且這個(gè)解的目標(biāo)函數(shù)值是原問題(9)的最優(yōu)解的下界．

② 將問題(10)分解為2個(gè)子問題,即

(11)

s.t.

(12)

s.t.

對子問題(11)和(12)進(jìn)行求解,比較子問題最優(yōu)解的目標(biāo)函數(shù)值,如果使得目標(biāo)函數(shù)最小的最優(yōu)解是原問題(9)的可行解,則它就是原問題(9)的最優(yōu)解,計(jì)算結(jié)束;否則,其目標(biāo)函數(shù)值是原問題最優(yōu)值的一個(gè)新的下界．另外,在各子問題的最優(yōu)解中,若有原問題(9)的可行解,其最小目標(biāo)函數(shù)值便是原問題最優(yōu)值的上界．

③ 對于最優(yōu)解的目標(biāo)函數(shù)值已大于上界的子問題,其可行解中必?zé)o原問題的最優(yōu)解,可以將這一枝砍去．對于最優(yōu)解的目標(biāo)函數(shù)值小于上界的子問題,都先保留下來．

④ 在保留下的所有子問題中,選出最優(yōu)解的目標(biāo)函數(shù)值中最小的一個(gè),重復(fù)步驟①和步驟②．如果該子問題的最優(yōu)解為原問題(9)的可行解,則將該子問題的最優(yōu)值作為新的上界,重復(fù)步驟③,直到求出最優(yōu)解．

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

圖1 Sioux Falls網(wǎng)絡(luò)

邊μijσ2ij邊μijσ2ij邊μijσ2ij邊μijσ2ij(1,2)3.223.90(8,7)0.481.42(13,24)3.277.23(19,17)5.109.86(1,3)15.168.16(8,9)5.800.25(14,11)13.313.47(19,20)0.410.29(2,1)17.423.17(8,16)6.354.21(14,15)17.886.60(20,18)18.475.35(2,6)7.018.14(9,5)13.071.84(14,23)10.333.83(20,19)13.070.87(3,1)13.717.89(9,8)19.137.25(15,10)14.056.27(20,21)18.658.02(3,4)5.888.52(9,10)18.713.70(15,14)3.070.21(20,22)3.279.89(3,12)10.615.05(10,9)9.158.41(15,19)19.069.10(21,20)18.420.66(4,3)16.646.35(10,11)4.807.34(15,22)10.818.00(21,22)15.899.39(4,5)11.949.50(10,15)15.275.71(16,8)13.597.45(21,24)11.540.18(4,11)6.704.43(10,16)15.181.76(16,10)0.738.13(22,15)8.806.83(5,4)5.980.60(10,17)14.819.57(16,17)16.183.83(22,20)5.157.83(5,6)9.058.66(11,4)14.872.65(16,18)14.976.17(22,21)15.035.34(5,9)8.456.31(11,10)2.119.24(17,10)2.405.75(22,23)4.578.85(6,2)7.193.55(11,12)13.632.23(17,16)10.505.30(23,14)1.288.99(6,5)11.169.97(11,14)9.263.73(17,19)6.512.75(23,22)15.346.25(6,8)14.852.24(12,3)4.240.87(18,7)10.922.48(23,24)13.421.37(7,8)8.486.52(12,11)1.976.40(18,16)7.974.51(24,13)14.302.17(7,18)8.586.04(12,13)16.471.80(18,20)8.302.27(24,21)12.841.82(8,6)2.493.87(13,12)3.500.45(19,15)3.618.04(24,23)8.380.41

在資源總量W=40的約束條件下,不同起迄點(diǎn)之間的資源消耗、最優(yōu)路徑和最優(yōu)值見表3．不同資源總量約束條件下,起迄點(diǎn)13—8以及起迄點(diǎn)2—23之間的資源消耗、最優(yōu)路徑和最優(yōu)值分別見表4和表5．

由表4可知,W=15,20,25,30時(shí),起迄點(diǎn)13—8之間的最優(yōu)路徑是不同的．由表5可知,起迄點(diǎn)2—23之間的最優(yōu)路徑是不同的．由此可以看出,在不同的資源總量上限約束條件下,相同起迄點(diǎn)之間的最優(yōu)路徑是不同的,并且隨著約束資源總量上限的增加,最優(yōu)值逐漸減少,約束資源總量上限與最優(yōu)值成反比關(guān)系．有約束和無約束條件下的隨機(jī)交通網(wǎng)絡(luò)環(huán)境中最優(yōu)路徑問題具有根本性的不同,且無約束條件下的最優(yōu)值要比有約束條件下的最優(yōu)值小,約束條件對路徑的選擇具有重大影響,這符合實(shí)際交通網(wǎng)絡(luò)中最可靠路徑選擇情況．

在資源總量上限約束條件下,可靠性系數(shù)對最優(yōu)路徑的選擇也是有影響的．當(dāng)可靠性系數(shù)取值不同時(shí),其獲得的最優(yōu)路徑不同．這表明在實(shí)際交通網(wǎng)絡(luò)中由于不同的風(fēng)險(xiǎn)規(guī)避可能性,駕駛員選擇的路徑也是不同的．

表2 資源消耗wij的取值

表3 不同起迄點(diǎn)之間的最優(yōu)路徑和最優(yōu)值(W=40)

表4不同資源上限約束條件下起訖點(diǎn)13—8之間的最優(yōu)路徑和最優(yōu)值

W總資源消耗最優(yōu)值最優(yōu)路徑10無解無解無解1512.8190.0913—24—21—20—19—17—16—82019.2585.4013—24—21—20—18—16—82524.0446.5013—12—11—10—16—83024.0446.5013—12—11—10—16—8

表5不同資源上限約束條件下起訖點(diǎn)2—23之間的最優(yōu)路徑和最優(yōu)值

W總資源消耗最優(yōu)值最優(yōu)路徑20無解無解無解3029.8668.412—6—8—16—10—11—14—233533.1262.642—6—8—7—18—20—22—234033.1262.642—6—8—7—18—20—22—23

由表3可知,在資源總量上限的約束條件下,不同起迄點(diǎn)之間的資源消耗、最優(yōu)路徑和最優(yōu)值均不同,但是在獲得最優(yōu)路徑的同時(shí)資源消耗不會超過其上限約束,證明本文提出的算法是有效的．然而,也會出現(xiàn)無解的情況,究其原因在于,當(dāng)資源約束上限比較小時(shí),起迄點(diǎn)之間找不到滿足約束條件的路徑,這符合實(shí)際交通網(wǎng)絡(luò)中最可靠路徑選擇情況．

本文提出的基于線性規(guī)劃的分支定界法能夠求解隨機(jī)網(wǎng)絡(luò)環(huán)境下約束最小期望-方差路徑問題的精確解,獲得確定的最優(yōu)路徑和最優(yōu)解,能夠直接反饋給駕駛員最優(yōu)路徑和行程時(shí)間．

4 結(jié)論

1) 本文建立的隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑模型同時(shí)考慮了資源約束條件、行程時(shí)間的隨機(jī)特性和路徑可靠性,能較好地仿真交通網(wǎng)絡(luò)中資源約束條件下的路徑選擇行為,較全面地反映了實(shí)際路徑選擇情況．

2) 本文構(gòu)造的基于線性規(guī)劃的分支定界法是求解隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑問題的有效算法,能獲得交通網(wǎng)絡(luò)中資源約束條件下的交通網(wǎng)絡(luò)車輛最優(yōu)路徑．

3) 交通網(wǎng)絡(luò)中資源約束條件對最優(yōu)路徑的選擇具有重大影響．無資源和有資源約束條件下交通網(wǎng)絡(luò)中相同起迄點(diǎn)之間的最優(yōu)值和最優(yōu)路徑是不同的．在不同的資源上限約束條件下,相同起迄點(diǎn)之間的最優(yōu)值和最優(yōu)路徑也是不同的,約束上限值與最優(yōu)值成反比關(guān)系．

4) 本文假設(shè)隨機(jī)網(wǎng)絡(luò)中邊的隨機(jī)變量之間是相互獨(dú)立的,沒有考慮隨機(jī)變量的相關(guān)性,下一步需要對考慮相關(guān)性的隨機(jī)網(wǎng)絡(luò)環(huán)境下約束最優(yōu)路徑問題進(jìn)行進(jìn)一步研究．

)

[1] Schrank D, Eisele B, Lomax T. TTI’s 2012 urban mobility report [EB/OL]. (2012-08-01) [2016-07-10].http://www.pagregion.com/Portals/0/documents/HumanServices/2012MobilityReport.pdf.

[2] Joksch H C. The shortest route problem with constraints[J].JournalofMathematicalAnalysisandApplications, 1966,14(2): 191-197. DOI:10.1016/0022-247x(66)90020-5.

[3] Avella P, Boccia M, Sforza A. A penalty function heuristic for the resource constrained shortest path problem[J].EuropeanJournalofOperationalResearch, 2002,142(2): 221-230. DOI:10.1016/s0377-2217(02)00262-x.

[4] 潘義勇, 余婷, 馬健霄. 基于路段與節(jié)點(diǎn)的城市道路阻抗函數(shù)改進(jìn)[J]. 重慶交通大學(xué)學(xué)報(bào) (自然科學(xué)版), 2017, 36(8): 76-81. DOI: 10.3969/j.issn.1674-0696.2017.08.14.

Pan Yiyong, Yu Ting, Ma Jianxiao. Improvement of urban road impedance function based on section impedance and node impedance[J].JournalofChongqingJiaotongUniversity(NaturalScience), 2017,36(8): 76-81. DOI: 10.3969/j.issn.1674-0696.2017.08.14. (in Chinese)

[5] Pan Yiyong, Sun Lu. Characterizing heterogeneity in vehicular traffic speed using two-step cluster analysis[J].JournalofSoutheastUniversity(EnglishEdition), 2012,28(4):480-484. DOI: 10.3969/j.issn.1003-7985.2012.04.019.

[6] 潘義勇. 動(dòng)態(tài)隨機(jī)交通網(wǎng)絡(luò)環(huán)境下耗時(shí)最可靠路徑研究[D]. 南京:東南大學(xué)交通學(xué)院, 2014.

[7] Wang L, Yang L, Gao Z. The constrained shortest path problem with stochastic correlated link travel times[J].EuropeanJournalofOperationalResearch, 2016,255(1): 43-57. DOI:10.1016/j.ejor.2016.05.040.

[8] Wu X, Nie Y. Modeling heterogeneous risk-taking behavior in route choice: A stochastic dominance approach[J].TransportationResearchPartA:PolicyandPractice, 2011,45(9): 896-915. DOI:10.1016/j.tra.2011.04.009.

[9] 潘義勇, 孫璐. 隨機(jī)交通網(wǎng)絡(luò)環(huán)境下自適應(yīng)最可靠路徑問題[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版), 2014, 44(6): 1622-1627. DOI:10.13229/j.cnki.jdxbgxb201406014.

Pan Yiyong, Sun Lu. Adaptive reliable shortest path problem in stochastic traffic network[J].JournalofJilinUniversity(EngineeringandTechnologyEdition), 2014,44(6): 1622-1627. DOI:10.13229/j.cnki.jdxbgxb201406014.(in Chinese)

[10] 潘義勇, 馬健霄, 孫璐. 基于可靠度的動(dòng)態(tài)隨機(jī)交通網(wǎng)絡(luò)耗時(shí)最優(yōu)路徑[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版), 2016, 46(2): 412-417. DOI:10.13229/j.cnki.jdxbgxb201602012.

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. DOI:10.13229/j.cnki.jdxbgxb201602012.(in Chinese)

[11] 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. DOI:10.1287/trsc.35.1.37.10141.

[12] Khani A, Boyles S D. An exact algorithm for the mean-standard deviation shortest path problem[J].TransportationResearchPartB:Methodological, 2015,81: 252-266. DOI:10.1016/j.trb.2015.04.002.

[13] Li W, Yang L, Wang L, et al. Eco-reliable path finding in time-variant and stochastic networks[J].Energy, 2017,121: 372-387. DOI:10.1016/j.energy.2017.01.008.

[14] Hillier F S.Introductiontooperationsresearch[M]. New York:Tata McGraw-Hill Education, 2012:125-156.

[15] Bar-Gera H. Transportation network test problems[EB/OL]. (2013-08-01)[2016-07-10]. http://www. bgu. ac. il/bargera/tntp.

Constrainedshortestpathprobleminstochastictrafficnetworkbasedonreliability

Pan Yiyong Ma Jianxiao

(College of Automobile and Traffic Engineering, Nanjing Forestry University, Nanjing 210037, China)

To simulate the behavior of the path choice under the resource constraints in the traffic network, the mathematical model of the constrained shortest path problem in the stochastic traffic network is established and solved. The mean-variance is defined as the objective function of the path. The constrained shortest path problem is modeled as a nonlinear mixed integer constrained optimization problem and solved by the proposed branch-and-bound algorithm based on linear programming. Numerical experiments in the Sioux Falls network are carried out, and the calculation results of the constrained shortest path without resource constraint and with different resource constraints are compared and analyzed. The experimental results show that the optimal values and the shortest paths obtained without resource constraints and with resource constraints are different. The optimal values and the shortest paths obtained with different resource constraints are also different, and the upper value of the resource constraints is in inverse proportion to the optimal value. The resource constraints have a great influence on the choice of the optimal path in the traffic network.

intelligent transportation; stochastic network; optimal path; resource constraint; reliability; branch-and-bound

10.3969/j.issn.1001-0505.2017.06.028

U491

A

1001-0505(2017)06-1263-06

2017-04-08.

潘義勇(1980—),男,博士,講師,uoupanyg@163.com.

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

潘義勇,馬健霄.基于可靠性的隨機(jī)交通網(wǎng)絡(luò)約束最優(yōu)路徑問題[J].東南大學(xué)學(xué)報(bào)(自然科學(xué)版),2017,47(6):1263-1268.

10.3969/j.issn.1001-0505.2017.06.028.