交通流分配7

平衡分配的引出•1.问题•且每条路段上的运行时间t是流量v的函数•问，假设出行者对路径出行信息有清楚的了解，问OD量在路径1、2上如何分配才达到平衡，或者说达到最优？AB12Wardrop平衡原理•1.1952年著名学者Wardrop提出了交通网络平衡分配的第一、第二原理；•2.Wardrop第一原理•在道路的利用者都确切知道网络的交通状态并试图选择最短径路时，网络将会达到平衡状态。在考虑拥挤对行驶时间影响的网络中，当网络达到平衡状态时，每个OD对的各条被使用的路径具有相等而且最小的行驶时间，没有被使用的路径的行驶时间大于或等于最小行驶时间。Wardrop平衡原理•Wardrop第一原理，在实际交通流分配中也称为用户均衡（UserEquilibrium，UE）或用户最优•用户平衡说明不存在司机能单方面改变其路径能减少其出行时间Wardrop平衡原理•Wardrop第二原理，系统平衡条件下，拥挤的路网上交通流应该按照平均或总的出行成本最小为依据来分配。——系统最优原理（SystemOptimization，SO）•第一原理主要是建立每个道路利用者使其自身出行成本（时间）最小化的行为模型；反映了道路用户选择路线的一种准则，因此按照第一原理分配的结果应该是路网上用户实际径路选择的结果；•第二原理则是达到出行成本最小的系统平衡；反映了一种目标，即按照什么样的方式分配是最好的，第二原理为交通管理人员提供了一种决策方法UE平衡的简单的例子AB12UE定义：在平衡点，连接每个O－D对的所有被使用的路径有相同的阻抗，且小于或等于任何未被使用的路径阻抗。在平衡点，连接每个OD对的路径可以分成两类，一类路径上有流量，对应的路径阻抗是相等的；另一类路径上没有流量，其阻抗大于第一类路径的阻抗UE平衡分配和非平衡分配•设OD之间交通量为q＝2000辆，有两条路径a和b，路径a行驶时间短，但通行能力小，路径b行驶时间长，但通行能力大，假设各自的行驶时间（min）与流量的关系是：bbaaqtqt005.01502.010•1.UE平衡分配的结果•2.非平衡分配的结果：最短路径、容量限制－增量加载平衡分配理论的发展•1.1952年，Wardrop提出了道路网平衡的概念和定义•2.1956年，Beckmann提出了描述平衡交通流分配的数学规划模型•3.1975年，LeBlanc设计出了求解Beckmann模型的算法平衡分配理论在交通分配上占有重要的地位，大部分商业软件的交通分配程序都是平衡分配程序。平衡分配理论的书籍•1.YOSEFSHEFFI，UrbanTransportationNetworks:EquilibriumAnalysiswithMathematicalProgrammingMethods,Prentice-Hall,INC•2.黄海军，城市交通网络平衡分析——理论与实践，人民交通出版社，1994年平衡分配方法1.平衡分配模型2.平衡分配算法符号定义•N——网络节点的集合；•A——网络有向弧（即路段）的集合•R——产生出行量的起点集合，R∈N；•F——吸收出行量的终点集合，F∈N,F∩R不一定是空集•r——代表一个起点节点，r∈R；•s——代表一个终点节点，s∈F；•Krs——连接OD对rs的所有路径的集合；•qrs——所研究的时段内从r到s的交通需求量；•q——OD矩阵（qrs），r∈R，s∈F；符号定义•xa——在弧a上的交通流量，a∈A；•x——向量（…,xa,…），a∈A；•ta——弧a上的阻抗（时间），a∈A，ta＝ta（xa）；•t——向量（…,ta,…），a∈A；符号定义rskf•——O-D对r-s之间路径k上的流量，k∈Krs；•frs——向量（…,,…），k∈Krs；•f——向量（…,frs,…），r∈R，s∈F；•——O-D对r-s之间路径k上的阻抗，k∈Krs；•crs——向量（…,,…），k∈Krs；•c——向量（…,crs,…），r∈R，s∈F；rskfrskcrskc符号定义rska,——如果弧a在连接O-D对r-s的路径k上，其值为1；否则为零•△rs——矩阵（），a∈A，k∈Krs；•△——向量（…,△rs,…），r∈R，s∈F；rska,路段与路径之间的流量和阻抗之间的关系arskaarsktc,FsRrKkrs,,rskrskarskafx,AaDUE平衡的定义DUE定义：在平衡点，连接每个O－D对的所有被使用的路径有相同的阻抗，且小于或等于任何未被适用的路径阻抗。在平衡点，连接每个OD对的路径可以分成两类，一类路径上有流量，对应的路径阻抗是相等的；另一类路径上没有流量，其阻抗大于第一类路径的阻抗在网络处于DUE平衡时，司机不能简单的通过改变路径来减少出行时间，也就是说这时候从出行者角度来说，网络的出行时间时最小的。DUE问题的数学规划模型——beckmann交通平衡分配模型•目标函数axaadxxtxZ0)(min•约束条件srqfrskrsk,srkfrsk,,0afxrskrskarska,（1）（2）（3）（4）DUE问题的数学规划模型•目标函数（1）是所有弧阻抗函数积分的和；•约束（1）代表路径流量与OD流量之间的守恒关系；•约束（2）保证所有的路径流量一定是正值；•约束（3）是弧流量与路径流量之间的关联关系；•模型中有两个假设：弧阻抗仅仅是该弧流量的函数，与其它弧上的流量没有联系；弧阻抗是流量的严格增函数Beckmann模型与wardrop第一原理的一致性•如图所示，一个有两条径路（同时也是路段）、连接一个出发地和一个目的地的简单交通网络，两个路段的阻抗函数分别为：221121,2xtxtOD量为q＝5，分别求该网络的Beckmann模型的解和平衡状态的解Beckmann模型解的唯一性•当所有路段的阻抗函数是单调递增函数时，目标函数是严格凸的，所以beckmann模型有唯一的最小点，也就是说，当达到平衡是，分配到各路段上的流量是唯一的。系统最优公式(SO)•1.在UE规划中，每位司机只从自身利益出发去寻找最小阻抗的路径，司机之间互不协商，经过不断的系统内部调整后，达成一个平衡状态。•2.系统最优的原则假设司机能接收统一的调度，大家的共同目的是使系统的总的阻抗最小。系统最优公式（SO）•目标函数aaaaxtxxZ)()(min•约束条件srqfrskrsk,srkfrsk,,0afxrskrskarska,（1）（2）（3）（4）SO一阶条件的变量说明——为弧a对网络总阻抗的边际贡献；即——是当弧上流量为xa时，新增一个出行单位经该弧时遇到的阻抗；——新增的一个出行单位使该弧现有流量xa承担的额外阻抗；——是连接OD对子r－s的路径k对网络总阻抗的边际贡献；)(aaxtbbbbaaaxtxxxt)()()(aaxtaaaadxxdtx/)(rskc系统最优（SO）与用户最优（UE）•SO达到系统最优时，路径分为两类：一类路径上有流量，路径阻抗边际量总是互相等值的，另一类路径上没有流量，路径总阻抗边际值大于或等于第一类路径的阻抗边际量UE在平衡点，连接每个OD对的路径可以分成两类，一类路径上有流量，对应的路径阻抗是相等的；另一类路径上没有流量，其阻抗大于第一类路径的阻抗UE与SO之间的比较•1.当网络上略去拥挤效应时，UE和SO时相等的•2.如果在UE规划中令阻抗函数为，其解与SO的解相同；•3.当网络拥挤程度较低时，很小，UE与SO十分接近。•4.当网络上交通需求量较大时，拥挤产生，UE与SO的差别就很明显)(aaxtaaadxxdt)(UE与SO之间的比较•1.SO解通常不是UE解，但SO解是使网络总阻抗最小的一个可行解•2.UE解中司机独立行动，只关心寻找对自己有利的路径，•3.SO解中司机服从统一指挥，寻找对整体系统有利的路径，即司机之间存在协作。练习•已知网络结构如图所示，出行起终点为1和3，其OD量为4，网络中每个路段的路阻函数分别为:•求平衡分配时路段的流量2112xt223xt23321xt4442xt1231234DUE平衡分配模型的求解•1.DUE规划是一个非线性凸规划问题•目标函数是严格凸的，且是非线性的•约束是线性的•2.非线性规划模型即使现在也没有通用的解法，只是对某些特殊的模型才有可靠的解法，DUE模型就是一种特殊的非线性规划模型求解方法•1.采用Frank-Wolfe算法，算法要求是约束条件必须是线性的•2.实质是用线性规划逐步逼近非线性规划的方法；•3.步骤：•①在每步迭代中确定搜索方向，利用一个线性规划的最优解确定下一步的迭代方向•②确定搜索的最优步长，根据目标函数的一维极值问题求最优迭代步长Frank－wolfe算法求解Beckmann模型•1.已知迭代起点求决定下一步迭代方向线性规划问题•naXsrkgsrqgstytYZrskrskrskaanan,,,0,,.)(:min•该模型实际是在路段阻抗已知的情况下，使网络的总阻抗最小的交通流分配问题，即将OD交通量全部沿OD间的最短路径进行分配即可使目标函数最小化Frank－wolfe算法求解Beckmann模型•1.已知迭代起点求决定下一步迭代方向线性规划问题•naXsrkgsrqgstytYZrskrskrskaanan,,,0,,.)(:min•该模型实际是在路段阻抗已知的情况下，使网络的总阻抗最小的交通流分配问题，即将OD交通量全部沿OD间的最短路径进行分配即可使目标函数最小化Frank－wolfe算法求解Beckmann模型•2.确定第n次迭代时沿最速下降方向的最佳迭代步长anananaananaaxyxaxyxtxyZdtZnanana0)()(,0)()(:min)(0得：•由二分法求出迭代的步长λ，因此，下一步迭代的起点1nax)(1nanananaxyxx二分法•1.高等数学微积分知识：•求函数极小值，且函数连续可微，如果找到一个区间[a,b](ab)使且，则在啊a，b之间一定有一个的极小值点，使得•2.思路•取，若，则在区间[a,x0]中必有极小点，用[a,x0]代替区间[a,b]；•再取，若，则在区间[x0,x1]中必有极小点，用[x0,x1]代替区间[a,x0]•重复上述过程，缩小区间，直至区间的大小小于规定的精度，取该区间的中点为极值点，迭代结束)(x)(x0)(a0)(b)(x*x0)(*x2/)(0bax0)(0x)(x2/)(01xax0)(0x)(x平衡分配模型的算法•1.初始化，按照零流量进行全无全有分配，得到各路段的流量•2.更新各路段的阻抗：•3.寻找下一步的迭代方向，按照更新后的，进行一次全无全有分配，得到一组附加流量•4.确定迭代的步长，用二分法求满足下式的λ•5.确定新的迭代起点：•6.收敛性检验，主要是判断第n+1次计算出路段流量与第n次计算流量之差是否满足精度要求1;,1naxa令axttnaana),(atna,nayanananaananaxyxtxy0)()()(1nanananaxyxx随机平衡分配和动态交通流分配•1.随机平衡分配（SUE）与非平衡分配法中多路径分配法相似，在分配中主要考虑出行者在路径选择中的随机性因素，更符合实际情况•2.动态交通分主要用于智能交通系统，如出行者信息系统，车辆线路诱导系统等核心部分都需要动态交通流分配作为理论基础•3.动态交通流分布与静态交通流分布最主要的却别在于动态交通流分配需要考虑OD矩阵随时间变化的特征。