考虑局部排队延误的VMS选址双层规划模型

戢晓峰，覃文文

（1.昆明理工大学 交通工程学院，昆明650500；2.长沙理工大学 公路工程省部共建教育部重点实验室,长沙410004；3.吉林大学 汽车仿真与控制国家重点实验室，长春130025）

考虑局部排队延误的VMS选址双层规划模型

戢晓峰*1,2,3，覃文文1

（1.昆明理工大学 交通工程学院，昆明650500；2.长沙理工大学 公路工程省部共建教育部重点实验室,长沙410004；3.吉林大学 汽车仿真与控制国家重点实验室，长春130025）

用Monte Carlo模拟技术刻画路网状态的随机性，优先考虑在交通网络瓶颈路段设置可变信息板待选点，建立多目标优化可变信息板选址双层规划模型.上层模型为基于不确定风险决策最小和诱导效益最大的双目标规划模型，下层模型为考虑局部网络有排队延迟现象的随机用户平衡模型.采用增广Lagrange对偶算法与相继平均算法组合求解下层模型，采用非劣排序遗传算法-II求解整个双层规划模型.算例结果表明，在可变信息板资金预算约束下，非劣排序遗传算法-II能够有效求解可变信息板选址的多目标优化问题，得到6组Pareto解.研究结果可为城市道路网可变信息板诱导配置的优化和建设提供决策支持.

智能交通；VMS选址；双层规划；交通诱导；非劣排序遗传算法-II；增广Lagrange对偶算法

1 引 言

可变信息板（Variable Message Signs，VMS）作为一种有效的群体式诱导信息发布系统，其布局和信息发布对出行质量起着关键性的影响[1].VMS信息发布对出行者路径选择行为的影响仍然是国内外学者广泛关注的问题[2-4]，但对于VMS选址问题的相关研究并不多见.后者研究对象大多限于高速公路或快速路的VMS布局优化，较少考虑交通系统对VMS选址建模的不确定性影响.Chiu和Huynh[5]假定所有出行者拥有完全信息，能预期其他出行者路径选择行为，建立了上层为最大化信息发布收益的VMS最优布点，下层为用户动态最优交通分配模型.该模型涉及多个VMS候选方案的评估，计算量过大，难以应用于大规模城市路网.随后，Chiu和Huynh[6]进一步考虑了随机事故与ATIS共存情况下的动态VMS最优选址问题，发现同时部署VMS与ATIS，比相继安装两个系统效益更好.

综上分析，VMS选址方案是在一个不确定性的路网环境中进行VMS的最佳布局，而这种不确定性主要体现在：

（1）交通需求的不确定性，即用户出行的随机性；

（2）道路交通状态的不确定性，如路段突发交通事故等；

（3）认知不确定性，即VMS信息发布的不完全和出行者对信息的认知偏差，导致出行者做出违背信息诱导的路径选择行为.

本文引入信息熵的概念，以诱导交通流与VMS影响区域产生的信息量作为诱导效益最大化的衡量指标，使用行程时间的期望和标准差量化不确定决策中的风险，建立VMS选址模型.

2 问题描述

考虑由VMS有效影响路段组成的局部路网，在路段能力约束下，一个有效的VMS选址方案应该尽可能地消除瓶颈路段上由于溢流而产生的排队现象.因此，本文利用路段费用的变化来反映VMS的诱导作用，即路段费用由行程时间和排队延误组成，出行者偏向选择旅行费用较小的路径出行.本文为降低模型整体规模的计算复杂度，在算例网络中利用UE配流确定瓶颈路段，以此得到VMS候选点集合，并界定每个VMS的有效影响路段.

考虑交通网络G=(N,A)，N为所有节点的集合；A为所有路段的集合；为所有VMS有效影响路段的集合；W为所有起讫点（OD）集合，w∈W；Kw为OD对w的所有路径集合，k∈Kw；Ω为OD需求随机抽样形成的不确定情景集合，并假设OD需求是满足给定概率分布的随机变量；ω为Ω集合中的任一需求情景实现；qω为ω情景下的OD需求量；pω为ω情景发生概率；Λ为路段交通状态不确定交通情景集合；λ为Λ集合中的任一交通情景实现；pλ为λ情景发生概率为ω情景下的路段α所需的行程时间，假设其只与该路段上的流量和实际通行能力有关；为ω情景下的OD对w之间路径k的阻抗；为ω情景下的路径路段流量关系的布尔变量，若路段a在OD对w之间路径k上，其值为1，否则为0；为ω情景下的OD对w之间路径k的流量；Cα为路段α的通行能力.

