第 4 节 用户均衡问题的解法
1, D ijks tra 法 （记号确定法）
该方法是从离起点最近的点开始，逐渐向全方位枚举
出最短径路的方法。
【 记号 】
K
,最短径路和最小费用已经确定的节点集合。
?
K
：最短径路尚未确定的局部最小费用节点集合。
m
F
：最短径路的途径节点集合。
j
c
：以 o 为起点的最小费用。
【计算步骤】
Step 1 设所有节点 ? ?j 的局部最小费用为
??
j
c
或为足够
大的值，并设
?
?? KjF
j
,0
。
设 o 为起点，对节点 o 有
ojc
o
??,0
，将节点 o 移
到集合 K 。
Step 2 检查以节点
i
为起点的所有路段的终点
? ?m
，若满
足
mim
dcc ??
，则令
iFdcc
mmim
???,
。
Ste p 3 对最小费用尚未确定 的节点集合
?
K 中的所有节
点，按下式计算局部最小费用的最小值 j
c
。
?
?
?
?
?
?
??
?
Kppcc
p
p
j
:),(mi n
。
将节点
j
移到集合 K 。
Ste p 4 如果
??
p
c
以外的节点是否全部被移到集合
K
中，则结束计算。反之，令
ji ?
，返回 Ste p 2 。
【最短径路的枚举】
利用
j
F
枚举出任意节点
j
到起点 o 的最短径路：
)()()()( ?????????
bghj
FfFgFhFj ??
起点 o
【例题】用 Dijkstra 法计算下图从点 1 到其它节点的最
短经路 。
1 5
6
4
7
2
3
2
2
2
1
1
1
1
3
3
4
4
6
8
9
节点及节点号码
路段及路段费用
解：将计算过程列于下图和 表，可以看出，到第７步 为
止，全部节点都被移到集合 K 中，结束计算。例如，
从节点１到节点６的最短径路为：
1)(4)(7)(6 476 ?????? FFF
1 5
6
4
7
2
3
2
2
2
1
1
1
1
3
3
4
4
6
8
9
表 Dijk stra 法的计算过程和结果
路段 各节点的
m
c 局部最小径路
m
F 最小费用节点计
算
顺
序
始
点
终点 节点号码 节点号码 }{m i n
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,全有全无法 （ al l o r n othin g m et hod ）
全有全无分配法是将 OD 交通需求沿最短经路一次分
配到路网上去的方法，也被称为交通需求分配。顾名思
义，全有 （ al l ）指将 OD 交通需求一次性地全部分配到
最短径路上。全无 （ not hi ng ）指对最短径路以外的径路
不分配交通需求量。
全有全无分配法应用于没有通行能力限制的网络交通
交通量分配等场合。在美国芝加哥城交通解析中，首次
获得应用。另外，后述增量分配法和均衡分配法中频繁
使用。
【分配计算步骤】
Step 1 令
0,0 ??
ij
xn
（始点
i
，终点
j
的路段交通量）。
Step 2 搜索第 n 个起点到其余各点的最短径路，求出最短
径路费用
? ?ioc ?
m i n 和 i
F
。
Step 3 按
? ?ioc ?
m i n 的相反顺序，用下式求出流入节点
j
并
处于最短径路上的路段
)(
i
Fi
→
j
间的交通量 ij
x
。
ns
ij
nsn
ij
n
ij
txx ????
? 1
1?n
ij
x
：分配到第
1?n
个交通量发生点时，路段
ij
的
交通量。
1,交通量发生点 n 的 OD 对 ns 的最短径路经
过路段
ij
时。
nrs
ij
,
?
=
0,交通量发生点
n
的 OD 对 ns 的最短径路不
经过路段
ij
时。
Step 4 如果 n=N,则结束计算。反之，令 n=n +1 返回 Step
2 。 N 为网络中交通量发生点的集合。
3,增量分配法 （ Increm ental ass ignm ent m ethod ）
增量分配法时将 OD 交通需求量进行适当形式的分割
（分割数, 等分或不等分），然后用全有全无分配法，将
分割后的 OD 交通需求量逐渐分配到网络上去。
实际工作中，如何分割 OD 交通需求量是很重要的，
一般多用 5 ― 10 分割，并且采用不等分。
【分配计算步骤】
Step 1 根据需要，以适当的形式分割 OD 交通需求量，
即
rs
n
rsn
tt ??
。令 n=1,
0?
n
ij
x
。 Step 2 更新路段费
用
)(
1?
?
n
ijij
n
ij
xcc
。
Step 3 用全有全无分配法将第 n 次分割 OD 交通需求量
r s n
t 分配到最短经路上。
Step 4 如果 n=N,则结束计算。反之，令 n=n+1 返回 Step
2 。 N 为分割次数。
4,均衡分配 （ Fr an k- W ol fe ）法
St ep 1 给出初始可能解
? ?
k
a
x
，令 0?k 。一般用前述全有全
无分配法求解初始可能解。
St ep 2 更新路段费用函数
)(
k
a
k
a
xc
。
St ep 3 搜索目标函数的下降方向。用最短径路搜索法求
出各 OD 间的最短径路，在用全有全无分配法求
出探索方向
? ?
k
a
y
。
Step 4 一维搜索。将下式代入到目标函数中，求出最佳
探索步长
*
?
。
)(
1 k
a
k
a
k
a
k
a
xyxx ???
?
?
Step 5 收敛判定。设 1
?
和 2
?
为任意小数，若满足下式，
则结束计算。反之，返回 Step 2 。
1
1
)()( ????
?
? k
a
k
a
Aa
k
a
k
a
ccxx
2
1
/)(m a x ???
? k
a
k
a
k
a
xxx
【例题】设图示交通网络的 OD 交通需求量为 200?t 辆，
各径路的交通费用函数分别为：
11
10.05 hc ??,
22
0 2 5.010 hc ??, 33 025.015 hc ??
试用全有全无分配法, 增量分配法和均衡分配法求出分
配结果，并进行比较。
径路 3
径路 1 D
径路 2
解：
1, 全有全无分配法
由路段费用函数可知，在路段交通量为零时，径路 1
最短。利用该方法的以下结果：
15,10,2520010.05,0,200
321321
????????? ccchhh
因为，
25,
132
?? ccc
，所以，没有得到均衡解。
目标函数：
3 0 0 00 1 2 5.0150 1 2 5.01005.05
2
33
2
22
2
11
??????? hhhhhhZ
２,增量分配法
采用 2 等分。
（ 1 ） 第 1 次分配
全有全无分配法相同，径路 1 最短。
15,10,151 0 010.05,0,1 0 0
321321
????????? ccchhh
（２）第 2 次分配 最短径路变为径路 2
5.12100025.010,1510010.05,0,100,100
21321
??????????? cchhh
，
15
3
?c
这时，结果接近于均衡解。目标函数为：
1 2 51 0 0 05 0 05 0 00 1 2 5.0150 1 2 5.01005.05
2
33
2
22
2
11
?????????? hhhhhhZ
2125?
３,均衡分配法
【 模型 】
m i n
2
33
2
22
2
11
0125.0150125.01005.05 hhhhhhZ ??????
..ts
?
?
?
3
1
20 0
k
k
h
)3,2,1(,0 ?? kh
k
（ 1 ） 用全有全无分配法求解初始可能解
3 0 0 0,15,10,252 0 010.05,0,2 0 0
321
0
3
0
2
0
1
?????????? Zccchhh
。
（ 2 ） 求最佳搜索方向
继续用全有全无分配法求解，得：
0,2 0 0,0
0
3
0
2
0
1
??? yyy
（４）一维搜索,求最佳搜索步长
*
? 和交通量修正
令
6 1 8.0??
6.123)0200(618.00,4.76)2000(618.0200
0
2
1
1
???????? hh
,
0
1
3
?h
15,09.136.1 2 30 2 5.010,64.124.7610.05
321
????????? ccc
222
00125.00156.1230125.06.123104.7605.04.765 ????????????Z
81.210096.190123685.291382 ?????
（５） 收敛判定
设 1
?
= 2
?
=0.01 。
1
1
)()( ???
?
?
? k
a
k
a
Aa
k
a
k
a
ccxx
2
1
/)(m a x ???
? k
a
k
a
k
a
xxx
显然，收敛条件得不到满足。返回 （ 2 ）继续修正计算 。
这时的最短径路为径路 1 。所以，继续用全有全无分
配法求解，得：
0,0,2 0 0
1
3
1
2
1
1
??? yyy
0.1 2 0)6.1 2 30(0 2 9 1.06.1 2 3,0.80)4.762 0 0(0 2 9 1.04.76
2
2
2
1
???????? hh
0
2
3
?h
222
00125.00150.1200125.00.120100.8005.00.805 ????????????Z
0.2 1 0 00.1801 2 0 0320400 ?????
求最佳探索步长
*
? 的方法：
将
)(
1 k
a
k
a
k
a
k
a
xyxx ???
?
?
代入目标函数中，得
m in
10 ?? ?
? ?
?
??
Aa
xyx
a
k
a
k
a
k
a
dwwc
)(
0
)(
?
这时，求满足下式的
*
?
即可。
? ?? ? 0)()( ??????
?
? Aa
k
a
k
a
n
aa
k
a
k
a
xyxcxy
d
dZ
?
?
【 作业 】 将在交通方式划分中求出的公共汽车和
汽车的 OD 交通量用全有全无分配法和增量
分配法 （３等分）分配到以下路网上去。
路阻函数,111
1.010)( xxt ??
222
1.015)( xxt ??
333
1.05)( xxt ??
444
1.05)( xxt ??
555
1.010)( xxt ??
666
1.015)( xxt ??
1
5
4
2 3
2
1
６
3
4
５
发生吸引点
公共汽车线路
道路网络
1, D ijks tra 法 （记号确定法）
该方法是从离起点最近的点开始，逐渐向全方位枚举
出最短径路的方法。
【 记号 】
K
,最短径路和最小费用已经确定的节点集合。
?
K
：最短径路尚未确定的局部最小费用节点集合。
m
F
：最短径路的途径节点集合。
j
c
：以 o 为起点的最小费用。
【计算步骤】
Step 1 设所有节点 ? ?j 的局部最小费用为
??
j
c
或为足够
大的值，并设
?
?? KjF
j
,0
。
设 o 为起点，对节点 o 有
ojc
o
??,0
，将节点 o 移
到集合 K 。
Step 2 检查以节点
i
为起点的所有路段的终点
? ?m
，若满
足
mim
dcc ??
，则令
iFdcc
mmim
???,
。
Ste p 3 对最小费用尚未确定 的节点集合
?
K 中的所有节
点，按下式计算局部最小费用的最小值 j
c
。
?
?
?
?
?
?
??
?
Kppcc
p
p
j
:),(mi n
。
将节点
j
移到集合 K 。
Ste p 4 如果
??
p
c
以外的节点是否全部被移到集合
K
中，则结束计算。反之，令
ji ?
，返回 Ste p 2 。
【最短径路的枚举】
利用
j
F
枚举出任意节点
j
到起点 o 的最短径路：
)()()()( ?????????
bghj
FfFgFhFj ??
起点 o
【例题】用 Dijkstra 法计算下图从点 1 到其它节点的最
短经路 。
1 5
6
4
7
2
3
2
2
2
1
1
1
1
3
3
4
4
6
8
9
节点及节点号码
路段及路段费用
解：将计算过程列于下图和 表，可以看出，到第７步 为
止，全部节点都被移到集合 K 中，结束计算。例如，
从节点１到节点６的最短径路为：
1)(4)(7)(6 476 ?????? FFF
1 5
6
4
7
2
3
2
2
2
1
1
1
1
3
3
4
4
6
8
9
表 Dijk stra 法的计算过程和结果
路段 各节点的
m
c 局部最小径路
m
F 最小费用节点计
算
顺
序
始
点
终点 节点号码 节点号码 }{m i n
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,全有全无法 （ al l o r n othin g m et hod ）
全有全无分配法是将 OD 交通需求沿最短经路一次分
配到路网上去的方法，也被称为交通需求分配。顾名思
义，全有 （ al l ）指将 OD 交通需求一次性地全部分配到
最短径路上。全无 （ not hi ng ）指对最短径路以外的径路
不分配交通需求量。
全有全无分配法应用于没有通行能力限制的网络交通
交通量分配等场合。在美国芝加哥城交通解析中，首次
获得应用。另外，后述增量分配法和均衡分配法中频繁
使用。
【分配计算步骤】
Step 1 令
0,0 ??
ij
xn
（始点
i
，终点
j
的路段交通量）。
Step 2 搜索第 n 个起点到其余各点的最短径路，求出最短
径路费用
? ?ioc ?
m i n 和 i
F
。
Step 3 按
? ?ioc ?
m i n 的相反顺序，用下式求出流入节点
j
并
处于最短径路上的路段
)(
i
Fi
→
j
间的交通量 ij
x
。
ns
ij
nsn
ij
n
ij
txx ????
? 1
1?n
ij
x
：分配到第
1?n
个交通量发生点时，路段
ij
的
交通量。
1,交通量发生点 n 的 OD 对 ns 的最短径路经
过路段
ij
时。
nrs
ij
,
?
=
0,交通量发生点
n
的 OD 对 ns 的最短径路不
经过路段
ij
时。
Step 4 如果 n=N,则结束计算。反之，令 n=n +1 返回 Step
2 。 N 为网络中交通量发生点的集合。
3,增量分配法 （ Increm ental ass ignm ent m ethod ）
增量分配法时将 OD 交通需求量进行适当形式的分割
（分割数, 等分或不等分），然后用全有全无分配法，将
分割后的 OD 交通需求量逐渐分配到网络上去。
实际工作中，如何分割 OD 交通需求量是很重要的，
一般多用 5 ― 10 分割，并且采用不等分。
【分配计算步骤】
Step 1 根据需要，以适当的形式分割 OD 交通需求量，
即
rs
n
rsn
tt ??
。令 n=1,
0?
n
ij
x
。 Step 2 更新路段费
用
)(
1?
?
n
ijij
n
ij
xcc
。
Step 3 用全有全无分配法将第 n 次分割 OD 交通需求量
r s n
t 分配到最短经路上。
Step 4 如果 n=N,则结束计算。反之，令 n=n+1 返回 Step
2 。 N 为分割次数。
4,均衡分配 （ Fr an k- W ol fe ）法
St ep 1 给出初始可能解
? ?
k
a
x
，令 0?k 。一般用前述全有全
无分配法求解初始可能解。
St ep 2 更新路段费用函数
)(
k
a
k
a
xc
。
St ep 3 搜索目标函数的下降方向。用最短径路搜索法求
出各 OD 间的最短径路，在用全有全无分配法求
出探索方向
? ?
k
a
y
。
Step 4 一维搜索。将下式代入到目标函数中，求出最佳
探索步长
*
?
。
)(
1 k
a
k
a
k
a
k
a
xyxx ???
?
?
Step 5 收敛判定。设 1
?
和 2
?
为任意小数，若满足下式，
则结束计算。反之，返回 Step 2 。
1
1
)()( ????
?
? k
a
k
a
Aa
k
a
k
a
ccxx
2
1
/)(m a x ???
? k
a
k
a
k
a
xxx
【例题】设图示交通网络的 OD 交通需求量为 200?t 辆，
各径路的交通费用函数分别为：
11
10.05 hc ??,
22
0 2 5.010 hc ??, 33 025.015 hc ??
试用全有全无分配法, 增量分配法和均衡分配法求出分
配结果，并进行比较。
径路 3
径路 1 D
径路 2
解：
1, 全有全无分配法
由路段费用函数可知，在路段交通量为零时，径路 1
最短。利用该方法的以下结果：
15,10,2520010.05,0,200
321321
????????? ccchhh
因为，
25,
132
?? ccc
，所以，没有得到均衡解。
目标函数：
3 0 0 00 1 2 5.0150 1 2 5.01005.05
2
33
2
22
2
11
??????? hhhhhhZ
２,增量分配法
采用 2 等分。
（ 1 ） 第 1 次分配
全有全无分配法相同，径路 1 最短。
15,10,151 0 010.05,0,1 0 0
321321
????????? ccchhh
（２）第 2 次分配 最短径路变为径路 2
5.12100025.010,1510010.05,0,100,100
21321
??????????? cchhh
，
15
3
?c
这时，结果接近于均衡解。目标函数为：
1 2 51 0 0 05 0 05 0 00 1 2 5.0150 1 2 5.01005.05
2
33
2
22
2
11
?????????? hhhhhhZ
2125?
３,均衡分配法
【 模型 】
m i n
2
33
2
22
2
11
0125.0150125.01005.05 hhhhhhZ ??????
..ts
?
?
?
3
1
20 0
k
k
h
)3,2,1(,0 ?? kh
k
（ 1 ） 用全有全无分配法求解初始可能解
3 0 0 0,15,10,252 0 010.05,0,2 0 0
321
0
3
0
2
0
1
?????????? Zccchhh
。
（ 2 ） 求最佳搜索方向
继续用全有全无分配法求解，得：
0,2 0 0,0
0
3
0
2
0
1
??? yyy
（４）一维搜索,求最佳搜索步长
*
? 和交通量修正
令
6 1 8.0??
6.123)0200(618.00,4.76)2000(618.0200
0
2
1
1
???????? hh
,
0
1
3
?h
15,09.136.1 2 30 2 5.010,64.124.7610.05
321
????????? ccc
222
00125.00156.1230125.06.123104.7605.04.765 ????????????Z
81.210096.190123685.291382 ?????
（５） 收敛判定
设 1
?
= 2
?
=0.01 。
1
1
)()( ???
?
?
? k
a
k
a
Aa
k
a
k
a
ccxx
2
1
/)(m a x ???
? k
a
k
a
k
a
xxx
显然，收敛条件得不到满足。返回 （ 2 ）继续修正计算 。
这时的最短径路为径路 1 。所以，继续用全有全无分
配法求解，得：
0,0,2 0 0
1
3
1
2
1
1
??? yyy
0.1 2 0)6.1 2 30(0 2 9 1.06.1 2 3,0.80)4.762 0 0(0 2 9 1.04.76
2
2
2
1
???????? hh
0
2
3
?h
222
00125.00150.1200125.00.120100.8005.00.805 ????????????Z
0.2 1 0 00.1801 2 0 0320400 ?????
求最佳探索步长
*
? 的方法：
将
)(
1 k
a
k
a
k
a
k
a
xyxx ???
?
?
代入目标函数中，得
m in
10 ?? ?
? ?
?
??
Aa
xyx
a
k
a
k
a
k
a
dwwc
)(
0
)(
?
这时，求满足下式的
*
?
即可。
? ?? ? 0)()( ??????
?
? Aa
k
a
k
a
n
aa
k
a
k
a
xyxcxy
d
dZ
?
?
【 作业 】 将在交通方式划分中求出的公共汽车和
汽车的 OD 交通量用全有全无分配法和增量
分配法 （３等分）分配到以下路网上去。
路阻函数,111
1.010)( xxt ??
222
1.015)( xxt ??
333
1.05)( xxt ??
444
1.05)( xxt ??
555
1.010)( xxt ??
666
1.015)( xxt ??
1
5
4
2 3
2
1
６
3
4
５
发生吸引点
公共汽车线路
道路网络
