基于可靠性的随机交通网络约束最优路径问题

潘义勇 马健霄

(南京林业大学汽车与交通工程学院, 南京 210037)

基于可靠性的随机交通网络约束最优路径问题

潘义勇 马健霄

(南京林业大学汽车与交通工程学院, 南京 210037)

为了仿真交通网络中资源约束条件下的路径选择行为,建立了随机交通网络约束最优路径问题数学模型并进行求解．采用期望-方差为路径目标函数,将约束最优路径问题建模为混合非线性整数约束优化问题,构造基于线性规划的分支定界算法以求解该问题．针对Sioux Falls网络展开数值试验,将无资源约束和不同资源约束条件下的交通网络最优路径计算结果进行比较分析．试验结果表明:无资源约束和有资源约束条件下交通网络中相同起迄点之间的最优值和最优路径是不同的;在不同资源上限的约束条件下,相同起迄点之间的最优值和最优路径也是不同的,约束上限值与最优值成反比例关系．交通网络中资源约束条件对最优路径的选择具有重大影响．

智能交通;随机网络;最优路径;资源约束;可靠性;分支定界

交通网络耗时最优路径问题是智能交通系统路径诱导子系统的核心问题[1]．鉴于行程时间的随机性,通常将该问题转化为随机交通网络环境下最优路径问题．但是人们在选择行程时间最短路径的同时对其他资源是有约束的,例如行车距离、机动车的油耗、电动汽车的蓄电能等,因此需对资源约束条件下随机交通网络最优路径问题展开研究．

约束最优路径问题是运筹学重要研究方向之一．1966年Joksch[2]首次提出了约束最优路径问题,在最优路径问题的基础上对路径权值设定了一个上限约束条件,虽然约束最优路径问题比最优路径问题只增加了一些约束条件,但是其求解要复杂得多,不能直接通过标号算法求解．约束最优路径问题主要的求解算法有动态规划算法、标号设定算法、拉格朗日松弛算法、分支定界算法以及智能算法等[3]．后续大部分研究工作集中在此类问题的算法改进上,该问题由于其普适性获得了广泛应用,但是其针对的是确定性网络,网络中边的权值是确定值,这种设定无法反映交通网络的耗时随机特性[4-5]．目前,关于随机交通网络环境下最优路径问题的研究较多[6],针对约束最优路径问题的研究则相对较少．Wang等[7]将约束最优路径问题扩展到随机交通网络,定义路径的目标函数为行程时间的期望值．然而,最小期望值的路径不能保证方差最小,没有考虑可靠性,可能该路径的风险很大,对于风险规避的行驶者是不可取的．大量实证研究结果表明,行驶者不仅关注行程时间的节省,而且关注行程时间的可靠性[8-10]．但国内外鲜有文献对基于可靠性的随机交通网络环境下约束最优路径问题及其求解算法展开讨论．

本文首先定义了最小期望-方差路径,以反映路径行程时间的可靠性,建立了随机交通网络环境下约束最优路径问题的数学模型;然后,构造了基于线性规划的分支定界算法,以求解该问题;最后,编写计算机算法程序,针对实际交通网络(Sioux Falls网络)展开数值试验,并对计算结果进行分析．

1 问题描述与建模

1.1 随机交通网络

1.2 路径目标函数

利用二进制来表示先验路径x∈Kod可得

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

(1)

式中,xij=1表示边(i,j)在先验路径x上;xij=0表示边(i,j)不在先验路径x上．此时,先验路径x上的行程时间为

(2)

(3)

(4)

最小期望路径问题不能反映路径行程时间的可靠性．Sen 等[11]和Khani等[12]将路径目标函数看作期望值和方差的线性组合,考虑了路径行程时间的可靠性,定义最优路径为最小期望-方差路径．方差是用来度量随机变量和其期望值之间的偏离程度,期望值最小不能保证该条路径的方差也最小,极端情况下该条路径的期望值最小,但是其方差是最大的．将方差加入到目标函数中,可有效控制该偏离程度,在一定程度上反映了该路径行程时间的可靠性．参考文献[11],将路径目标函数定义为期望值和方差的线性和,即

(5)

式中,λ为可靠性系数,反映了行驶者对风险的容忍程度,与行驶者的置信水平α∈[0,1]有关系,α>0.5表示风险规避行为,α=0.5表示风险中性行为,α<0.5表示愿意冒风险行为．在已知行程时间满足正态分布的前提下,λ的理论取值范围为[0,∞),当λ=0时,该问题退化为最小期望路径问题．

1.3 约束条件

任意路径x={xij∈{0,1}|(i,j)∈A}必须满足如下的网络平衡条件:

(6)

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

(7)

交通网络中行驶者不仅考虑行程时间,还会受到不同资源的约束,例如对于电动汽车,其耗电量为路段资源消耗权重,因此它的电池总容量是其资源总消耗的上限值．对于机动车,其碳排放量为路段资源消耗权重,碳排放总量是其资源总消耗的上限值[13]．

K种资源在任意路径x={xij∈{0,1}|(i,j)∈A}上总的资源消耗必须小于上限Wk(k=1,2,…,K),即

(8)

1.4 数学模型

针对上述路径目标函数和约束条件,将基于可靠性的随机交通网络环境下约束最优路径问题建模为如下的混合非线性整数约束优化问题:

(9)

s.t.

Wang 等[7]提出的随机交通网络约束最优路径模型只考虑将路径的目标函数作为期望值,没有考虑路径行程时间的可靠性．本文将期望值和方差的线性组合作为路径目标函数,并在其中添加了方差,考虑了路径行程时间的可靠性,但是相对于文献[7]的约束最优路径问题,增加了求解难度．下面将采用分支定界算法来求解混合非线性整数约束优化问题(9)．

