资源描述
第 4 节 用户均衡问题的解法1 Dijkstra 法（记号确定法）该方法是从离起点最近的点开始，逐渐向全方位枚举出最短径路的方法。【记号】K:最短径路和最小费用已经确定的节点集合。K：最短径路尚未确定的局部最小费用节点集合。mF：最短径路的途径节点集合。jc：以 o 为起点的最小费用。【计算步骤】Step 1 设所有节点 j的局部最小费用为jc或为足够大的值，并设KjFj, 0。设 o 为起点，对节点 o 有ojco , 0，将节点 o 移到集合K。Step 2 检查以节点i为起点的所有路段的终点 m，若满足mimdcc，则令iFdccmmim,。Step 3 对最小费用尚未确定的节点集合K中的所有节点，按下式计算局部最小费用的最小值jc。Kppccppj:),(min。将节点j移到集合K。Step 4 如果pc以外的节点是否全部被移到集合K中，则结束计算。反之，令ji ，返回 Step 2。【最短径路的枚举】 利用jF枚举出任意节点j到起点 o 的最短径路：)()()()(bghjFfFgFhFj起点 o【例题】用 Dijkstra 法计算下图从点 1 到其它节点的最短经路。156472322211113344689节点及节点号码路段及路段费用解：将计算过程列于下图和表，可以看出，到第步为止，全部节点都被移到集合K中，结束计算。例如，从节点到节点的最短径路为： 1 )(4)(7)(6476FFF156472322211113344689表Dijkstra 法的计算过程和结果路段各节点的mc局部最小径路mF最小费用节点计算顺序始点终点节点号码节点号码minppc1234567123456710 00000001212，4，5024901011002323，402104901211004445，7021048601214047573，6029487601714746665，7029487601714745754，60294876017147432.全有全无法（all or nothing method）全有全无分配法是将 OD 交通需求沿最短经路一次分配到路网上去的方法，也被称为交通需求分配。顾名思义，全有（all）指将 OD 交通需求一次性地全部分配到最短径路上。全无（nothing）指对最短径路以外的径路不分配交通需求量。全有全无分配法应用于没有通行能力限制的网络交通交通量分配等场合。在美国芝加哥城交通解析中，首次获得应用。另外，后述增量分配法和均衡分配法中频繁使用。【分配计算步骤】Step 1 令0, 0ijxn（始点i，终点j的路段交通量） 。Step 2 搜索第 n 个起点到其余各点的最短径路，求出最短径路费用iocmin和iF。Step 3 按iocmin的相反顺序，用下式求出流入节点j并处于最短径路上的路段)(iFij间的交通量ijx。nsijnsnijnijtxx11nijx：分配到第1n个交通量发生点时，路段ij的交通量。1: 交通量发生点n的 OD 对ns的最短径路经过路段ij时。nrsij,=0: 交通量发生点n的 OD 对ns的最短径路不经过路段ij时。Step 4 如果 n=N，则结束计算。反之，令 n=n+1 返回 Step2。N 为网络中交通量发生点的集合。3.增量分配法（Incremental assignment method）增量分配法时将 OD 交通需求量进行适当形式的分割（分割数、等分或不等分） ，然后用全有全无分配法，将分割后的 OD 交通需求量逐渐分配到网络上去。实际工作中，如何分割 OD 交通需求量是很重要的，一般多用 510 分割，并且采用不等分。【分配计算步骤】Step 1 根据需要，以适当的形式分割 OD 交通需求量，即rsnrsntt。令 n=1，0nijx。Step 2 更新路段费用)(1nijijnijxcc。Step 3 用全有全无分配法将第 n 次分割 OD 交通需求量rsnt分配到最短经路上。Step 4 如果 n=N， 则结束计算。 反之， 令 n=n+1 返回 Step2。N 为分割次数。4.均衡分配（Frank-Wolfe）法Step 1 给出初始可能解 kax，令0k。一般用前述全有全无分配法求解初始可能解。Step 2 更新路段费用函数)(kakaxc。Step 3 搜索目标函数的下降方向。用最短径路搜索法求出各 OD 间的最短径路，在用全有全无分配法求出探索方向 kay。Step 4 一维搜索。将下式代入到目标函数中，求出最佳探索步长*。)(1kakakakaxyxxStep 5 收敛判定。设1和2为任意小数，若满足下式，则结束计算。反之，返回 Step 2。11)()(kakaAakakaccxx21/ )(maxkakakaxxx【例题】设图示交通网络的 OD 交通需求量为200t辆，各径路的交通费用函数分别为：1110. 05hc，22025. 010hc，33025. 015hc试用全有全无分配法、增量分配法和均衡分配法求出分配结果，并进行比较。径路3径路1D径路2解：1 全有全无分配法 由路段费用函数可知，在路段交通量为零时，径路 1最短。利用该方法的以下结果：15,10,2520010. 05, 0,200321321ccchhh因为，25,132 ccc，所以，没有得到均衡解。目标函数：30000125. 0150125. 01005. 05233222211hhhhhhZ 增量分配法采用 2 等分。（1） 第 1 次分配全有全无分配法相同，径路 1 最短。15,10,1510010. 05, 0,100321321ccchhh（）第 2 次分配最短径路变为径路 25 .12100025. 010,1510010. 05, 0,100,10021321cchhh，153c这时，结果接近于均衡解。目标函数为：12510005005000125. 0150125. 01005. 05233222211hhhhhhZ2125 均衡分配法【模型】min 2332222110125. 0150125. 01005. 05hhhhhhZ. .ts 31200kkh) 3 , 2 , 1( , 0khk（1） 用全有全无分配法求解初始可能解3000,15,10,2520010. 05, 0,200321030201Zccchhh。（2） 求最佳搜索方向继续用全有全无分配法求解，得：0,200, 0030201yyy（）一维搜索,求最佳搜索步长*和交通量修正令618. 06 .123)0200(618. 00, 4 .76)2000(618. 02000211hh,013h15,09.136 .123025. 010,64.124 .7610. 05321ccc22200125. 00156 .1230125. 06 .123104 .7605. 04 .765Z81.210096.190123685.291382（） 收敛判定设1=2=0.01。11)()(kakaAakakaccxx21/)(maxkakakaxxx显然，收敛条件得不到满足。返回（2）继续修正计算。这时的最短径路为径路 1。所以，继续用全有全无分配法求解，得：0, 0,200131211yyy0 .120)6 .1230(0291. 06 .123, 0 .80)4 .76200(0291. 04 .762221hh023h22200125. 00150 .1200125. 00 .120100 .8005. 00 .805Z0 .21000 .1801200320400求最佳探索步长*的方法：将)(1kakakakaxyxx代入目标函数中，得min10Aaxyxakakakadwwc)(0)(这时，求满足下式的*即可。0)()(AakakanaakakaxyxcxyddZ【作业】将在交通方式划分中求出的公共汽车和汽车的 OD 交通量用全有全无分配法和增量分配法（等分）分配到以下路网上去。路阻函数：1111 . 010)(xxt2221 . 015)(xxt3331 . 05)(xxt4441 . 05)(xxt5551 . 010)(xxt6661 . 015)(xxt154232134发生吸引点公共汽车线路道路网络
展开阅读全文