由于路段的交通状态具有不确定性与实时性，本文利用信息熵衡量VMS有效影响路段上交通情景产生的信息量.信息量越大，越需设置VMS消除路段交通状态的不确定性.

3 模型建立

3.1 VMS的诱导效益值估计

定义VMS的诱导效益为VMS的诱导交通流与VMS消除有效影响路段产生的信息熵的乘积，计算公式为

考虑四种路段交通情景的集合Λ={λ1=顺畅（V∕C≤0.6）；λ2=稍有拥堵（0.6＜V∕C≤0.8）；λ3=拥堵（0.8＜V∕C≤1）；λ4=严重拥堵（V∕C＞1）}.其中，估计任一交通情景的发生概率pλ的基本步骤是：

Step 1初始化，确定OD需求概率分布函数.

Step 2令抽样次数k=1.

Step 3随机生成 OD需求向量 qk,ω=

Step 4采用随机用户平衡配流模型，将交通需求分配到路网上，获得有效影响路段 j上的V∕C比值

Step 5若∈(0,0.6]，则 λ1,j=λ1,j+1；若∈(0.6,0.8]，则 λ2,j=λ2,j+1；若∈(0.8,1]，则λ3,j=λ3,j+1；若∈(1,∞]，则λ4,j=λ4,j+1.

Step 6若k小于抽样规模S，则k=k+1；返回Step3.

Step 7若k=S，则停止，计算，再由式(1)得到有效影响路段 j产生的信息熵.

3.2 VMS选址双层规划模型

VMS选址要考虑用户的路径选择行为，一般从规划角度构建上层决策模型，从用户角度构建下层路径选择模型.理论上，如整个路网都设置VMS能最大化VMS的诱导作用，但容易导致集聚反应，使得网络更加拥堵.考虑OD需求和路段交通状态的不确定性，不同需求强度和交通状态下的VMS选址方案差异很大，决策者也将面临较大的风险决策.为降低选址方案对不确定性的敏感度，采用行程时间的期望和标准差量化不确定决策中的风险，使得布置的VMS诱导效用值最大，不确定性的风险值最小.

3.2.1 上层规划模型

上层规划模型包含两个目标函数：一是最大化诱导流量和VMS影响区域的信息量；二是最小化所有交通情景发生下的路网总行程时间均值和标准差，决策变量为Zα.模型如下.

式中 Gα(Zα)为路段α配置VMS的投资函数；B为整个路网配置VMS的预算总额；Zα是0-1决策变量，当路段 α设置VMS时，Zα=1，反之，Zα=0；Fω为需求情景ω时的路网总行程时间；为路网总行程时间的期望值；ρ(0≤ρ≤1)为权重因子，反映了决策者对网络效益和网络稳定性不同的重视程度.ρ取值越大，表明决策者越重视网络效益，而忽略网络稳定性.

3.2.2 下层规划模型

下层规划模型为考虑局部网络有排队延迟现象的随机用户平衡模型.该局部网络由VMS有效影响路段集合A¯组成，并在有效影响路段上添加通行能力约束条件.如路段流量超过通行能力，排队现象就会形成.在基于Fisk的随机用户平衡模型上添加容量约束条件，通过VMS的有效布点使常发性拥挤路段的V/C值小于1，以此刻画VMS有效诱导行驶车辆、消除排队现象的作用，达到总行程时间最小的目标.其中，下层模型的Kuhn-Tucker条件的具体证明过程可参考文献[7]和[8]，本文不再累赘.θ为出行者对VMS发布信息的认知偏差系数，本文取0.1.若θ=0，表明出行者等概率地选择VMS影响区域内的各条路径；若θ→∞，表明出行者倾向于选择最短路径出行.模型如下：

4 模型求解算法

4.1 双层模型求解

多目标优化VMS选址问题的最佳方法是求得问题的Pareto解，然后根据决策者的偏好程度从多组Pareto解中选出最优解[9].因此，采用基于Monte Carlo模拟的非劣排序遗传算法-II（Nondominated Sorting Genetic Algorithm-II，NSGA-II）算法求解双层规划模型[10]，即生成满足VMS投资预算要求的初始可行解集后，代入含容量限制的平衡配流模型中，根据所有OD随机需求交通分配结果计算上层规划的目标函数，得到种群中每个个体（VMS选址方案）的适应度，并进行选择、交叉、变异及非支配排序等步骤，最终获得VMS选址的Pareto最优解集.其中，带容量约束的SUE模型采用增广Lagrange对偶算法与MSA算法组合求解.求解流程如图1所示.

图1 基于Monte Carlo的NSGA-II算法流程Fig.1 Flow chart of NSGA-II based on Monte Carlo

