第8章 交通流分配(三)

第4节用户均衡问题的解法1．Dijkstra法（记号确定法）该方法是从离起点最近的点开始，逐渐向全方位枚举出最短径路的方法。【记号】K:最短径路和最小费用已经确定的节点集合。K：最短径路尚未确定的局部最小费用节点集合。mF：最短径路的途径节点集合。jc：以o为起点的最小费用。【计算步骤】Step1设所有节点j的局部最小费用为jc或为足够大的值，并设KjFj,0。设o为起点，对节点o有ojco,0，将节点o移到集合K。Step2检查以节点i为起点的所有路段的终点m，若满足mimdcc，则令iFdccmmim,。Step3对最小费用尚未确定的节点集合K中的所有节点，按下式计算局部最小费用的最小值jc。Kppccppj:),(min。将节点j移到集合K。Step4如果pc以外的节点是否全部被移到集合K中，则结束计算。反之，令ji，返回Step2。【最短径路的枚举】利用jF枚举出任意节点j到起点o的最短径路：)()()()(bghjFfFgFhFj起点o【例题】用Dijkstra法计算下图从点1到其它节点的最短经路。156472322211113344689节点及节点号码路段及路段费用解：将计算过程列于下图和表，可以看出，到第７步为止，全部节点都被移到集合K中，结束计算。例如，从节点１到节点６的最短径路为：1)(4)(7)(6476FFF156472322211113344689表　　Dijkstra法的计算过程和结果路段各节点的mc局部最小径路mF最小费用节点计算顺序始点终点节点号码节点号码}{minppc1234567123456710∞∞∞∞∞∞00000001212，4，502∞49∞∞01011002323，4021049∞∞01211004445，7021048∞601214047573，6029487601714746665，7029487601714745754，60294876017147432.全有全无法（allornothingmethod）全有全无分配法是将OD交通需求沿最短经路一次分配到路网上去的方法，也被称为交通需求分配。顾名思义，全有（all）指将OD交通需求一次性地全部分配到最短径路上。全无（nothing）指对最短径路以外的径路不分配交通需求量。全有全无分配法应用于没有通行能力限制的网络交通交通量分配等场合。在美国芝加哥城交通解析中，首次获得应用。另外，后述增量分配法和均衡分配法中频繁使用。【分配计算步骤】Step1令0,0ijxn（始点i，终点j的路段交通量）。Step2搜索第n个起点到其余各点的最短径路，求出最短径路费用iocmin和iF。Step3按iocmin的相反顺序，用下式求出流入节点j并处于最短径路上的路段)(iFi→j间的交通量ijx。nsijnsnijnijtxx11nijx：分配到第1n个交通量发生点时，路段ij的交通量。1:交通量发生点n的OD对ns的最短径路经过路段ij时。nrsij,=0:交通量发生点n的OD对ns的最短径路不经过路段ij时。Step4如果n=N，则结束计算。反之，令n=n+1返回Step2。N为网络中交通量发生点的集合。3.增量分配法（Incrementalassignmentmethod）增量分配法时将OD交通需求量进行适当形式的分割（分割数、等分或不等分），然后用全有全无分配法，将分割后的OD交通需求量逐渐分配到网络上去。实际工作中，如何分割OD交通需求量是很重要的，一般多用5―10分割，并且采用不等分。【分配计算步骤】Step1根据需要，以适当的形式分割OD交通需求量，即rsnrsntt。令n=1，0nijx。Step2更新路段费用)(1nijijnijxcc。Step3用全有全无分配法将第n次分割OD交通需求量rsnt分配到最短经路上。Step4如果n=N，则结束计算。反之，令n=n+1返回Step2。N为分割次数。4.均衡分配（Frank-Wolfe）法Step1给出初始可能解kax，令0k。一般用前述全有全无分配法求解初始可能解。Step2更新路段费用函数)(kakaxc。Step3搜索目标函数的下降方向。用最短径路搜索法求出各OD间的最短径路，在用全有全无分配法求出探索方向kay。Step4一维搜索。将下式代入到目标函数中，求出最佳探索步长*。)(1kakakakaxyxxStep5收敛判定。设1和2为任意小数，若满足下式，则结束计算。反之，返回Step2。11)()(kakaAakakaccxx21/)(maxkakakaxxx【例题】设图示交通网络的OD交通需求量为200t辆，各径路的交通费用函数分别为：1110.05hc，22025.010hc，33025.015hc试用全有全无分配法、增量分配法和均衡分配法求出分配结果，并进行比较。径路3径路1D径路2解：1．全有全无分配法由路段费用函数可知，在路段交通量为零时，径路1最短。利用该方法的以下结果：15,10,2520010.05,0,200321321ccchhh因为，25,132ccc，所以，没有得到均衡解。目标函数：30000125.0150125.01005.05233222211hhhhhhZ２．增量分配法采用2等分。（1）第1次分配全有全无分配法相同，径路1最短。15,10,1510010.05,0,100321321ccchhh（２）第2次分配　最短径路变为径路25.12100025.010,1510010.05,0,100,10021321cchhh，153c这时，结果接近于均衡解。目标函数为：12510005005000125.0150125.01005.05233222211hhhhhhZ2125３．均衡分配法【模型】min2332222110125.0150125.01005.05hhhhhhZ..ts31200kkh)3,2,1(,0khk（1）用全有全无分配法求解初始可能解3000,15,10,2520010.05,0,200321030201Zccchhh。（2）求最佳搜索方向继续用全有全无分配法求解，得：0,200,0030201yyy（４）一维搜索,求最佳搜索步长*和交通量修正令618.06.123)0200(618.00,4.76)2000(618.02000211hh,013h15,09.136.123025.010,64.124.7610.05321ccc22200125.00156.1230125.06.123104.7605.04.765Z81.210096.190123685.291382（５）收敛判定设1=2=0.01。11)()(kakaAakakaccxx21/)(maxkakakaxxx显然，收敛条件得不到满足。返回（2）继续修正计算。这时的最短径路为径路1。所以，继续用全有全无分配法求解，得：0,0,200131211yyy0.120)6.1230(0291.06.123,0.80)4.76200(0291.04.762221hh023h22200125.00150.1200125.00.120100.8005.00.805Z0.21000.1801200320400求最佳探索步长*的方法：将)(1kakakakaxyxx代入目标函数中，得min10　Aaxyxakakakadwwc)(0)(这时，求满足下式的*即可。0)()(AakakanaakakaxyxcxyddZ【作业】将在交通方式划分中求出的公共汽车和汽车的OD交通量用全有全无分配法和增量分配法（３等分）分配到以下路网上去。路阻函数：1111.010)(xxt2221.015)(xxt3331.05)(xxt4441.05)(xxt5551.010)(xxt6661.015)(xxt1542321６34５发生吸引点公共汽车线路道路网络