1、?10.1弹性需求下的平衡分配问题?10.2随机用户均衡交通分配模型?已学方法的特点:?(1)固定需求:OD需求不变。?(2)四阶段预测法:各阶段分别考虑,按步骤进行。?(3)正向预测:交通调查、土地利用、出行的生成、断面交通量。?实际:?(1)OD需求的变动:随时间,随交通状态等?(2)一体化预测组合模型?交通方式选择+交通流分配?交通分布+交通流分配?交通方式选择+交通分布+交通流分配?(3)短、平、快而经济的预测?观测断面(路段)交通量OD交通量?交通需求预测的其他模型?弹性需求分配模型?随机用户均衡交通分配模型?交通方式划分和交通流分配的组合模型?交通分布和交通流分配的组合模型?路段之
2、间相互影响的用户均衡配流模型?交通分布/方式分担/交通分配组合模型?超级网络模型?由路段交通量推算OD交通量的方法?弹性需求:OD交通量随道路的交通情况发生变化 OD交通量qrs可假定成r与s之间行驶时间trs的函数:?式中 urs r 与 s 之间的最短行驶时间;Drs r 与 s 之间的需求函数。?弹性需求分配问题:上述可变需求的分配问题?(1)模型公式?求一组满足 Wardrop 平衡原理的路段交通量和 OD 交通量,同时 OD 交通量也满足需求函数的问题则是弹性需求下的平衡分配问题。该问题可表达为下列模型:?式中,Drs-1:需求函数的反函数?与UE问题的差别:目标函数和新变量 qrs
3、?【例题 10-1】?网络中只有一条道路。设该道路的行驶时间函数(阻抗函数)为 t=1+x(x 是道路上的交通流量),OD 需求函数为 x=5-t。求该网络的平衡解。?分析:需求函数为 x=5-t 表明随着走行时间的增加交通需求量减少,阻抗函数t=1+x表明随着交通需求量的增加走行时间减少。?两条线的交点就是平衡点。x=2,t=3 tx230t=1+xD-1(x)=5-x?解:?根据阻抗函数t=1+x和OD需求函数为q=5-t列平衡分配方程:需求函数的反函数t=5-q,所以目标函数为:?即:?令dZ/dx=2x-4=0,得:x=2,t=3?由此可见,根据弹性需求模型求得的解是平衡解。2220.
4、550.54Zxxxxxx?(2)模型解的等价性证明?利用等价拉格朗日函数的一阶最优性条件说明。?库恩-塔克(Kuhn-Tucher)条件:?如果 ,那么 ,即 ,满足需求函数。?如果 ,那么 ,说明路线行驶时间太长,不能诱发任何OD量。?因此,模型的解满足均衡条件和需求函数(前两个库恩 -塔克条件就是UE均衡准则)。11()00()0()000rsrskkrsrskrsrsrsrsrsrsrsrsrskrsfcucuquDquDqfq?0?rsq)(1rsrsrsqDu?wsruDqrsrsrs?),()(,0?rsq)(1rsrsrsqDu?(3)模型求解方法(迭代法):与UE 模型基本相
5、同。?步骤1 初始化。设置一组初始可行的路段交通量 xa1,OD交通量qrs1,令n=1。?步骤2 更新行驶时间?步骤3 寻找下降方向。根据tan计算所有rs间的最小行驶时间ursn,确定附加OD交通量vrsn和附加路段交通量yrsn:?若 则 vrsn=(qrs上限),若 则vrsn=0;?将vrsn加载到所有最短径路上,得到 yan。?步骤4求最佳步长n*。解一维极值问题:?步骤5更新流量。?步骤6 收敛判断。如果下式满足,则停止计算;否则,令n=n+1,返回步骤2。?【例10-2】?用Frank-Wolfe算法求解下述弹性需求用户均衡交通分配问题。?Case1:令需求的上限等于4;?Ca
6、se2:令需求的上限等于5;?Case3:令需求的上限等于10;12t=1+xx=5-t?【解】Case1:令需求的上限等于4;?步骤1初始化,q1=x1=2,令n=1;?步骤2 更新行驶时间t1=1+x1=3和D-1(q1)=5-q1=3;?步骤3 寻找下降方向。?由于t1=D-1(q1),因此附加OD交通量v1=4;?使用0-1分配法将v1=4加载到网络中,得到y1=4;?步骤4 求最佳步长1?将 ,代入目标函数中,得:?这时,求满足dZ/d 1=0的1*,211111()22xxyx?211111()22qqvq?112 22 20001min(1)(5)Zdd?111111/1(22)
7、25(22)22(32)2(32)80dZ d?所以,1*=0?这时,交通量:?费用(时间):t=1+x=3?得到了平衡解。211111()222xxyx?211111()222qqvq?【解】Case2:令需求的上限等于5;?步骤1初始化,q1=x1=2;?步骤2 更新行驶时间t1=1+x1=3和D-1(q1)=5-q1=3;?步骤3 寻找下降方向。?由于t1=D-1(q1),因此附加OD交通量v1=5;?使用0-1分配法将v1=5加载到网络中,得到y1=5;?步骤4 求最佳步长1?将 ,代入目标函数中,得:?这时,求满足dZ/d 1=0的1*,211111()23xxyx?211111()
8、23qqvq?112 32 30001min(1)(5)Zdd?111111/1(23)35(23)33(33)3(3 3)180dZ d?所以,1*=0?更新交通量:?更新费用(时间):t2=1+x2=3,D-1(q1)=5-q2=3;?得到了平衡解。211111()232xxyx?211111()232qqvq?【解】,Case3:令需求的上限等于10;?步骤1初始化,q1=x1=2;?步骤2 更新行驶时间t1=1+x1=3和D-1(q1)=5-q1=3;?步骤3 寻找下降方向。?由于t1=D-1(q1),因此附加OD交通量v1=10;?使用0-1分配法将v1=5加载到网络中,得到y1=1
9、0;?步骤4 求最佳步长1?将 ,代入目标函数中,得:?这时,求满足dZ/d 1=0的1*,211111()28xxyx?211111()28qqvq?112 82 80001min(1)(5)Zdd?111111/1(28)85(28)88(38)3(3 8)1280dZ d?所以,1*=0?更新交通量:?更新费用(时间):t2=1+x2=3,D-1(q1)=5-q2=3;?得到了平衡解。211111()282xxyx?211111()282qqvq?网络变换法的基本思想:通过变换网络图,将弹性需求用户均衡配流问题转化为等价的固定需求用户均衡配流问题,然后可以直接利用 F-W算法进行求解。有
10、两种变换网络的方法:?零阻抗附加流量法?超量需求法?在基本网络基础上,增加两条路段和一个虚节点 r。两条路段分别是从r到r以及从s到r。令两条附加路段的行驶时间函数分别为?设从r到r的交通流量是固定的,等于从 r到s的需求上限 (例如取小区r的人口),成为固定需求的平衡分配问题,模型可表达为:?模型说明:?(1)由前面对附加路段的定义 ,以及网络的结构,决定了从基本网络流过的交通流量与路段 sr上的交通流量完全相同,即 。?可得,变换前后目标函数完全一致:?(2)对于固定需求 ,由于有 ,结合 和 可知必有 成立。因此从基本网络流过的流量为 ,剩余需求量 会转移到边 上。即原弹性需求的约束条件
11、在修改后的网络分配模型中完全满足。?(3)在变换后的网络模型的解点上,即平衡状态点上,有:如果从r到s的某条路径上有流量(即 ),则 ,从r到r的上下两条路径上应该有相等的阻抗,即有:,满足需求函数。?rsqrsaxarsxrsqrsaxarsxr rrsxr saxarsar rrsar rr sadDdtddDdtdtdtdtxz0100010000)()(0)()()()()()(min?rskrskqf?krsr rrskqxf0?r rxrsrsqq?rsq)(rsrsqq?),(rr0?rsq0?rsrsrrqqx)(0)(11rsrsrsrsrsrsrrqDuqDut?结论:通过
12、对基本网络的每一组OD增加2条虚拟边、1个虚节点之后,完全可以用固定需求均衡模型的解法求解弹性需求下的均衡分配问题。而固定需求下的均衡配流问题我们是熟悉的,如 F-W算法。?【例10-3】?用零阻抗附加流量法求解【例 10-1】中网络模型。?令需求的上限等于4;图10-1 例10-3网络变换示意图 12t=1+xx=5-t121t1t3t2=D-1t2=-D-1(x2)t1=1+x1 t3=0?【解】?根据图10-1建立用户均衡模型为:?1)用全有全无分配法求解初始可行解:?自由流状态下,t3=0、t1+t2=-4?(2)求最佳搜索方向 继续用全有全无分配法求解,得:120013min()(1
13、)(5)4.0(1,2,3)xxaz xddxxstxa?0001231234,0,5,1,0 xxxttt?0001230,4yyy?(3)求最佳步长*?将 代入目标函数中,得:?这时,求满足dZ/d =0的*:?所以,*=0.5 100011111000222210003333()44()44()4xxyxxxyxxxyx?4 44 40001min(1)(5)Zdd?/42(44)432160dZ d?这时,交通量:?费用(时间):?目标函数:?收敛判定:?所以,满足了Wardrop第一平衡原理 111123442,442,42xxx?123123,253,0ttt?2200220(1)
14、(5)4|4Zdd?1230ttt?弹性需求平衡分配模型的目标函数:?上式中第二项可分解成?由于右边第一项为常数,从目标函数中去掉对问题的求解没有影响。第二项可以对超量需求 进行积分变换。即令 ,原积分变量 w 从 至 ,则新积分变量 v 从 至零,有?其中 ,表示逆需求函数的扩展补函数。?由此,可变需求问题的等价规划模型可写成?模型中,只要定义一条载流ers的附加路段rs,其路段的阻抗函数为 ,构成超量需求路段网络,同样可以用固定需求下平衡模型的解法求解弹性需求下的平衡分配问题:图10-2 超量需求法网络变换示意图?【例10-4】?用超量需求法求解【例10-1】中网络模型(令需求的上限等于8
15、)。图10-3 例10-4网络示意图 12t=1+xx=5-t?【解】?如图10-3 所示,基本网络只有一个 OD 对和一条路段,路段阻抗函数是 t=1+x,x 为径路流量,也是 OD 需求量,需求函数为 x=5-t。?为需求设置一个上限 ,逆需求函数为 ,因 e=8-x,故超需求路段的阻抗函数为?代入可变需求问题的等价规划模型?积分并将 e 消去,得?显然,极小解为 x=2,和例题 10-1 所得结果相同。?当需求上限取4、5或20时,其解都是 x=2。因此,当需求上限取得足够大时,问题的解不受其值影响。但实践表明,需求上限的取值会影响求解效率,其值过大,会增加迭代次数,所以应尽量取小些。如
16、可令 ,其中 是零流径路阻抗值。?由于超量需求法所增加的虚拟路段比零阻抗附加流量法少一半,减少了计算工作量,因此可以认为超量需求法优于零阻抗附加流量法。源起:?第九章中的随机网络加载模型:将一组 OD分配到旅行时间固定不变的网络上(如 Dial算法、多路径交通分配模型等)。?考虑将均衡的概念引入到随机分配之中,探讨随机用户均衡交通分配问题,随机用户均衡分配简记为SUE(Stochastic User Equilibrium)。随机用户均衡的定义?SUE的概念最是早由Daganzo和Sheffi于1977年发展起来的。?SUE分配假设路线选择是基于感受的路段的旅行时间而不是量测出的时间(perc
17、eived travel time,感知出行时间),出行者感受的时间被认为是随机变量,在出行者中的分布是已知的。?对这些随机变量作不同的假设分布,可以获得不同的随机网络装载模型。(Gumblelogit;Normprobit)。?随机用户均衡定义为:当不存在出行者认为他能通过单方面改变出行路径来降低其阻抗时,达到了 SUE状态。?路段感知阻抗不仅作为随机变量,而且还要受到交通量的影响。?出行者的路径选择行为仍然遵守 Wardrop第一原理,只不过用户选择的是自己估计阻抗最小的路径。OD对 rs 之间的路径 k 被选择的概率实际上就是该路径的阻抗被估计为最小的概率。?SUE条件:?SUE比UE更
18、具一般性,事实上,UE是SUE的一种特殊情形。如果路段感知阻抗的方差为零,SUE就变成UE了。srkpqfrskrsrsk,?(二)优化模型:?式中,以各路段实际阻抗为条件的感知阻抗的数学期望,称为“期望感知阻抗”;?ckrs(X):(r,s)间各条径路的实际阻抗的向量,?Ckrs:(r,s)间第k条径路的感知阻抗。?模型与 SUE 条件的等价性?对于上述无约束极值问题,其极值点上的一阶条件为:。?Z(X)由三项组成,分别对其各项求关于 xa的偏导数。?对于第一项有:?由于 ,所以有:?对于第二项有:?对于第三项有:?因此,极值点的一阶条件为:?若路段阻抗是单调递增函数,即 dta/dxa0,
19、则 ,当且仅当:?注意到有:,所以有 。这正是 SUE 的条件。这就说明,模型与 SUE 条件是等价的。?由此得:?这也证明了模型满足非负约束和交通量守恒要求。?模型解的唯一性?可以证明,目标函数 Z(X)的海赛矩阵虽然是不确定阵(不定型阵),但是它在驻点附近是正定的,故驻点是该无约束极小化问题的一个局部极小点。问题是,Z(X)在全局范围内存在几个极小点,如果只有一个,那么该极小点就是最小点,即为唯一的最优解。?可以证明(过程从略,可参考刘灿齐 2001),Z(X)只有一个极小点,而且在该极小点附近是严格凸的,所以该局部极小点就是全局的极小点,解是唯一的。?迭代加权法(Method of Su
20、ccessive Averages)?步骤 1:初始化。基于 0 交通量的初始阻抗 进行 0-1 分配,得到路段交通量 。令迭代次数k=1。?步骤 2:更新各路段的阻抗,令?步骤 3:在新的阻抗的基础上,调用 Dial 算法进行交通量的随机加载,得到各路段的附加交通量?步骤 4:令?步骤 5:判别收敛判断条件:。?如果满足(是预先设定的精度值),则停止计算 ;否则,令 k=k+1,返回步骤 2。1(1/)(),kkkkaaaaxxkyxaA?【例10-5】?图示简单网络的OD需求交通量q=4,测得径路行驶时间分别为:t1=1+2x1 t2=2+x2?试使用优化模型,求网络平衡交通流。?【解】?
21、建立模型?式中,?即:?整理得:?因为,问题为无约束条件极值问题 12121122112200min:(,)4(),()(1 2)(2)(1 2)(2)xxZ x xS t xtxxxxxdd?0,min:()()()()axrsrsrsa aaar saaZ xq Scxx txtd?()min|()rsrsrsrskScxECcx?2212112212min:(,)4(),()0.5Z x xS t xtxxx?121122111111111(,)(),()42422820Z x xS t xtxdtxxtdxpxpx?对于x2,同样有:?联立方程得:解得:x1=1.75,x2=2.25,p1=0.438,p2=0.562 t1=4.5,t2=4.25 t1 t2 网络流为SUE,非UE 1222222(,)4140Z x xpxpxx?112212128204014pxpxppxx?目标函数Z=-9.1?作业10-1?分别用零阻抗附加流量法和超量需求法 求解下述弹性需求用户均衡交通分配问题(设定需求的上限为 8)。1212 121211uq?、115xt?、2223xt?作业10-2?使用优化模型对如下网络求解SUE流量解。DO1212000q?11200.005tx?22150.01tx?