第 4 节 用户均衡问题的解法
1, D ij kst r a 法 (记号确定法)
该方法是从离起点最近的点开始,逐渐向全方位枚举
出最短径路的方法。
【 记号 】
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
???,

Step 3 对最小费用尚未确定 的节点集合
?
K 中的所有节
点,按下式计算局部最小费用的最小值 j
c

?
?
?
?
?
?
??
?
Kppcc
p
p
j
:),(m i n

将节点
j
移到集合
K

Step 4 如果
??
p
c
以外的节点是否全部被移到集合
K
中,则结束计算。反之,令
ji ?
,返回 Step 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
节点及节点号码
路段及路段费用
解:将计算过程列于下图和 表,可以看出,到第7步 为
止,全部节点都被移到集合 K 中,结束计算。例如,
从节点1到节点6的最短径路为:
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
表 Di jk st ra 法的计算过程和结果
路段 各节点的
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 or nothing m et hod )
全有全无分配法是将 OD 交通需求沿最短经路一次分
配到路网上去的方法,也被称为交通需求分配。顾名思
义,全有 ( al l )指将 OD 交通需求一次性地全部分配到
最短径路上。全无 ( not hin g )指对最短径路以外的径路
不分配交通需求量。
全有全无分配法应用于没有通行能力限制的网络交通
交通量分配等场合。在美国芝加哥城交通解析中,首次
获得应用。另外,后述增量分配法和均衡分配法中频繁
使用。
【分配计算步骤】
Step 1 令
0,0 ??
ij
xn
(始点
i
,终点
j
的路段交通量)。
Step 2 搜索第 n 个起点到其余各点的最短径路,求出最短
径路费用
? ?ioc ?
m in 和
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
时。
Ste p 4 如果 n=N,则结束计算。反之,令 n=n +1 返回 Ste p
2 。 N 为网络中交通量发生点的集合。
3,增量分配法 ( In cr em en t al a ssig nm en t m et ho d )
增量分配法时将 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,均衡分配 ( Frank- W olfe )法
Step 1 给出初始可能解
? ?
k
a
x
,令 0?k 。一般用前述全有全
无分配法求解初始可能解。
Step 2 更新路段费用函数
)(
k
a
k
a
xc

Step 3 搜索目标函数的下降方向。用最短径路搜索法求
出各 OD 间的最短径路,在用全有全无分配法求
出探索方向
? ?
k
a
y

S tep 4 一维搜索。将下式代入到目标函数中,求出最佳
探索步长
*
?

)(
1 k
a
k
a
k
a
k
a
xyxx ???
?
?
S tep 5 收敛判定。设 1
?

2
?
为任意小数,若满足下式,
则结束计算。反之,返回 S tep 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 交通需求量为 2 0 0?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,增量分配法
采用 2 等分。
( 1 ) 第 1 次分配
全有全无分配法相同,径路 1 最短。
15,10,151 0 010.05,0,1 0 0
321321
????????? ccchhh
(2)第 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?
3,均衡分配法
【 模型 】
m i n
2
33
2
22
2
11
0 1 2 5.0150 1 2 5.01005.05 hhhhhhZ ??????
..ts
?
?
?
3
1
200
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
(4)一维搜索,求最佳搜索步长
*
? 和交通量修正

618.0??
6.1 2 3)02 0 0(6 1 8.00,4.76)2 0 00(6 1 8.02 0 0
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.2 1 0 096.1 9 01 2 3 685.2 9 13 8 2 ?????
(5) 收敛判定

1
?
=
2
?
=0.01 。
1
1
)()( ???
?
?
? k
a
k
a
Aa
k
a
k
a
ccxx
2
1
/)(max ???
? k
a
k
a
k
a
xxx
显然,收敛条件得不到满足。返回 ( 2 )继续修正计算 。
这时的最短径路为径路 1 。所以,继续用全有全无分
配法求解,得:
0,0,200
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 i n
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 交通量用全有全无分配法和增量
分配法 (3等分)分配到以下路网上去。
路阻函数,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

发生吸引点
公共汽车线路
道路网络