第十章均衡交通分配模型的扩展课件.ppt

?,10.1,弹性需求下的平衡分配问题,?,10.2,随机用户均衡交通分配模型,?,已学方法的特点：,?,(1),固定需求：,OD,需求不变。,?,(2),四阶段预测法：各阶段分别考虑，按步骤进行。,?,(3),正向预测：交通调查、土地利用、出行的生成、断面交,通量。,?,实际：,?,(1)OD,需求的变动：随时间，随交通状态等,?,(2),一体化预测组合模型,?,交通方式选择,+,交通流分配,?,交通分布,+,交通流分配,?,交通方式选择,+,交通分布,+,交通流分配,?,(3),短、平、快而经济的预测,?,观测断面,(,路段,),交通量,OD,交通量,?,交通需求预测的其他模型,?,弹性需求分配模型,?,随机用户均衡交通分配模型,?,交通方式划分和交通流分配的组合模型,?,交通分布和交通流分配的组合模型,?,路段之间相互影响的用户均衡配流模型,?,交通分布,/,方式分担,/,交通分配组合模型,?,超级网络模型,?,由路段交通量推算,OD,交通量的方法,?,弹性需求,:OD,交通量随道路的交通情况发生变化,OD,交通量,q,rs,可假定成,r,与,s,之间行驶时间,t,rs,的函数：,?,式中,u,rs,r,与,s,之间的最短行驶时间；,D,rs,r,与,s,之间的需求函数。,?,弹性需求分配问题,:,上述可变需求的分配问题,?,（,1,）模型公式,?,求一组满足,Wardrop,平衡原理的路段交通量和,OD,交通量，,同时,OD,交通量也满足需求函数的问题则是弹性需求下的,平衡分配问题。该问题可表达为下列模型：,?,式中，,D,rs,-,1,：,需求函数的反函数,?,与,UE,问题的差别：目标函数和新变量,q,rs,?,【,例题,10-1,】,?,网络中只有一条道路。设该道路的行驶时间函数（阻抗函,数）为,t,=1+,x,（,x,是道路上的交通流量），,OD,需求函数,为,x,=5-,t,。求该网络的平衡解。,?,分析：需求函数为,x,=5-,t,表明随着走行时间的增加交通需,求量减少，阻抗函数,t,=1+,x,表明随着交通需求量的增加走行,时间减少。,?,两条线的交点就是平衡点。,x,=2,t,=3,t,x,2,3,0,t=,1,+x,D,-1,(,x,),=5-x,?,解：,?,根据阻抗函数,t,=1+,x,和,OD,需求函数为,q,=5-,t,列平衡分配方程：,需求函数的反函数,t,=5-,q,，所以目标函数为：,?,即：,?,令,dZ,/,dx,=2,x,-4=0,得：,x,=2,t,=3,?,由此可见，根据弹性需求模型求得的解是平衡解。,2,2,2,0.5,5,0.5,4,Z,x,x,x,x,x,x,?,?,?,?,?,?,(2),模型解的等价性证明,?,利用等价拉格朗日函数的一阶最优性条件说明。,?,库恩,-,塔克（,Kuhn-Tucher,）条件,:,?,如果,，那么,，即,，,满足需求函数。,?,如果,，那么,，说明路线行驶时间太长，不能,诱发任何,OD,量。,?,因此，模型的解满足均衡条件和需求函数（前两个库恩,-,塔克条,件就是,UE,均衡准则）。,1,1,(,),0,0,(,),0,(,),0,0,0,rs,rs,k,k,rs,rs,k,rs,rs,rs,rs,rs,rs,rs,rs,rs,k,rs,f,c,u,c,u,q,u,D,q,u,D,q,f,q,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,0,?,rs,q,),(,1,rs,rs,rs,q,D,u,?,?,w,s,r,u,D,q,rs,rs,rs,?,?,?,),(,),(,，,0,?,rs,q,),(,1,rs,rs,rs,q,D,u,?,?,?,（,3,）,模型求解方法,(,迭代法,):,与,UE,模型基本相同。,?,步骤,1,初始化。设置一组初始可行的路段交通量,x,a,1,，,OD,交通量,q,rs,1,，令,n,=1,。,?,步骤,2,更新行驶时间,?,步骤,3,寻找下降方向。根据,t,a,n,计算所有,rs,间的最小行驶时,间,u,rs,n,，确定附加,OD,交通量,v,rs,n,和附加路段交通量,y,rs,n,：,?,若,则,v,rs,n,=,（,q,rs,上限），若,则,v,rs,n,=0,；,?,将,v,rs,n,加载到所有最短径路上，得到,y,a,n,。,?,步骤,4,求最佳步长,n,*,。解一维极值问题：,?,步骤,5,更新流量。,?,步骤,6,收敛判断。如果下式满足，则停止计算；否则，令,n,=,n,+1,，返回步骤,2,。,?,【例,10-2,】,?,用,Frank-Wolfe,算法求解下述弹性需求用户均衡交通分配问题。,?,Case1,：令需求的上限等于,4,；,?,Case2,：令需求的上限等于,5,；,?,Case3,：令需求的上限等于,10,；,1,2,t=1+x,x=5-t,?,【,解,】,Case1,：令需求的上限等于,4,；,?,步骤,1,初始化，,q,1,=,x,1,=2,令,n,=1,；,?,步骤,2,更新行驶时间,t,1,=1+,x,1,=3,和,D,-1,(,q,1,),=5-,q,1,=3;,?,步骤,3,寻找下降方向。,?,由于,t,1,=D,-1,(,q,1,),，因此附加,OD,交通量,v,1,=4,；,?,使用,0-1,分配法将,v,1,=4,加载到网络中，得到,y,1,=4,；,?,步骤,4,求最佳步长,1,?,将,代入目标函数,中，得,：,?,这时，求满足,dZ,/,d,1,=0,的,1,*,，,2,1,1,1,1,1,(,),2,2,x,x,y,x,?,?,?,?,?,?,?,2,1,1,1,1,1,(,),2,2,q,q,v,q,?,?,?,?,?,?,?,1,1,2,2,2,2,0,0,0,1,min,(1,),(5,),Z,d,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,1,1,1,1,1,1,/,1,(2,2,),2,5,(2,2,),2,2(3,2,),2(3,2,),8,0,dZ,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,所以，,1,*,=0,?,这时，交通量：,?,费用（时间）：,t,=1+,x,=3,?,得到了平衡解。,2,1,1,1,1,1,(,),2,2,2,x,x,y,x,?,?,?,?,?,?,?,?,2,1,1,1,1,1,(,),2,2,2,q,q,v,q,?,?,?,?,?,?,?,?,?,【,解,】,Case2,：令需求的上限等于,5,；,?,步骤,1,初始化，,q,1,=,x,1,=2,；,?,步骤,2,更新行驶时间,t,1,=1+,x,1,=3,和,D,-1,(,q,1,),=5-,q,1,=3;,?,步骤,3,寻找下降方向。,?,由于,t,1,=D,-1,(,q,1,),，因此附加,OD,交通量,v,1,=5,；,?,使用,0-1,分配法将,v,1,=5,加载到网络中，得到,y,1,=5,；,?,步骤,4,求最佳步长,1,?,将,代入目标函数,中，得,：,?,这时，求满足,dZ,/,d,1,=0,的,1,*,，,2,1,1,1,1,1,(,),2,3,x,x,y,x,?,?,?,?,?,?,?,2,1,1,1,1,1,(,),2,3,q,q,v,q,?,?,?,?,?,?,?,1,1,2,3,2,3,0,0,0,1,min,(1,),(5,),Z,d,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,1,1,1,1,1,1,/,1,(2,3,),3,5,(2,3,),3,3(3,3,),3(3,3,),18,0,dZ,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,所以，,1,*,=0,?,更新交通量：,?,更新,费用（时间）：,t,2,=1+,x,2,=3,D,-1,(,q,1,),=5-,q,2,=3;,?,得到了平衡解。,2,1,1,1,1,1,(,),2,3,2,x,x,y,x,?,?,?,?,?,?,?,?,2,1,1,1,1,1,(,),2,3,2,q,q,v,q,?,?,?,?,?,?,?,?,?,【,解,】,Case3,：令需求的上限等于,10,；,?,步骤,1,初始化，,q,1,=,x,1,=2,；,?,步骤,2,更新行驶时间,t,1,=1+,x,1,=3,和,D,-1,(,q,1,),=5-,q,1,=3;,?,步骤,3,寻找下降方向。,?,由于,t,1,=D,-1,(,q,1,),，因此附加,OD,交通量,v,1,=10,；,?,使用,0-1,分配法将,v,1,=5,加载到网络中，得到,y,1,=10,；,?,步骤,4,求最佳步长,1,?,将,代入目标函数,中，得,：,?,这时，求满足,dZ,/,d,1,=0,的,1,*,，,2,1,1,1,1,1,(,),2,8,x,x,y,x,?,?,?,?,?,?,?,2,1,1,1,1,1,(,),2,8,q,q,v,q,?,?,?,?,?,?,?,1,1,2,8,2,8,0,0,0,1,min,(1,),(5,),Z,d,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,1,1,1,1,1,1,/,1,(2,8,),8,5,(2,8,),8,8(3,8,),3(3,8,),128,0,dZ,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,所以，,1,*,=0,?,更新交通量：,?,更新,费用（时间）：,t,2,=1+,x,2,=3,D,-1,(,q,1,),=5-,q,2,=3;,?,得到了平衡解。,2,1,1,1,1,1,(,),2,8,2,x,x,y,x,?,?,?,?,?,?,?,?,2,1,1,1,1,1,(,),2,8,2,q,q,v,q,?,?,?,?,?,?,?,?,?,网络变换法的基本思想：通过变换网络图，将弹性,需求用户均衡配流问题转化为等价的固定需求用户,均衡配流问题，然后可以直接利用,F-W,算法进行求,解。有两种变换网络的方法：,?,零阻抗附加流量法,?,超量需求法,?,在基本网络基础上，增加两条路段和一个虚节点,r,。,两条路段分别是从,r,到,r,以及从,s,到,r,。令两条附加路,段的行驶时间函数分别为,?,设从,r,到,r,的交通流量是固定的，等于从,r,到,s,的需求上限,（例如取小区,r,的人口），成为固定需求的平衡分配问题，,模型可表达为,:,?,模型说明：,?,（,1,）由前面对附加路段的定义,以及,网络的结构，决定了从基本网络流过的交通流量与路段,sr,上,的交通流量完全相同，即,。,?,可得，变换前后目标函数完全一致：,?,（,2,）对于固定需求,，由于有,，结合,和,可知必有,成立。因此从基本网络流过的流,量为,，剩余需求量,会转移到边,上。即原弹,性需求的约束条件在修改后的网络分配模型中完全满足。,?,（,3,）在变换后的网络模型的解点上，即平衡状态点上，,有：如果从,r,到,s,的某条路径上有流量（即,），,则,，,从,r,到,r,的上下两条路径上应该有相等,的阻抗，即有：,，满,足需求函数。,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,rs,q,rs,a,x,a,rs,x,rs,q,rs,a,x,a,rs,x,r,r,rs,x,r,s,a,x,a,rs,a,r,r,rs,a,r,r,r,s,a,d,D,d,t,d,d,D,d,t,d,t,d,t,d,t,x,z,0,1,0,0,0,1,0,0,0,0,),(,),(,0,),(,),(,),(,),(,),(,),(,min,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,rs,k,rs,k,q,f,?,?,?,?,?,?,k,rs,r,r,rs,k,q,x,f,0,?,?,r,r,x,rs,rs,q,q,?,rs,q,),(,rs,rs,q,q,?,),(,r,r,0,?,rs,q,0,?,?,?,rs,rs,rr,q,q,x,),(,0,),(,1,1,rs,rs,rs,rs,rs,rs,rr,q,D,u,q,D,u,t,?,?,?,?,?,?,?,?,?,结论：通过对基本网络的每一组,OD,增加,2,条虚拟边、,1,个虚节点之后，完全可以用固定需求均衡模型的,解法求解弹性需求下的均衡分配问题。而固定需求,下的均衡配流问题我们是熟悉的，如,F-W,算法。,?,【例,10-3,】,?,用零阻抗附加流量法求解【例,10-1,】中网络模型。,?,令需求的上限等于,4,；,图,10-1,例,10-3,网络变换示意图,1,2,t=1+x,x=5-t,1,2,1,t,1,t,3,t,2,=D,-1,t,2,=-,D,-1,(,x,2,),t,1,=1+,x,1,t,3,=0,?,【,解,】,?,根据图,10-1,建立用户均衡模型为：,?,1,）,用全有全无分配法求解初始可行解：,?,自由流状态下，,t,3,=0,、,t,1,+,t,2,=-4,?,（,2,）,求最佳搜索方向,继续用全有全无分配法求解，得：,1,2,0,0,1,3,min,(,),(1,),(,5),4,.,0,(,1,2,3),x,x,a,z,x,d,d,x,x,s,t,x,a,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,0,0,0,1,2,3,1,2,3,4,0,5,1,0,x,x,x,t,t,t,?,?,?,?,?,?,?,0,0,0,1,2,3,0,4,y,y,y,?,?,?,?,(3),求最佳步长,*,?,将,代入目标函数中，得,：,?,这时，求满足,dZ,/,d,=0,的,*,：,?,所以，,*,=0.5,1,0,0,0,1,1,1,1,1,0,0,0,2,2,2,2,1,0,0,0,3,3,3,3,(,),4,4,(,),4,4,(,),4,x,x,y,x,x,x,y,x,x,x,y,x,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,4,4,4,4,0,0,0,1,min,(1,),(,5),Z,d,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,/,42(4,4,),4,32,16,0,dZ,d,?,?,?,?,?,?,?,?,?,?,?,这时，交通量：,?,费用（时间）：,?,目标函数：,?,收敛判定：,?,所以，满足了,Wardrop,第一平衡原理,1,1,1,1,2,3,4,4,2,4,4,2,4,2,x,x,x,?,?,?,?,?,?,?,?,?,?,?,1,2,3,1,2,3,2,5,3,0,t,t,t,?,?,?,?,?,?,?,?,2,2,0,0,2,2,0,(1,),(,5),4,|,4,Z,d,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,1,2,3,0,t,t,t,?,?,?,?,弹性需求平衡分配模型的目标函数：,?,上式中第二项可分解成,?,由于右边第一项为常数，从目标函数中去掉对问题的求解没有影响。,第二项可以对超量需求,进行积分变换。即,令,，原积分变量,w,从,至,，则新积分变量,v,从,至零，有,?,其中,，,表示逆需求函数的扩展补函数。,?,由此，可变需求问题的等价规划模型可写成,?,模型中，只要定义一条载流,e,rs,的附加路段,rs,，其路,段的阻抗函数为,，构成超量需求路,段网络，同样可以用固定需求下平衡模型的解法求,解弹性需求下的平衡分配问题：,图,10-2,超量需求法网络变换示意图,?,【例,10-4,】,?,用超量需求法求解【例,10-1,】中网络模型,(,令需求的上限等,于,8),。,图,10-3,例,10-4,网络示意图,1,2,t=1+x,x=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,。因此，,当需求上限取得足够大时，问题的解不受其值影响。,但实践表明，需求上限的取值会影响求解效率，其,值过大，会增加迭代次数，所以应尽量取小些。如,可令,，其中,是零流径路阻抗值。,?,由于超量需求法所增加的虚拟路段比零阻抗附加流量法少一半，,减少了计算工作量，因此可以认为超量需求法优于零阻抗附加流,量法。,源起：,?,第九章中的随机网络加载模型：将一组,OD,分配到旅,行时间固定不变的网络上（如,Dial,算法、多路径交通,分配模型等）。,?,考虑将均衡的概念引入到随机分配之中，探讨随机,用户均衡交通分配问题，随机用户均衡分配简记为,SUE,（,Stochastic User Equilibrium,）。,随机用户均衡的定义,?,SUE,的概念最是早由,Daganzo,和,Sheffi,于,1977,年发展起来的。,?,SUE,分配假设路线选择是基于感受的路段的旅行时间而不是量,测出的时间（,perceived travel time,，感知出行时间），出行者感,受的时间被认为是随机变量，在出行者中的分布是已知的。,?,对这些随机变量作不同的假设分布，可以获得不同的随机网络,装载模型。（,Gumblelogit,；,Normprobit,）。,?,随机用户均衡定义为：当不存在出行者认为他能通过单方面改,变出行路径来降低其阻抗时，达到了,SUE,状态。,?,路段感知阻抗不仅作为随机变量，而且还要受到交通量的影响。,?,出行者的路径选择行为仍然遵守,Wardrop,第一原理，只不过用户,选择的是自己估计阻抗最小的路径。,OD,对,rs,之间的路径,k,被选,择的概率实际上就是该路径的阻抗被估计为最小的概率。,?,SUE,条件：,?,SUE,比,UE,更具一般性，事实上，,UE,是,SUE,的一种特殊情形。如,果路段感知阻抗的方差为零，,SUE,就变成,UE,了。,s,r,k,p,q,f,rs,k,rs,rs,k,?,?,?,(,二,),优化模型：,?,式中，,以各路段实际阻抗为条件的感知,阻抗的数学期望，称为,“,期望感知阻抗,”,；,?,c,k,rs,(,X,),：,(,r,s,),间各条径路的实际阻抗的向量，,?,C,k,rs,：,(,r,s,),间第,k,条径路的感知阻抗。,?,模型与,SUE,条件的等价性,?,对于上述无约束极值问题，其极值点上的一阶条件,为：,。,?,Z,(,X,),由三项组成，分别对其各项求关于,x,a,的偏导数。,?,对于第一项有：,?,由于,，所以有：,?,对于第二项有：,?,对于第三项有：,?,因此，极值点的一阶条件为：,?,若路段阻抗是单调递增函数，即,dt,a,/,dx,a,0,，则,，当,且仅当：,?,注意到有：,，所以有,。这正是,SUE,的条件。这就说明，模型与,SUE,条件是等价的。,?,由此得：,?,这也证明了模型满足非负约束和交通量守恒要求。,?,模型解的唯一性,?,可以证明，目标函数,Z,(,X,),的海赛矩阵虽然是不确定阵（不,定型阵），但是它在驻点附近是正定的，故驻点是该无约,束极小化问题的一个局部极小点。问题是，,Z,(,X,),在全局范,围内存在几个极小点，如果只有一个，那么该极小点就是,最小点，即为唯一的最优解。,?,可以证明,（过程从略，可参考刘灿齐,2001,）,，,Z,(,X,),只有,一个极小点，而且在该极小点附近是严格凸的，所以该局,部极小点就是全局的极小点，解是唯一的。,?,迭代加权法（,Method of Successive Averages,）,?,步骤,1,：,初始化。基于,0,交通量的初始阻抗,进行,0-1,分配，得到路段交通量,。令迭代次数,k,=1,。,?,步骤,2,：更新各路段的阻抗,，令,?,步骤,3,：在新的阻抗的基础上，调用,Dial,算法进行交通量,的随机加载，得到各路段的附加交通量,?,步骤,4,：令,?,步骤,5,：判别收敛判断条件：,。,?,如果满足,（,是预先设定的精度值），则停止计算,；,否则，,令,k,=,k,+1,，返回步骤,2,。,1,(1/,)(,),k,k,k,k,a,a,a,a,x,x,k,y,x,a,A,?,?,?,?,?,?,?,【例,10-5,】,?,图示简单网络的,OD,需求交通量,q,=4,测得径路行驶时间分,别为：,t,1,=1+2,x,1,t,2,=2+,x,2,?,试使用优化模型，求网络平衡交通流。,?,【解】,?,建立模型,?,式中，,?,即：,?,整理得：,?,因为，问题为无约束条件极值问题,1,2,1,2,1,1,2,2,1,1,2,2,0,0,min,:,(,),4,(,),(,),(1,2,),(2,),(1,2,),(2,),x,x,Z,x,x,S,t,x,t,x,x,x,x,x,d,d,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,0,min,:,(,),(,),(,),(,),a,x,rs,rs,rs,a,a,a,a,r,s,a,a,Z,x,q,S,c,x,x,t,x,t,d,?,?,?,?,?,?,?,?,?,?,(,),min,|,(,),rs,rs,rs,rs,k,S,c,x,E,C,c,x,?,2,2,1,2,1,1,2,2,1,2,min,:,(,),4,(,),(,),0.5,Z,x,x,S,t,x,t,x,x,x,?,?,?,?,1,2,1,1,2,2,1,1,1,1,1,1,1,1,1,(,),(,),(,),4,2,4,2,2,8,2,0,Z,x,x,S,t,x,t,x,dt,x,x,t,dx,p,x,p,x,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,对于,x,2,，同样有：,?,联立方程得：,解得：,x,1,=1.75,x,2,=2.25,p,1,=0.438,p,2,=0.562,t,1,=4.5,t,2,=4.25,t,1,t,2,网络流为,SUE,，非,UE,1,2,2,2,2,2,2,(,),4,1,4,0,Z,x,x,p,x,p,x,x,?,?,?,?,?,?,?,?,?,?,1,1,2,2,1,2,1,2,8,2,0,4,0,1,4,p,x,p,x,p,p,x,x,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,?,目标函数,Z,=-9.1,?,作业,10-1,?,分别用,零阻抗附加流量法和超量需求法,求解下述弹性,需求用户均衡交通分配问题（设定需求的上限为,8,）。,1,2,1,2,12,12,11,u,q,?,?,、,1,1,5,x,t,?,?,、,2,2,2,3,x,t,?,?,?,作业,10-2,?,使用优化模型对如下网络求解,SUE,流量解。,D,O,1,2,1,2000,q,?,1,1,20,0.005,t,x,?,?,2,2,15,0.01,t,x,?,?,