10 非平衡与随机交通流分配.pdf

1道路交通规划石家庄铁道学院 交通工程分院yanxy@0502310第十讲非平衡分配与随机分配前讲回顾„ Wardrop第一原理‡ 在出行者都确切知道网络状态，并总是选择使自己的行驶时间最小的路径时，网络将会达到平衡状态：同一 OD对之间所有被使用的路径具有相等的时间，并不大于未被使用路径的时间„ Wardrop第二原理‡ 在系统平衡条件下，拥挤路网上的交通流应该按照平均或总的出行成本最小为依据来分配前讲回顾„ 简单平衡分配问题的求解t2x1x)()(221121xtxtxxq=+=)(22xt)(11xt2x1xq第十讲非平衡分配与随机分配„ 10.1 非平衡分配方法„ 10.2 随机分配方法„ 10.3 交通分配方法的选择„重点问题1、非平衡分配中的增量分配方法2、简单的随机分配问题求解10.1 非平衡分配方法„ 交通网络平衡模型是一个维数大、约束多的 NLP问题在 1975年由 LeBlanc等将 Frank-Wolfe算法用于求解UE模型获得成功之前，很多学者一直在探讨用模拟和近似的方法求解交通平衡分配问题；即使在此之后，由于受限于庞大的问题规模和当时相对落后的计算机技术，研究 UE分配的近似算法依然是交通分配中的一个重要课题。

„ 由此得到了有别于寻求 UE分配最优解的一些算法，通常称其为 非平衡分配算法 这些算法在一定程度上是对真正的平衡分配算法的近似或者特殊化1、全有全无（All or Nothing）分配„ 对于任意一个 OD对，将全部出行量都加载到连接这个 OD对的当前最短路径上，而其余路径上的加载量为零即对于任意路段 a，令 ， 然后搜索最短路径，将交通量全部加载到最短路径上去„ 全有全无分配不考虑流量变化对路段阻抗的影响，因此只能用于非拥挤交通网络的分配‡ 全有全无分配法是其他分配方法的基础，其他方法分配过程中均需反复调用全有全无分配方法0)aatt=2例题10-1„ 求解下图网络中的全有全无分配结果„ 解： 路段流量：x2=5, x1=0分配后的路段阻抗：t1=2, t2=112221 xt +=112 xt +=5=q2、增量分配方法„ 增量分配法的基本思想是将 OD量分成 N份，然后分 N次用全有全无分配法分配 OD量，每次分配一个 OD分表；每分配一次，用当前流量修正路段阻抗函数，直到把 N个 OD分表全部分配到网络上„ 一般来说 N越大，增量分配法的结果就越接近平衡解，但计算工作量相应增加，况且非常大的 N值也不能完全保证结果一定满足 UE条件。

另一方面，当 N =1时，这个方法就是全有全无分配法‡ 实际工作中，可按 “先多后少 ”的原则将每组 OD量分成不等的 N份，随着迭代的进行每次加载的 OD量占原有总量的比例逐渐减少，这样改进后的算法相对于原算法在相同的 N值前提下能获得更接近于平衡解的结果N 1 2 3 4 5 6 7 8 9 10123451010060504030204030302520202020151015101010 5 5 5 5 5分配次数N与每次的OD量分配率（％）增量分配方法算法步骤例题10-2„ 令 N=2,求解下图网络中的增量分配结果„ 解： 第一次分配，q1=2.5,路段流量： x1=0 ,x2=2.5第一次分配后的路段阻抗：t1=2, t2=6第二次分配，q2=2.5,路段流量： x1=2.5 ,x2=2.5第二次分配后的路段阻抗：t1=4.5, t2=62221 xt +=112 xt +=5=q3、逐次平均分配法（了解）„ 逐次平均分配法是一种介于增量加载法和平衡分配法之间的一种迭代算法，其基本思路是不断调整已分配到各路段上的交通量而逐渐到达或接近平衡解„ 逐次平均分配法是一种简单实用但能最接近于平衡解的启发式算法，如果每次迭代中的步长严格按照一维最优搜索的结果取值，那么它就是 Frank-Wolfe算法。

3逐次平均分配法算法步骤10.2 随机分配方法„ UE模型的前提假设是所有出行者都拥有当前交通状态下可供选择路径的全部信息，并且具有相同的路径选择行为，均试图选择最短路径到达其目的地„ 但是在实际的出行过程中，出行者对路网状况及交通现状不可能完全了解，因此应该将出行者对路径阻抗的估计视为分布于出行者群体上的一个随机变量不同的出行者对最短路径的估计是不同的，对路径阻抗估计的随机性导致了路径选择的随机性„ 能够描述这种随机路径选择行为的交通流分配方法称为随机分配方法 与其相对应，前述提到的各类分配方法也称为 确定型分配方法 随机分配模型„ 基本假设：出行者从连接两 O、 D点的可行路径中，选择路径 k的概率为：„ 上述模型可以和任意确定型分配方法组合使用，构成随机分配方法∑⋅−⋅−=kttkkkeePθθ例题10-3„ 求解下图网络中的随机分配结果（θ =1）„ 解：路径1被选择的概率：p1=exp(-2)/(exp(-2)+exp(-1))=0.27路径2被选择的概率：p2=1-p1=0.73路径流量： x1=5x0.27=1.35, x2=5-1.35=3.65 (路段阻抗：t1=3.35, t2=8.3 )2221 xt +=112 xt +=5=q可行路径v.s. 有效路径„ 实际的交通网络中，任意两点之间的可行路径数量往往非常庞大，而只有少数路径才是实际出行者会考虑选择的路径，可以称这类路径为 “有效路径 ” 。

Dial算法„ Dial曾提出一个判别网络中有效路径的可行方法，目前在随机分配模型中被广泛采用 Dial算法用一个预处理过程来识别连接 OD的有效路径，而 OD量仅仅分配到这些有效路径而非所有路径上‡ 有效路段 ：当路段（ i， j）的上游端点 i比下游端点 j离起点 r近，而且 i比 j离终点 s远，则该路段为有效路段‡ 有效路径 ：如果连接 OD对的某条路径所包含的每条路段都是有效路段，则该路径是一条有效路径4Dial算法示例10.3 交通分配方法的选择高高较高低高精度可与前述任一方法组合使用拥挤效应显著的网络拥挤效应较显著的网络没有拥挤效应的网络拥挤效应显著的网络适用范围简单全有全无较简单增量分配复杂随机分配较简单逐次平均复杂平衡分配求解方法作业如图所示的交通网络，从A到B有两条路径1、2，两条路径上的交通阻抗函数分别为：路径1： t1=15+0.005x1 路径2： t2=10+0.02x2现从A到B有3000辆车，分别用以下方法进行交通流分配：（1）UE分配方法（2）全有全无分配方法（3）增量分配方法（OD三等分）4）随机分配方法（参数θ=0.1）2202.010 xt +=11005.015 xt +=3000=qAB本讲到此结束谢谢各位同学！。