基于部分随机用户均衡的可变信息板选址双层规划模型
2017-01-03覃文文
覃文文
(同济大学 道路与交通工程教育部重点实验室，上海 201804)
基于部分随机用户均衡的可变信息板选址双层规划模型
覃文文
(同济大学 道路与交通工程教育部重点实验室，上海 201804)
为了准确描述随机需求与随机供给对可变信息板选址带来的不确定影响，用蒙特卡罗模拟技术来刻画路网状态的随机性，考虑出行者对可变信息板信息发布的不同诱导服从程度，建立了多目标优化的VMS选址双层规划模型。上层模型为VMS影响区域信息熵、路网总行程时间均值与标准差加权和最小的双目标函数，用于求解随机环境下VMS的选址方案，下层模型为部分随机用户均衡分配模型，用于分析VMS诱导下出行者的路径复杂选择行为。采用非劣排序遗传算法-II求解模型，并以一个简单网络进行了算例分析。计算结果表明：非劣排序遗传算法-II能够有效求解VMS选址的多目标优化问题，平均得到5组Pareto解;在部署VMS后，全路网的平均行程时间最大可由0.54 h下降至0.486 h；出行者的诱导服从率从20%增大到60%时，VMS的诱导效益呈上升趋势；随着诱导服从率接近100%，VMS对路网运行质量的改善作用呈下降趋势，并可能出现比不发布诱导信息还差的局面。
交通工程；可变信息板选址；非劣排序遗传算法-II；多目标优化；蒙特卡罗模拟
0 引言
VMS作为一种群体式的交通流诱导信息发布系统，其布局和信息发布对出行质量起着关键性的影响，合理布设VMS具有重要意义[1]。目前，VMS诱导下的路径选择行为一直是学术界广泛关注的热点。钟石泉等[2]研究了图形VMS发布路况信息下不同因素对驾驶员诱导服从行为的影响。徐天东等[3]基于实时交通数据，利用经验分析法与probit模型量化了不同VMS信息内容对驾驶员在途转移行为的影响。尚华艳等[4]采用元胞传输模型分析了路径选择概率变化与VMS位置之间的关系。姜桂艳等[5]应用仿真模拟方法，探讨了拥挤条件下VMS发布诱导信息对驾驶行为的影响。上述研究多为VMS布局已知，在小范围路网内对VMS诱导下的路径选择行为进行建模仿真，较少关注VMS选址问题，特别是考虑交通系统对VMS选址建模的不确定性影响。Chiu等[6]假定所有出行者拥有完全信息，能预期其他出行者路径选择行为，建立了上层为最大化信息发布收益的VMS最优布点、下层为用户动态最优的交通分配模型。该模型涉及多个VMS候选方案的评估，计算量过大，难以应用于大规模城市路网。随后，Chiu等[7]进一步考虑了随机事故与ATIS共存情况下的动态VMS最优选址问题，发现同时部署VMS与ATIS比相继安装两个系统效益更好。上述研究主要考虑突发事故影响下的VMS布局优化，考虑因素较为单一，未能将交通系统的不确定性作为一个整体纳入VMS选址模型中，以更好地切合实际情况。
综上分析，VMS选址方案是在一个不确定性的路网环境中进行VMS的最佳布局，而这种不确定性主要体现在：(1)交通需求的不确定性，即用户出行的随机性；(2)道路交通状态的不确定性，如路段突发交通事故等；(3)认知的不确定性，即VMS信息发布的不完全和出行者对信息的认知偏差，导致出行者做出违背信息诱导的路径选择行为。本文从以上3个层面，引入信息论中熵的概念，通过部署VMS，以信息熵衡量VMS消除影响区域内的不确定性程度，使用行程时间的期望和标准差量化不确定决策中的风险，基于部分随机用户平衡描述VMS诱导下的出行者路径选择行为，建立VMS选址规划模型，并设计模型的求解算法。
1 问题描述
在整个路网中，只有VMS影响的区域为信息透明的区域，出行者能够通过VMS发布的信息准确了解前方局部路网的交通状况，并决定是否响应VMS的信息诱导，做出符合自身利益的路径选择。可在Logit模型的基础上，建立VMS诱导下的出行者信息响应模型来描述诱导服从率对于出行者路径选择行为的影响。而在VMS影响之外的区域路网，则为没有信息指引的区域，出行者只能根据行车经验、习惯性等因素进行路径选择，此时，可采用Logit模型来描述路网上的随机行为。
2 模型构建
2.2 信息熵的估计
研究表明，VMS的收益不仅体现在缩短行程时间上，对减少交通状况的不确定性也有突出贡献[8]。因此，考虑到城市交通网络处于一个随机干扰环境中，路段的交通状态具有不确定性与实时性，本文将利用信息熵衡量影响区域内VMS消除的不确定性程度，即局部路网产生的信息熵越大，越需要部署VMS消除路段交通状态的不确定性。基于以上思路，定义VMS覆盖的路段为有效影响路段，VMS影响区域信息熵的估计公式为：
(1)
考虑4种路段交通情景的集合Λ={λ1=顺畅(V/C≤0.6)；λ2=稍有拥堵(0.6
Step 1：初始化。确定OD需求概率分布函数和路段通行能力概率分布函数。
Step 2：令抽样次数t=1。
Step 3：随机生成本轮OD需求量和路段通行能力值。
Step 6：如果t小于抽样规模T，则t=t+1；返回Step 3。
2.3 VMS诱导下的路径选择模型
文献[9-10]以诱导交通量最大化为目标研究了VMS选址问题，但未能将VMS诱导下的路径选择行为纳入选址模型中进行集成分析，这就使得选址方案与出行者之间缺乏反馈机制。交通管理者做出选址方案决策，其结果能够影响并引导交通流分布到交通负荷水平较低的道路，但不能直接决定路网中的出行者都服从信息诱导；反过来，出行者可选择是否对VMS发布的信息做出响应，改变自己原有的出行路径，这将直接关系到VMS选址方案的实施能否获得良好的收益，并对交通管理者的决策产生一定影响。因此，VMS选址模型的建立要考虑出行者的诱导服从行为。
根据上述讨论，设u为VMS影响区域内出行的起点，V为VMS影响区域内出行终点的集合，Kuv为起点u与讫点v之间的路径集合。在VMS影响区域建立出行者信息响应模型，引入诱导服从率E∈[0,1]来表征出行者信息响应特性，E为0或1时表示所有出行者都会忽略或服从VMS的信息诱导。具体模型如下：
(2)
(3)
2.4 VMS选址双层规划模型
VMS选址方案的决策过程是典型的领导者-跟随者双层规划问题，交通管理者对城市路网部署VMS后，驾驶员根据VMS发布的前方路况信息，结合自身经验与利益，选择出行路径。在VMS选址的双层规划模型中，上层模型从领导者的角度出发，提出布局方案，下层模型从跟随者的角度出发，调整出行行为；上层模型再根据下层模型反馈的信息，做出符合全局最优的决策，模型结构见图1。
图1 模型结构Fig.1 Model structure
2.4.1 上层模型
考虑到随机需求强度和随机通行能力下降对VMS选址结果造成的较大差异，决策者也将面临很大的决策风险。为了降低选址方案对不确定性的敏感度，采用行程时间的期望和标准差量化不确定决策中的风险，希望模型处理不确定性的风险值最小，以提高模型鲁棒性。上层模型包含两个目标函数：一个是最小化VMS影响区域产生的信息熵；另一个是最小化所有需求与供给情景发生下的路网总行程时间均值和标准差。具体模型如下。
(4)
(5)
(6)
Zij={0,1},(i,j)∈A,
(7)
(8)
(9)
2.4.2 下层模型
下层模型为部分随机用户均衡模型[12]。在VMS影响区域内，部分随机用户均衡是指服从信息诱导的出行者能够调整原有路径选择行为，其他出行者则保持原有的路径选择行为，实现新的随机用户均衡；而VMS影响区域之外，则仍然遵循基于Logit的随机用户均衡模型[12]。具体模型如下。
(10)
(11)
(12)
(i, j)∈A, ω∈Ω，
(13)
3 模型求解算法
针对多目标优化的VMS选址问题，最佳方法是求得问题的Pareto解集，然后根据决策人的偏好程度从Pareto解集中选择其中一组解作为解决方案[13]。因此，采用基于Monte Carlo模拟的NSGA-II算法[13]求解双层规划模型，对于下层模型，首先根据文献[15]确定交通网络中任意OD对之间的有效路径集，然后基于Dial算法的基本框架，设计考虑VMS诱导的流量加载算法，并将此算法嵌入相继平均法(Method of Successive Averages,MSA)中，用于求解下层模型的随机交通分配问题。
3.1 下层模型求解
3.1.1 VMS诱导下的流量加载算法
原有的Dial算法需要进行起讫点间的正反两次最短路径搜索，计算过程较为复杂。因此，基于Dial算法的基本框架，设计了能反映VMS诱导下的出行者路径选择行为的流量加载算法。定义s()为相应节点到终点s的最小阻抗，具体算法过程如下。
Step 1：初始化。对OD对r-s之间属于有效路径的路段进行标号处理，用lij=1表示；lij=0则表示该路段不属于有效路径的路段。
Step 2：对于每个路段(i,j)，按式(14)计算路段似然值，其中tij为路段(i,j)的行程时间。
(14)
Step 3：从终点s开始逆序计算路段权重W(i,j)，当j到达起点r时，停止权重计算。其中定义downi为路段起点为i的路段终点集合(即为i所有的下游节点集合)，具体计算公式为：
(15)
Step 4：从起点r开始顺序计算i节点到下游各相邻节点j选择路段(i, j)的概率P(i, j)：
(16)
(17)
Step6：VMS影响区域内的流量加载。采用式(2)～(3)对VMS影响区域内的路段流量进行重新分配。且有：
(18)
不难看出，上述算法首先实现的是正向路段流量加载的Dial算法，之后在VMS影响区域内嵌入出行者信息响应模型，重新调整影响区域内的流量，从而真正实现了静态网络中考虑VMS诱导的出行者路径选择行为的流量加载算法。
3.1.2 VMS诱导下的MSA算法
为了求解考虑拥挤效应的用户均衡随机配流问题，可运用MSA算法实现路段出行时间为随机变量的交通分配。算法的具体步骤如下。
Step 4：计算各路段的交通量：
(19)
Step 5：收敛性检查。若满足式(20)的收敛准则，算法终止，其中ε为预先给定的收敛精度参数；否则令n=n+1，并转至Step 2。
(20)
3.2 双层模型求解
由资金约束条件(6)生成VMS初始可行解集，代入部分随机用户均衡配流模型中，根据所有OD随机需求和路段随机供给的交通分配结果计算上层规划的目标函数，得到种群中每个个体(VMS选址方案)的适应度，并进行选择、交叉、变异及非支配排序等步骤，最终获得VMS选址问题的Pareto最优解集。算法流程如图2所示。
图2 基于Monte Carlo的NSGA-II算法流程图Fig.2 Flowchart of NSGA-II algorithm based on Monte Carlo
4 算例分析
以图3所示的简单路网为例，对上述模型及求解算法进行验证。假设VMS候选集合V={V2,V5,V15,V20,V29,V34}，V2的有效影响路段为{15,16,17,18,19}，V5的有效影响路段为{20,21,22,37,38,39}，V15的有效影响路段为{17,18,19,20,21,22}，V20的有效影响路段为{23,24,25,26,27}，V29的有效影响路段为{31,32,33,34,35,36}，V34的有效影响路段为{37,38,39,40,41}。表1为简单路网的相关参数，包括路段自由流行程时间、通行能力上限。
图3 简单路网Fig.3 Simple road network
表1 路网参数Tab.1 Parameters of road network
4.1 模型参数
假设VMS投资函数为G=∑(i, j)bZij,(i, j)∈A，其中b为配置每个VMS所需费用，b=200 000元，预算总额B=600 000元，算法用MATLAB编程实现，NSGA-II算法的基本参数为：种群规模20，进化代数100，交叉概率0.9，变异概率0.1。
4.2 计算结果分析
应用NSGA-II算法求出参数ρ=0.8，θ=0.01，β=0.1，诱导服从率E为不同值时的Pareto最优VMS选址解集及对应的路网总行程时间的期望值(Expected Total Travel Time, ETTT)，如表2所示。
对表2进行初步分析，发现有些选址方案(如V2,V29和V20,V29)在不同参数组合的随机情景下都被选中，这是由于在随机需求与随机供给条件下，本文模型很好地降低出行环境的动态变化给选址带来的敏感性影响，得到稳健性VMS选址方案，决策者可综合考虑VMS建设、运营与维护成本等因素，在规划实践中将路段2，20，29作为规划方案的重点选择对象部署VMS。
为了进一步分析诱导服从率E对路网运行质量的影响，图2显示了E取不同值时的VMS最优解集分布。不难发现，当E值增大到0.6时，不同E取值下的Pareto前沿面整体都在往下移动，分布在Pareto前沿面上的个体ETTT值呈下降趋势，这可以解释为交通网络中部署的VMS发挥了诱导作用，随
表2E取不同值时的计算结果
Tab.2 Calculation results for differentEvalues
参数组合ρ=0.8，θ=0.01，β=0.1，E=0.4ρ=0.8，θ=0.01，β=0.1，E=0.6个体序号ABCDEABCDE选址方案V2，V29V20，V29V2，V29，V34V29，V34V15，V34V20，V29V2，V29V2，V29，V34V29，V34目标值F110.9999.14218.58010.92514.8479.24111.17917.3179.859F21.0231.0641.0091.0520.9981.0821.0230.9941.058ETTT0.5280.4970.5030.5030.4940.5050.5030.5110.498参数组合ρ=0.8，θ=0.01，β=0.1，E=0.8ρ=0.8，θ=0.01，β=0.1，E=0.1个体序号ABCDEABCDE选址方案V20，V29V2，V29V2，V20V2，V29，V34V2，V34V15，V34V2，V15，V34V20，V29V29，V34目标值F19.31610.79214.30418.26115.64515.69822.4209.81410.030F21.0461.0381.0271.0121.0241.0281.0121.1181.030ETTT0.5130.5180.5140.4860.5060.5530.5140.5100.488
着出行者对VMS发布信息服从程度的逐步上升，有效地降低了整体网络的ETTT值。而随着E值的进一步增大，Pareto前沿面整体往上移动，ETTT值有上升趋势，此时，过多的出行者接受VMS诱导，极易形成集聚反应，将会恶化交通网络的运行状况。
图4显示了不同E值的选址方案ETTT值与没有部署VMS的路网ETTT值的比较情况。其中，在没有部署VMS的路网中，考虑了相同抽样条件的随机需求与随机供给情景下求解得到的ETTT值为0.54 h。
图4 E为不同值时的最优解集分布对比Fig.4 Comparison of distributions of optimal solutionunder different E values
从图5中清晰可见，当E=1时，个体序号A的ETTT值大于没有部署VMS的路网ETTT值，这说明随着E值越接近1，VMS对路网运行质量的改善作用呈下降趋势，并可能出现比不发布诱导信息还差的局面。对比没有部署VMS的路网，所有选址方案的ETTT值平均下降了2.37%。当E=0.6时，通过部署VMS平均降低了网络总行程时间的3.78%；当E=0.4和E=0.8时，平均降低的网络总行程时间分别为3.22%和3.26%。
5 结论
本文基于Monte Carlo模拟技术刻画了随机需求和随机供给情景下的路网交通状态，采用出行者信息响应模型描述了路网中出行者的路径选择行为，建立了VMS影响区域信息熵、路网总行程时间均值与标准差加权和最小的双目标VMS选址规划模型。最后采用基于Dial算法的MSA均衡分配和NSGA-II算法对模型进行了优化求解，以一个24个节点的简单路网进行了算例分析，验证了本文所提模型及算法的有效性。
图5 路网中有无VMS的ETTT值对比Fig.5 Comparison of ETTT values between VMS installed and uninstalled in network
需要说明的是，文中采用的各种函数及参数仍需进一步利用实际数据进行标定，以使模型结果更切合实际应用。此外，本文采用的Monte Carlo法虽然具有能够描述复杂多样的系统行为的优点，但其计算量随着网络规模增加而急剧增加。如何设计一套Monte Carlo法结合启发式算法的混合求解算法，在保证解质量的前提下提高求解速度将是下一步研究的重点。
[1] 戢晓峰,覃文文.考虑局部排队延误的VMS选址双层规划模型[J].交通运输系统工程与信息,2014,14 (6):194-200. JI Xiao-feng, QING Wen-wen. Bi-level Programming Model for VMS Layout Considering Local Queuing Delay[J]. Journal of Transportation Systems Engineering and Information Technology, 2014,14(6):194-200.
[2] ZHONG Shi-quan, ZHOU Li-zhen, MA Shou-feng, et al. Effects of Different Factors on Drivers’ Guidance Compliance Behaviors under Road Condition Information Shown on VMS [J]. Transportation Research Part A: Policy and Practice, 2012, 46(9): 1490-1505.
[3] XU Tian-dong, SUN Li-jun, PENG Zhong-ren. Empirical Analysis and Modeling of Drivers’ Response to Variable Message Signs in Shanghai, China [J]. Transportation Research Record, 2011,2243: 99-107.
[4] 尚华艳,黄海军,高自友.基于元胞传输模型的可变信息标志选址问题研究[J].物理学报,2007,56(8):26-31. SHANG Hua-yan, HUANG Hai-jun, GAO Zi-you. Locating the Variable Message Signs by Cell Transmission Model [J]. Acta Physica Sinica, 2007, 56(8): 26-3.
[5] 姜桂艳,郑祖舵,白竹, 等.拥挤条件下可变信息板交通诱导信息对驾驶行为的影响[J]. 吉林大学学报: 工学版,2006,36(2):183-187. JIANG Gui-yan, ZHENG Zu-duo, BAI Zhu, et al. Simulation-based Assessment of Variable Message Signs Route Guidance Information under Congestion Condition[J]. Journal of Jilin University: Engineering and Technology Edition, 2006, 36(2): 183-187.
[6] CHIU Y C, HUYNH N, MAHMASSANI H S. Determining Optimal Locations for VMS’s under Stochastic Incident Scenarios [C]// Transportation Research Board 80th Annual Meeting. Washington, D. C.: TRB, 2001.
[7] CHIU Y C, HUYNH N. Location Configuration Design for Dynamic Message Signs under Stochastic Incident and ATIS Scenarios [J]. Transportation Research Part C: Emerging Technologies, 2007, 15(1): 33-50.
[8] LAM W H K, CHAN K S. A Model for Assessing the Effects of Dynamic Travel Time Information via Variable Message Signs[J]. Transportation, 2001, 28(1): 79-99.
[9] 袁舒平,漆凯,关积珍.考虑诱导信息影响的可变信息标志优化选址研究: 北京南站为例[J].交通运输系统工程与信息,2011,11(增1):228-233. YUAN Shu-ping, QI Kai, GUAN Ji-zhen. Research on the Location Choice of the Optimal Variable Messages Signs in Consideration of the Effect of Traffic Guidance Information: Case Study of the Road Area of Beijing South Railway Station [J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(S1): 228-233.
[10]杨远舟,毛宝华,张笑杰, 等.基于路径诱导的高负荷路网微循环组织研究[J].系统仿真学报,2010,22(7):1580-1584. YAN Yuan-zhou, MAO Bao-hua, ZHANG Xiao-jie, et al. Study on Traffic Micro-circulation Organization in Heavy Traffic Networks Based on Route Guidance[J]. Journal of System Simulation, 2010, 22(7): 1580-1584.
[11]FISK C. Some Developments in Equilibrium Traffic Assignment [J]. Transportation Research Part B: Methodological, 1980, 14(3): 243-255.
[12]蒲云,刘海旭.基于部分随机用户平衡的可靠性网络设计[J].西南交通大学学报,2011,46(2):321-325. PU Yun, LIU Hai-xu. Reliable Network Design Based on Partial Stochastic User Equilibrium [J]. Journal of Southwest Jiaotong University, 2011, 46(2): 321-325.
[13]陈大山, 孙剑, 李克平. 基于SPEA2的城市快速路速度引导多目标优化[J]. 公路交通科技, 2011,28(10):92-95. CHEN Da-shan, SUN Jian, LI Ke-ping. Multi-object Optimization of Urban Expressway Speed Guidance Based on SPEA2 [J]. Journal of Highway and Transportation Research and Development, 2015, 32(9):128-132.
[14]DEB K, PRATAP A, AGARWAL S, et al. A Fast Elitist Multi-objective Genetic Algorithms: NSGA-Ⅱ [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
[15]四兵峰,张好智,高自由.求解Logit随机网络配流问题的改进Dial算法[J].中国公路学报,2009,22(1):78-83. SI Bing-feng, ZHANG Hao-zhi, GAO Zi-you. Improved Dial’s Algorithm for Logit-based Stochastic Traffic Metwork Assignment Problem [J]. China Journal of Highway and Transport, 2009, 22(1): 78-83.
[16]LAGUNA M. Applying Robust Optimization to Capacity Expansion of One Location in Telecommunications with Demand Uncertainty [J]. Management Science, 1998, 44(11): 101-110.
A Bi-level Programming Model for Variable Message Signs Locating Based on Partial Stochastic User Equilibrium
QIN Wen-wen
(Key Laboratory of Road and Traffic Engineering of Ministry of Education, Tongji University, Shanghai 201804,China)
In order to accurately describe the uncertainty impact of variable message sign (VMS) locating under stochastic demand and stochastic supply, a Monte Carlo based simulation methodology is used to characterize the randomness of road network state, and a bi-level programming model for multi-objective optimization of VMS locating is established considering the different guidance compliance rates for drivers on the information release of VMS. The upper-level model, used for giving the VMS locating scheme in random environment, is a dual-objective programming model for minimizing the information entropy of coverage area by VMS and the weighted sum between mean and standard deviation of total travel time. The lower-level model is partial stochastic user equilibrium assignment model, which is used to analyse the traveler’s complicated route choice behavior under guidance of VMS. A non-dominated sorting genetic algorithm (NSGA-II) is adopted to solve the whole model, and example analysis is carried out on a simple network. The calculation result indicates that (1) NSGA-II can effectively solve the multi-objective optimization problem of VMS locating, and get average 5 Pareto solutions; (2) the mean travel time of road network with VMS can be dropped maximum from 0.54 h to 0.486 h after deployment of VMS; (3) when guidance compliance rate increased from 20% to 60%, the inductive benefit of VMS is shown an upward trend, as the guidance compliance rate close to 100%, the road network performance with VMS is on the downward trend, and may be worse than no information released situation.
traffic engineering; VMS locating; non-dominated sorting genetic algorithm-II; multi-objective optimization; Monte Carlo simulation
2015-12-30
覃文文(1986-)，男，广西柳州人，博士研究生.(qinwenwen_tongji@126.com)
10.3969/j.issn.1002-0268.2016.11.019
U491
A
1002-0268(2016)11-0126-08