4.1下层模型求解

为求解含有不等式约束的下层规划问题，在式（9）中加入一个Lagrange项，构造增广Lagrange函数，形成只含有非负线性等式约束的目标函数.

式中 η值为惩罚因子(η＞0)；μ向量为对偶约束的 Lagrange算子向量.若知道 μ，对于L(f,x,μ,η)，只要取足够大的罚因子，就可通过求解等式约束问题得到原问题的最优解.

因此，设计增广Lagrange对偶算法与MSA算法组合求解式（14）.

Step 1初始化.选择初始的μ值，即

Step 2求解子问题.令路段时间函数为

利用MSA算法求解一般性的随机用户均衡（Stochastic User Equilibrium，SUE）无能力约束交通分配问题，得到路段流量解xω,n.

Step 3终止条件.若（预置一个很小的数），停止迭代.否则转下步.

Step 4更新算子和惩罚因子.由式（20）计算新的和 ρn+1：

式中 参数2≤k≤10，γ=0.25，并令n=n+1，转Step 2.

上述步骤中，Step 2可用基于Logit加载技术的MSA算法求解随机用户平衡的交通分配问题；Step 3是一个确保路段流量有效的停止准则.在Step 4中，如对偶约束的不可行程度没有足够降低，则惩罚算子的η值上升.

5 算例分析

算例交通网络包含38条路段和20个节点，从节点1到20只有1个OD对，如图2所示.

图2 VMS候选点与瓶颈路段示意图Fig.2 Test network

采用BPR函数作为路阻函数

式中 tα0表示路段α的自由流行程时间，各参数取值如表1所示.

为识别瓶颈路段，按照用户均衡原则进行交通分配，得到最拥堵的8个路段是5，8，16，19，20，27，30和32，则VMS候选点集合为{Z1，Z3，Z12，Z14，Z17，Z23，Z25，Z28}，Z1的有效影响路段为{3, 4,5}，Z3的有效影响路段为{6,7,8}，Z12的有效影响路段为{14,15,16}，Z14的有效影响路段为{17, 18,19}，Z17的有效影响路段为{20,21}，Z23的有效影响路段为{25,26,27}，Z25的有效影响路段为{28, 29,30}，Z28的有效影响路段为{31,32}.

算法用MATLAB编程实现，并设计4种实验场景以验证NSGA-II算法的有效性.NSGA-II算法基本参数为：种群规模40，进化代数100，交叉概率0.9，变异概率0.1.

表1 算例相关参数Table 1 Parameters of test network

表2 4种实验场景基本情况Table 2 The basic situation of four kinds of experiment scenarios

在每一种场景中，应用NSGA-II算法求出所有个体的路网总行程时间的期望值（expected total travel time,ETTT）与标准差（standard deviation of total travel time,SDTTT），表3给出了4种实验场景下的Pareto最优VMS选址解集.

表3 4种实验场景的Pareto最优VMS选址Table 3 The Pareto set of VMS locations for four kinds of experiment scenarios

对表3进行初步分析，可以得到如下结果：

（1）当资金预算相同，出行需求增大时，安装VMS的交通网络ETTT值增大；

（2）当出行需求相同，资金预算减少时，安装VMS的交通网络ETTT值增大.

图3对比了4种场景下不同选址方案的ETTT值与未安装VMS的ETTT值.其中，在未安装VMS的交通网络中，分别考虑OD需求均值为1 000和1 500求解得ETTT值：585.23 h和958.54 h.

对参数τ和ρ捆绑分析发现，τ和 ρ反映了VMS选址对交通网络效益和稳定性的影响.在需求均值为1 000，资金预算都相同的情况下，表4给出了三种场景中不同设计参数组合的ETTT值和SDTTT值.

表4 三种场景下的ETTT值和SDTTT值Table 4 The ETTT and SDTTT of three experiment scenarios

图3 交通网络中有无VMS的ETTT值对比Fig.3 The Comparison of ETTT between VMS installed and uninstalled in network

6 研究结论

本文研究了在不确定性的交通网络中寻找VMS的最佳布局点，用基于Monte Carlo的NSGA-II对VMS选址的多目标优化问题进行求解，考虑了OD需求、资金预算和设计参数不同组合的5种实验场景，得出以下结论：

（1）所有实验场景的ETTT值基本上大于没有安装VMS的交通网络ETTT值，这一现象可以解释为在求解下层模型中构造了增广Lagrange函数，使得原本局部网络发生拥挤的路段，通过设置Lagrange算子μ，强制性增大拥挤路段的出行阻抗，以此刻画了VMS有效诱导行驶车辆、消除排队现象的作用；

