第4节用户均衡问题的解法 1. Dijkstra法(记号确定法) 该方法是从离起点最近的点开始,逐渐向全方位枚举 出最短径路的方法。 【记号】 K:最短径路和最小费用已经确定的节点集合。 k:最短径路尚未确定的局部最小费用节点集合 最短径路的途径节点集 j:以o为起点的最小费用
第 4 节 用户均衡问题的解法 1． Dijkstra 法（记号确定法） 该方法是从离起点最近的点开始，逐渐向全方位枚举 出最短径路的方法。 【记号】 K :最短径路和最小费用已经确定的节点集合。 − K ：最短径路尚未确定的局部最小费用节点集合。 Fm ：最短径路的途径节点集合。 j c ：以 o 为起点的最小费用
【计算步骤】 Step1设所有节点的局部最小费用为c=或为足够 大的值,并设F=0,∈K 设o为起点,对节点o有∽=0,j=0,将节点o移 到集合K Step2检查以节点为起点的所有路段的终点四m},若满 足Cn >c.+ 则令Cm=C1+dm,F
【计算步骤】 Step 1 设所有节点j 的局部最小费用为c j = 或为足够 大的值，并设 − Fj = 0, j K 。 设 o 为起点，对节点 o 有co = 0, j = o ，将节点 o 移 到集合K 。 Step 2 检查以节点 i 为起点的所有路段的终点m ，若满 足 m i d m c c + ，则令c c d F i m = i + m , m =
Step3对最小费用尚未确定的节点集合k中的所有节 点,按下式计算局部最小费用的最小值C。 c=min(cn),{p:P∈K 将节点/移到集合K Step4如果cp=∞以外的节点是否全部被移到集合K 中,则结束计算。反之,令i=j,返回Step2 【最短径路的枚举】 利用F枚举出任意节点到起点o的最短径路 j→(F=→(F=)→(F8=)→…→(F=)起点o
Step 3 对最小费用尚未确定的节点集合 − K 中的所有节 点，按下式计算局部最小费用的最小值 j c 。 = − c c p p p K p j min( ), : 。 将节点 j 移到集合K 。 Step 4 如 果c p = 以外的节点是否全部被移到集合K 中，则结束计算。反之，令i = j ，返回 Step 2。 【最短径路的枚举】 利用Fj 枚举出任意节点 j 到起点 o 的最短径路： ( =) ( =) ( =) ( =) j h g Fb j F h F g F f 起点 o
【例题】用 Di jkstra法计算下图从点1到其它节点的最 短经路 节点及节点号码 路段及路段费用
【例题】用 Dijkstra 法计算下图从点 1 到其它节点的最 短经路。 1 56 4 7 23 2 2 2 1 1 1 1 3 3 4 4 6 8 9 节点及节点号码 路段及路段费用
解:将计算过程列于下图和表,可以看出,到第7步为 止,全部节点都被移到集合K中,结束计算。例如, 从节点1到节点6的最短径路为: 6→(F6=)7→(F7=4→(F4
解：将计算过程列于下图和表，可以看出，到第７步为 止，全部节点都被移到集合K 中，结束计算。例如， 从节点１到节点６的最短径路为： 6 (F6 =)7 (F7 =)4 (F4 =)1 1 56 4 7 23 2 2 2 1 1 1 1 3 3 4 4 6 8 9
表 Di jkstra法的计算过程和结果 计路段 各节点的 局部最小径路m 最小费用节点 算 顺「始终点 节点号码 节点号码 mn ic,i 2345671234567 ∞0000000 000 0 1049 00 445,7021048 60121404 573,602948760171474 665,70|2|948760171474 47653 4,602948
表 Dijkstra 法的计算过程和结果 路段 各节点的m 计 c 局部最小径路Fm 最小费用节点 算 顺 序 始 点 终点 节点号码 节点号码 min { }p p c 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 0 ∞ ∞ ∞ ∞ ∞ ∞ 0 0 0 0 0 0 0 1 2 1 2，4，5 0 2 ∞ 4 9 ∞ ∞ 0 1 0 1 1 0 0 2 3 2 3，4 0 2 10 4 9 ∞ ∞ 0 1 2 1 1 0 0 4 4 4 5，7 0 2 10 4 8 ∞ 6 0 1 2 1 4 0 4 7 5 7 3，6 0 2 9 4 8 7 6 0 1 7 1 4 7 4 6 6 6 5，7 0 2 9 4 8 7 6 0 1 7 1 4 7 4 5 7 5 4，6 0 2 9 4 8 7 6 0 1 7 1 4 7 4 3
2全有全无法( all or nothing method) 全有全无分配法是将OD交通需求沿最短经路一次分 配到路网上去的方法,也被称为交通需求分配。顾名思 义,全有(a)指将OD交通需求一次性地全部分配到 最短径路上。全无( nothing)指对最短径路以外的径路 不分配交通需求量 全有全无分配法应用于没有通行能力限制的网络交通 交通量分配等场合。在美国芝加哥城交通解析中,首次 获得应用。另外,后述增量分配法和均衡分配法中频繁 使用
2.全有全无法（all or nothing method） 全有全无分配法是将 OD 交通需求沿最短经路一次分 配到路网上去的方法，也被称为交通需求分配。顾名思 义，全有（all）指将 OD 交通需求一次性地全部分配到 最短径路上。全无（nothing）指对最短径路以外的径路 不分配交通需求量。 全有全无分配法应用于没有通行能力限制的网络交通 交通量分配等场合。在美国芝加哥城交通解析中，首次 获得应用。另外，后述增量分配法和均衡分配法中频繁 使用
【分配计算步骤】 Step1令n=0x=0(始点,终点j的路段交通量)。 Step2搜索第n个起点到其余各点的最短径路,求出最短 径路费用c=D→和F。 step3按cmbo→l的相反顺序,用下式求出流入节点并 处于最短径路上的路段(F)间的交通量。 x:分配到第η-1个交通量发生点时,路段的 交通量
【分配计算步骤】 Step 1 令n = 0, xi j = 0（始点i ，终点 j 的路段交通量）。 Step 2 搜索第 n 个起点到其余各点的最短径路，求出最短 径路费用c o → i min 和Fi 。 Step 3 按c o → i min 的相反顺序，用下式求出流入节点j 并 处于最短径路上的路段 ( ) Fi i →j 间的交通量ij x 。 n s ij n n s ij n ij x = x + t −1 n−1 ij x ：分配到第n −1 个交通量发生点时，路段ij 的 交通量
交通量发生点n的OD对s的最短径路经 过路段时。 0:交通量发生点的OD对§的最短径路不 经过路段时 Step4如果nN,则结束计算。反之,令n=n+1返回Step 2。N为网络中交通量发生点的集合
1: 交通量发生点n 的 OD 对ns 的最短径路经 过路段ij 时。 r s n ij , = 0: 交通量发生点n 的 OD 对n s 的最短径路不 经过路段ij 时。 Step 4 如果 n=N，则结束计算。反之，令 n=n+1 返回 Step 2。N 为网络中交通量发生点的集合
3.增量分配法( Incremental assignment method) 增量分配法时将OD交通需求量进行适当形式的分割 (分割数、等分或不等分),然后用全有全无分配法,将 分割后的OD交通需求量逐渐分配到网络上去 实际工作中,如何分割OD交通需求量是很重要的, 般多用5-10分割,并且采用不等分
3.增量分配法（Incremental assignment method） 增量分配法时将 OD 交通需求量进行适当形式的分割 （分割数、等分或不等分），然后用全有全无分配法，将 分割后的 OD 交通需求量逐渐分配到网络上去。 实际工作中，如何分割 OD 交通需求量是很重要的， 一般多用 5―10 分割，并且采用不等分