基于元胞传输模型的动态拥堵收费最优费率计算方法转让专利
申请号 : CN201810418436.0
文献号 : CN108830401B
文献日 : 2021-07-09
发明人 : 刘志远 , 王路濛 , 程启秀 , 俞俊
申请人 : 东南大学
摘要 :
权利要求 :
1.基于元胞传输模型的动态拥堵收费最优费率计算方法，其特征在于，包括如下步骤：(1)输入城市交通网络相关数据，建立交通网络拓扑图；
(2)基于警戒线收费的要求，将收费区域的各个入口确定为收费起点，出口确定为收费终点，得到收费区域内各路段长度，并建立随时间变化的基于距离和拥堵的联合收费函数一般表达式；建立随时间变化的基于距离和拥堵的联合收费函数一般表达式具体为：设路W
网G＝(N,A)中有N个节点和A个路段，W表示起讫点对OD的集合，P表示OD之间的路径集合，假设收费警戒线内的最小长度和最大长度分别为l0和lK，将行程距离分K个相等的间隔，每个间隔的距离长度函数由两个端点表示，设每段收费区间的顶点为l＝(l0,l1,…,lk,…,T T
lK) ，对应的收费分别为φ＝(φ0,φ1,…,φk,…,φK) ， 表示第k个收费区间的长度，则该收费区间基于距离的收费函数φ(l)表示为：用各路段的延误时间表征道路拥堵情况，则OD点对w之间路径p上基于拥堵水平的收费函数 的一般表达式为：
其中 表示OD点对w之间路径p上基于拥堵的收费费率， 表示延误时间，t0表示路段自由流行程时间，β为拥堵费率，基于距离和拥堵的联合收费函数τ(l,β)的一般表达式表示为：
式(3)表示基于距离和拥堵的联合收费函数，其中， 表示OD点对w之间路径p上基于距离和拥堵的联合收费费率，θ1和θ2分别表示距离收费和拥堵收费的权重；
对于第d个子区间，基于距离和拥堵的联合动态拥堵收费函数τd(l,β)的一般表达式表示为：
表示d区间内OD点对w之间路径p上基于距离和拥堵的联合收费费率；
车辆到达收费警戒线区域内的确切时间根据从起始点到收费警戒线区域内的行程时间确定，因此正确地计算出收费时间间隔d：其中， 表示大于等于括号中数值的最小整数，t′和 分别表示元胞传输模型中从起始点到收费警戒线区域内的行程时间以及时间区间长度，以分钟为单位；
(3)采用基于路径的元胞传输模型，模拟交通流的传播过程，进而计算平均路线在途行程时间；具体为：将路段分割成基本单元、时长划分为时间间隔，元胞传输模型的基本形式表示为：
表示元胞i在第t个时间步长的交通量， 表示在第t个时间步长从上游元胞i移动i i+1
至下游元胞i+1的交通量，Q表示从元胞i流出的最大车辆数，N 表示拥堵传播系数，γ表示后向流入速度与前进速度的比值，元胞长度采用车辆在一个时间步长内以自由流的速度通过的距离长度；
构建元胞传输模型时需要考虑单元胞相接、路段会聚和发散三种情形，所构建的元胞传输模型包含五种元胞以及三种链接；五种元胞分别为：普通元胞，上下游各有一个元胞与之相连；发散元胞，上游只与一个元胞、下游与两个元胞相连；会聚元胞，上游与两个元胞、下游只与一个元胞相连；源元胞，只有下游元胞而没有上游元胞；终元胞，只有上游元胞而没有下游元胞；三种链接分别为普通链接、发散链接和会聚链接；
初始化元胞的设定值：
五种元胞被表示为：
源元胞：
普通元胞：
发散元胞以及会聚元胞：
终元胞：
其中， 表示路径p上的元胞i在时间间隔t初始时的占有率， 表示在时间区间t初始时路径p上从元胞i流向元胞j的交通量，hp,t表示在时间区间t内路径p上的车辆离开率；对于参数 当元胞i(or j,k)在路径p上时， 否则CD、CM、CR、CS、CO分别表示发散元胞、会聚元胞、源元胞、终元胞和普通元胞的集合；Γi为元胞i的下游元胞集合， 为元胞i的上游元胞集合；T表示最大时间范围；
三种链接被表示为：
普通链接：
发散链接：
会聚链接：
其中，ED、EM、EO分别表示发散链接、会聚链接和普通链接的集合， 为时间区间t初始时将会从发散元胞i流入元胞j的合计占有率， 表示路径p上的元胞i在时间间隔t初始时的占有率均值，μ为一个无穷小且大于零的数；
上述的元胞传输模型中，式(8)‑(9)中假设初始的元胞占有率和流出交通量为零；式(10)‑(13)表示基于路径的元胞更新过程；式(14)‑(16)表示基于路径的交通流传播约束；
其中，基于路径的元胞传输模型的转化率并非外源性的，而是由上下游元胞的供给和需求唯一确定；
设定车辆的路径选择决策遵循动态用户均衡原则，将基于路径的元胞传输模型应用于动态用户均衡问题中，通过计算从元胞传输模型中输出的实际路径行程时间，确定同时出发车辆唯一确定的平均在途行程时间；
理想的动态用户均衡状态的均衡条件表示为：每个OD对间同时出发的旅客所产生的总广义成本相等且最小；
动态用户均衡理论的数学表达式为：其中，
Td∈T表示随时间变化的收费时间区间集合， 表示OD对w在时间区间t内的最小路径出行成本，α为时间价值， 表示在时间区间t内，从OD对w上的路径p离开的广义出行成本；路径流量是关于拥堵费率 的函数，因此，动态用户均衡问题的目的转化为寻找同时满足式(17)和(18)，以及需求流量守恒原则(20)和非负约束(21)的可行流量f≥0,u≥0 (21)
其中，u表示 的向量，
上述式(17)‑(21)介绍的动态用户均衡问题，等价于式(22)中的有限变量不等式问题：式(22)中，上角标*代表最优解，Ψ表示 的列向量，Ω表示满足需求流量守恒原则(20)和非负约束(21)的可行解的集合；
元胞传输模型输出的是每个时间区间的元胞占有率，路径p上的源元胞r在时间区间t初始时的累计离开交通量 等于路径p上从元胞r在时间区间t‑1初始时离开的累计交通量 以及路径p上元胞r在时间区间t内流出的交通量 的总和；路径p上终元胞s在初始时间区间ω初始时的累计到达交通量 等于路径p上终元胞s在时间区间ω‑1初始时的累计到达交通量 以及路径p上终元胞s在时间区间ω‑1的累计流入交通量 的总和，用数学公式表达为：
其中， 为时间区间t初始时在路径p上从元胞r离开的累计交通量；实际上，在时间离散化的情况下，时间区间t内在路径p上从元胞r离开的累计交通量 未必全部同时到达终点s；采用平均在途行程时间代替该路径上同时离开车辆的实际在途行程时间，引入两个到达时间系数ω1和ω2，ω1是满足 条件的最小时间系数值，ω2是满足条件的最小时间系数值；则时间区间t内从连接OD对w的路径p上离开的交通流的平均行程时间 的表达式为：
(4)建立双层优化模型，通过优化整个系统来确定满足动态用户均衡原则、随时间变化的基于距离和拥堵的联合拥堵费率；
(5)应用混合自适应梯度投影算法和人工蜂群算法，解决步骤(4)中提出的双层优化模型，输出最优费率。
2.如权利要求1所述的基于元胞传输模型的动态拥堵收费最优费率计算方法，其特征在于，步骤(4)中，建立了双层优化模型，通过优化整个系统来确定满足动态用户均衡原则、随时间变化的、基于距离和拥堵的联合拥堵费率；其上层为路网系统优化模型，目的是使路网的总行程时间最小；下层为动态的用户均衡状态，描述为多元不等式；具体表达式为：上层：
下层：
3.如权利要求1所述的基于元胞传输模型的动态拥堵收费最优费率计算方法，其特征在于，步骤(5)中，解决步骤(4)中双层优化模型的方法，采用自适应梯度投影算法解决下层的多元不等式问题；采用人工蜂群算法解决上层的优化模型；采用自适应梯度投影算法解决下层的多元不等式问题具体为：(51)设 u∈[0.5,1]；ε＞0，ρmax＞0，ρ0＞0，f0∈Ω；γ0＝ρ0，k＝0；
(52)寻找满足 条件的最小非负整数lk，更新满足约束(29)的非最短路径流量：
其中 是第k次迭代中OD对w之间的最短路径； Fk表示向量表示向量 更新最短路径流
量：
(53)如果满足不等式(30)，则 否则γk+1＝ρk+1；
(54)如果满足预先设定的收敛标准，则停止算法得到最终结果fk+1；否则，令k＝k+1，返回步骤(52)。
4.如权利要求3所述的基于元胞传输模型的动态拥堵收费最优费率计算方法，其特征在于，步骤(5)中，采用人工蜂群算法解决上层的优化模型具体为：(a)设定群体规模Nc，引领蜂数量Ne，跟随蜂数量No，阈值limit；设置迭代初始值I＝1，以及最大迭代次数Imax；
(b)随机生成初始解，计算每个引领蜂对应的每个解的适应度值，并初始化阈值为零；
(c)根据现有解进行局部搜索，估计其适应度值；若这个解更好，用新生成的局域解替代现有解，并重置阈值为零；否则，现有解不变但将阈值设为1；
(d)每个跟随蜂采用轮盘赌的方法选择引领蜂，即在[0,1]产生一个均匀分布的随机数r，若概率大于r，该跟随蜂在现有解的周围产生一个新的解，并计算其适应度值；如果这个解更优，则用相邻解替代现有解，否则不改变现有解，并将阈值增加至1；
(e)根据现有解，选择适应度值最高的解，如果存在一个在阈值内无法继续提高适应度值的解，却不是适应度值最高的最优解，则对应的引领蜂角色转变为侦察蜂，在相邻空间重新进行搜索，生成新的随机解，并重置阈值为0；
(f)令I＝I+1，判断算法是否满足终止条件，若I＜Imax则转到步骤(c)；否则终止算法得出最优解。
说明书 :
基于元胞传输模型的动态拥堵收费最优费率计算方法
技术领域
背景技术
市道路拥堵收费是交通需求管理的一种手段,是利用价格杠杆使小汽车使用者改变出行线
路、调整出行时间或变更出行方式，从而达到调控交通需求总量、优化交通出行结构的目
的。
伦敦、斯德哥尔摩和米兰等)相继实施了道路拥堵收费政策，在缓解城市交通拥堵方面取得
了显著成效。由于警戒线收费方式具有易实施和有效性等优点，这些地区几乎都采用了警
戒线收费方式：在城市部分地区，由警戒线确定一个收费区域，对进入该区域的机动车征收
一定的道路拥堵费用。然而，所有实施道路拥堵收费政策的城市都采用了单一定价方法，这
种方法忽略了车辆在警戒线内的出行距离和道路拥堵情况，对不同拥堵情况下警戒线内不
同出行距离的用户征收相同的费用，这带来了不公平收费问题。另外，部分用户可能会故意
在警戒线内增加使用路段来提高其所支付拥堵费用的经济效用，这不但不能缓解交通拥
堵，反而会增加警戒线内的拥堵现象。拥堵收费措施通常具有针对性，针对城市中央商务
区、快速路及外环线以及城市商业区等易发生交通拥堵的区域进行收费，且这些城市通常
具有较高的私人机动车出行比例和完善的环路，交通拥堵区域易于划分，拥堵收费区域之
外存在尚未饱和的路网或发达的公共交通可承担实施拥堵收费后而转移的巨大交通量。
发明内容
函数一般表达式；
的随时间变动的，基于距离和拥堵的联合收费函数。
式具体为：设路网G＝(N,A)中有N个节点和A个路段，W表示起讫点对OD的集合，P 表示OD之
间的路径集合，假设收费警戒线内的最小长度和最大长度分别为l0和lK，可以将行程距离分
K个相等的间隔，每个间隔的距离长度函数可以由两个端点表示，设每段收费区间的顶点为
T T
l＝(l0,l1,…,lk,…,lK) ，对应的收费分别为φ＝(φ0,φ1,…,φk,…,φK) ， 表示第k个
收费区间的长度，则该收费区间基于距离的收费函数φ(l)可表示为：
一般表达式即可表示为：
收费时间为从早上7：30到9：30。由于收费每半个小时变动一次，这两个小时会被分为四个
子区间，进而生成四个子区间的收费表达式；
元胞传输模型的基本形式可表示为：
移动至下游元胞i+1的交通量，Q 表示从元胞i流出的最大车辆数，N 表示拥堵传播系数，
γ表示后向流入速度与前进速度的比值，元胞长度通常采用车辆在一个时间步长内以自由
流的速度通过的距离长度；
胞与之相连；发散元胞，上游只与一个元胞、下游与两个元胞相连；会聚元胞，上游与两个元
胞、下游只与一个元胞相连；源元胞，只有下游元胞而没有上游元胞；终元胞，只有上游元胞
而没有下游元胞；三种链接分别为普通链接、发散链接和会聚链接；
开率。对于参数 当元胞i(or j,k)在路径p上时， 否则
间隔t初始时的占有率均值，μ为一个无穷小且大于零的数；
束；其中，基于路径的元胞传输模型的转化率并非外源性的，而是由上下游元胞的供给和需
求唯一确定；
间，确定同时出发车辆唯一确定的平均在途行程时间；
成本。路径流量 是关于拥堵费率 的函数，因此，动态用户均衡问题的目的转化为寻找
同时满足式(17)和(18)，以及需求流量守恒原则(20)和非负约束(21)的可行流量
交通量 以及路径p上元胞r在时间区间t内流出的交通量 的总和；路径p上终元胞s
在初始时间区间ω初始时的累计到达交通量 等于路径p上终元胞s在时间区间ω‑1初
始时的累计到达交通量 以及路径p上终元胞s在时间区间ω‑1的累计流入交通量
的总和，可用数学公式表达为：
时到达终点s；本发明中采用平均在途行程时间代替该路径上同时离开车辆的实际在途行
程时间，引入两个到达时间系数ω1和ω2，ω1是满足 条件的最小时间系数值，ω2
是满足 条件的最小时间系数值。则时间区间t内从连接OD对w的路径p上离开的交
通流的平均行程时间 的表达式为：
型，目的是使路网的总行程时间最小；下层为动态的用户均衡状态，可描述为多元不等式；
具体表达式为：
投影算法解决下层的多元不等式问题具体为：
流量：
这个解更优，则用相邻解替代现有解，否则不改变现有解，并将阈值增加至1；
间重新进行搜索，生成新的随机解，并重置阈值为0；
题的目标就是寻找一个合适的费率，使得社会总效益达到最大值；本发明提出的基于元胞
传输模型的动态拥堵收费最优费率计算方法相比于已有的算法，更加公平有效，得出的最
优费率使整个路网的时间消耗最小；本发明中采用的基于路径的元胞传输模型与原始的元
胞传输模型相比，拥有无需计算元胞等待时间等优点，使得计算更加简便高效，当本发明应
用在较大的城市区域中时，可以大幅节省整个路网系统的总出行时间。
附图说明
具体实施方式
函数一般表达式；
息如表1所示。
表达式。
0.8km。
率每半个小时变动一次，这两个小时会被分为四个子区间，进而生成四个子区间的收费表
达式。
1800vehicles/h。
径流量：
果这个解更好，则用相邻解替代现有解，否则不改变现有解，并将阈值增加至1。
空间重新进行搜索，生成新的随机解，重置阈值为0。步骤6：令I＝I+1；判断算法是否满足终
止条件，如果I
数值计算出来的。