（2）随着设计参数τ、ρ的变大，OD需求抽样的随机性增大，ETTT与SDTTT加权和的离散程度也随之增大.发现ETTT值越大，SDTTT值就越小，ETTT值越小，SDTTT值就越大，存在明显的替代关系；

（3）出行者的随机需求与决策者的风险偏好对选址方案具有显著影响，ETTT与SDTTT作为量化网络稳定与效益程度的重要指标，成为直接影响决策者制定方案的重要影响因素.

[1] 戢晓峰,黄永忠,何增辉,等.面向诱导的交通状态信息提取方法[J].计算机工程与应用,2010,46(25):16-18. [JI X F,HUANG Y Z,HE Z H,et al.Traffic state information extraction methods for traffic guidance[J]. Computer Engineering and Applications,2010,46(25): 16-18.]

[2] ZHONG Shiquan,et al.Effects of different factors on drivers’guidance compliance behaviors under road condition information shown on VMS[J].Transportation Research Part A,2012,46(9):1490-1505.

[3] XU Tiandong,SUN Lijun,PENG Zhongren.Empirical analysis and modeling of drivers’response to variable message signs in Shanghai,China[J].Transportation Research Record,2011(2243):99-107.

[4] 王卫卫，赵小梅，李新刚，等.VMS对驾驶员路径选择影响的实证研究与建模[J].交通运输系统工程与信息,2013,13(3):60-64.[WANG W W,ZHAO X M,LI X G,et al.Empirical study and modeling of variable message signs on route choice behavior[J].Journal of Transportation Systems Engineering and Information Technology,2013,13(3):60-64.]

[5] CHIU YC,HUYNHN,MAHMASSANIHS. Determining optimallocationsforVMS’sunder stochastic incident scenarios[C]∕Transportation Research Board Annual Meeting.Washington D C, 2001.

[6] CHIU Y C,HUYNH N.Location configuration design for dynamic message signs under stochastic incident and ATIS scenarios[J].Transportation Research Part C, 2007,15(1):33-50.

[7] BELL MGH.Stochastic user equilibrium assignment in network with queues[J].Transportation Research Part B, 1995,29(2):125-137.

[8] RYU S,CHEN A,XU X,et al.A dual approach for solving the combined distribution and assignment problem with link capacity constraints[J].Networks and Spatial Economics,2014,14(1):245-270.

[9] 庞晓平,陈进.非支配排序遗传算法的动压轴承形状多目标优化[J].西南交通大学学报,2012,47(4): 639-645.[PANG X P,CHEN J.Multi-objective shape optimization of hydrodynamic journal bearings using non-dominated sorting genetic algorithmⅡ[J].Journal of Southwest Jiaotong University,2012,47(4):639-645.]

[10] 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.

Bi-level Programming Model for VMS Layout Considering Local Queuing Delay

JI Xiao-feng1,2,3,QIN Wen-wen1
(1.Faculty of Transportation Engineering,Kunming University of Science and Technology,Kunming 650500,China 2.Key Laboratory of Highway Engineering,Ministry of Education,Changsha University of Science&Technology,Changsha 410004, China;3.State Key Laboratory ofAutomotive Simulation and Control,Jilin University,Changchun 130025,China)

Using Monte Carlo methodology to characterize randomness of the road network state,a number of candidate variable message signs(VMS)locations are deployed in bottleneck links,and then a biobjective bi-level programming model is established for optimization of VMS location.The upper level model is a dual-objective programming model considering the minimum of uncertain risk decision-making and the maximum of guidance benefits.The lower level model is stochastic user equilibrium with local network considering queuing delay.The augmented Lagrange dual algorithm combined with method successive average algorithm is adopted to solve the lower model,and the non-dominated sorting genetic algorithm-II(NSGA-II)is adopted to solve the whole bi-level programming.Analysis result indicates that NSGA-II can effectively solve the bi-level programming model of VMS location under the restriction of capital budget,and get 6 Pareto solutions.Outcomes of this research can provide decision support for optimization and construction of VMS layout in uncertain road network.

intelligent transportation;VMS layout;bi-level programming;traffic guidance;non-dominated sorting genetic algorithm-II;augmented Lagrange dual algorithm

2014-04-03

2014-09-24录用日期：2014-10-08

国家自然科学基金项目（61263025）；公路工程省部共建教育部重点实验室开放基金（kfj100107）；汽车仿真与控制国家重点实验室开放基金（20111116）.

戢晓峰(1982－)，男，副教授，博士.*通讯作者:yiluxinshi@sina.com

1009-6744（2014）06-0194-07

U491.1

A