2 求解算法

分支定界法是一种求解整数规划问题的最常用算法,不但可以求解纯整数规划,还可以求解混合整数规划问题[14]．具体算法步骤如下:

① 将问题(9)的整数约束(7)松弛为非线性约束,即

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

将问题(9)转化为松弛线性规划问题,即

(10)

s.t.

对问题(10)进行求解．如果求出的最优解是原问题(9)的可行解,那么这个解就是原问题(9)的最优解,计算结束．如果求出的最优解不是原问题(9)的可行解,例如某一个xkl不是整数,则转到步骤②,并且这个解的目标函数值是原问题(9)的最优解的下界．

② 将问题(10)分解为2个子问题,即

(11)

s.t.

(12)

s.t.

对子问题(11)和(12)进行求解,比较子问题最优解的目标函数值,如果使得目标函数最小的最优解是原问题(9)的可行解,则它就是原问题(9)的最优解,计算结束;否则,其目标函数值是原问题最优值的一个新的下界．另外,在各子问题的最优解中,若有原问题(9)的可行解,其最小目标函数值便是原问题最优值的上界．

③ 对于最优解的目标函数值已大于上界的子问题,其可行解中必无原问题的最优解,可以将这一枝砍去．对于最优解的目标函数值小于上界的子问题,都先保留下来．

④ 在保留下的所有子问题中,选出最优解的目标函数值中最小的一个,重复步骤①和步骤②．如果该子问题的最优解为原问题(9)的可行解,则将该子问题的最优值作为新的上界,重复步骤③,直到求出最优解．

3 数值试验

图1 Sioux Falls网络

边μ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的约束条件下,不同起迄点之间的资源消耗、最优路径和最优值见表3．不同资源总量约束条件下,起迄点13—8以及起迄点2—23之间的资源消耗、最优路径和最优值分别见表4和表5．

由表4可知,W=15,20,25,30时,起迄点13—8之间的最优路径是不同的．由表5可知,起迄点2—23之间的最优路径是不同的．由此可以看出,在不同的资源总量上限约束条件下,相同起迄点之间的最优路径是不同的,并且随着约束资源总量上限的增加,最优值逐渐减少,约束资源总量上限与最优值成反比关系．有约束和无约束条件下的随机交通网络环境中最优路径问题具有根本性的不同,且无约束条件下的最优值要比有约束条件下的最优值小,约束条件对路径的选择具有重大影响,这符合实际交通网络中最可靠路径选择情况．

在资源总量上限约束条件下,可靠性系数对最优路径的选择也是有影响的．当可靠性系数取值不同时,其获得的最优路径不同．这表明在实际交通网络中由于不同的风险规避可能性,驾驶员选择的路径也是不同的．

表2 资源消耗wij的取值

表3 不同起迄点之间的最优路径和最优值(W=40)

表4不同资源上限约束条件下起讫点13—8之间的最优路径和最优值

W总资源消耗最优值最优路径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不同资源上限约束条件下起讫点2—23之间的最优路径和最优值

W总资源消耗最优值最优路径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可知,在资源总量上限的约束条件下,不同起迄点之间的资源消耗、最优路径和最优值均不同,但是在获得最优路径的同时资源消耗不会超过其上限约束,证明本文提出的算法是有效的．然而,也会出现无解的情况,究其原因在于,当资源约束上限比较小时,起迄点之间找不到满足约束条件的路径,这符合实际交通网络中最可靠路径选择情况．

本文提出的基于线性规划的分支定界法能够求解随机网络环境下约束最小期望-方差路径问题的精确解,获得确定的最优路径和最优解,能够直接反馈给驾驶员最优路径和行程时间．

4 结论

1) 本文建立的随机交通网络约束最优路径模型同时考虑了资源约束条件、行程时间的随机特性和路径可靠性,能较好地仿真交通网络中资源约束条件下的路径选择行为,较全面地反映了实际路径选择情况．

2) 本文构造的基于线性规划的分支定界法是求解随机交通网络约束最优路径问题的有效算法,能获得交通网络中资源约束条件下的交通网络车辆最优路径．

3) 交通网络中资源约束条件对最优路径的选择具有重大影响．无资源和有资源约束条件下交通网络中相同起迄点之间的最优值和最优路径是不同的．在不同的资源上限约束条件下,相同起迄点之间的最优值和最优路径也是不同的,约束上限值与最优值成反比关系．

4) 本文假设随机网络中边的随机变量之间是相互独立的,没有考虑随机变量的相关性,下一步需要对考虑相关性的随机网络环境下约束最优路径问题进行进一步研究．

)

[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] 潘义勇, 余婷, 马健霄. 基于路段与节点的城市道路阻抗函数改进[J]. 重庆交通大学学报 (自然科学版), 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]. 南京:东南大学交通学院, 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]. 吉林大学学报(工学版), 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] 潘义勇, 马健霄, 孙璐. 基于可靠度的动态随机交通网络耗时最优路径[J]. 吉林大学学报(工学版), 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.

国家自然科学基金青年科学基金资助项目(51508280)、江苏省高等学校大学生创新创业训练计划资助项目(201610298037Z)、南京林业大学高学历人才基金资助项目(GXL2014031).

潘义勇,马健霄.基于可靠性的随机交通网络约束最优路径问题[J].东南大学学报(自然科学版),2017,47(6):1263-1268.

10.3969/j.issn.1001-0505.2017.06.028.