第 6 节 系统最优化分配 (System Op tim u m A ssi g n me n t)
系统最优化分配按照 W ar d rop 第二法则，即使得路
网中总行驶时间最小进行交通量分配。
该方法适用于最大限度地使用现有道路系统的场
合。从径路选择角度，该分配方法与用户均衡分配法
中用户一直选择时间上的最短径路不同，它有必要让
用户选择最短径路以外的径路。从此种意义上说，是
道路规划者或道路管理者所希望的分配原则，尤其在
智能交通系统获得广泛应用之后。
１,【 模型 】
m i n
?
?
?
Aa
aaa
xcxZ )(
..ts
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
该模型可以变换成下示与用户均衡分配模型相同的
形式。
这样，系统最优化分配可以完全用用户均衡分配的解
法计算。
m i n ? ?? ?? ?? ?? Aa
x
a dwdwwcwdZ
a
0
/)(
? ?? ?? ?
?
???
Aa
x
aa
a
dwdwwcdwwc
0
/)()(
２,B r a e s s 奇论 （ P a r a do x ）
1
４
２
3
３
1
４
２
奇论,为提高路网的服务水平而制定的交通政策，在用
户均衡状态下反而导致服务水平的下降。
ＯＤ交通量,6 0 013 ?t 辆
路阻函数：
111 01.050)( xxt ?? （分）
222 1.0)( xxt ? （分）
333 01.050)( xxt ??
444 1.0)( xxt ?
解,利用用户均衡分配法和系统均衡分配法得，
径路１ （路段１＋路段２），径路２ （路段３＋路段４）
的交通量：
300,300
21
?? hh （辆）
径路１ （路段１＋路段２），径路２ （路段３＋路段４）
的旅行时间：
83,83
21
?? cc
（分）
目标函数值：
用户均衡分配法
399?
ue
Z
（辆分），系统最优分配法
4 9 8?
so
Z
1
４
２
3
３
1
４
５
２
555 01.010)( xxt ??
现在道路规划部门计划提高该地区道路的服务
水平 ( 减少总行驶时间 ),计划新建一条道路 （路
段５）。假设路段３, 路段５和路段２形成径路
３，这时，使用用户均衡分配法求出的径路交通
量和行驶时间分别为：
200,200,200 321 ??? hhh （辆）
92,92,92 321 ??? ccc （分）
目标函数值：
用户均衡分配法 3 8 6?ueZ （辆分），系统最优分配
法 552?soZ （辆分）
用户均衡分配法,在新路规划之前，目标函数值为
399,之后为 386 。目标函数值向着最佳方向变动，
径路行驶时间在新路规划前 83 分，之后变成了 92 分。
系统最优分配,目标函数值由新路规划前的 498 变成
552 。
结论：
因路网的结构不同，新线道路的建设反而恶化
道路原有的服务水平，这种现象在实际道路规划中
很有可能出现。
【作业】设图示交通网络的 OD 交通需求量为 200?t 辆，
各径路的交通费用函数分别为：
11
10.05 hc ??
,22 0 2 5.010 hc ??,
33
025.015 hc ??
试用 F - W 算法求均衡分配法和系统最优分配
法的分配结果，并对结果进行讨论。
径路 3
径路 1 D
径路 2
o
第 7 节 随机用户均衡分配 (S to chas ti c Use r Eq uili brium
Ass ignm ent )
在用户均衡分配中,假设了所有的用户都完全掌
握路网上的全部信息，并选择最短径路从出发地到目
的地。然而，这种假设在实际的用户径路选择行动过
程中难以实现。
这里，从用户对路网的交通信息的认识角度出
发，应用效用理论假设用户对路网交通信息的遵照随
机效用理论，即研究交通信息的不确定条件下的径路
选择和路网的交通均衡问题。
1,随机用户均衡分配及其模型化
与用户均衡问题相同，这里仍假设径路的交通费
用与其交通量成正比 （ f l o w i n d e p e n d e n t ），并且假设
在用户对径路交通费用的认识中存在随机误差。对图
示简单路网，可观测费用为：
)2,1(),( ?? ihcc
iii
另外，对观测费用，考虑用户的认识误差后，有：
)2,1(,)( ??? ihcc
iiii
?
，各个用户在该费用前提下进行
径路选择，其结果决定路网交通量。
假设用户的交通选择行为可以用随机效用理论表现，那么
径路
i
被选择的概率：
? ?)()(
jjiii
ccp r o bP ?? ????
期望交通量：
)2,1(,??? iPqh
ii
用户在每日的实际交通选择过程中，反复进行两径路择一
的过程，假设用户始终按照使自己认识的交通费用最小而
选择行驶径路。反复这种选择过程，路网的交通流将达到
如下随机用户均衡状态：
所有的用户都相信自己的行驶费用不因为改变行驶径
路而减少。
随机用户均衡的概念拓展了 W a r dr op 均衡的概念。
【随机用户均衡问题的建模】
ＯＤ对径路
k
的效用函数,
rs
k
rs
k
rs
k
cU ????
这里，
rs
k
c
为径路
k
的费用，其值为径路经过路段的
费用和。
?
?
??
Aa
rs
kaij
rs
k
tc
.
?
径路
k
的选择概率：
? ?
?
?
?
?
?
?
??
?
tUUP
rs
k
Kk
rs
k
rs
k
'
'
m a x
.Pr
? ?
?
?
?
?
?
?
??????
?
tcc
rs
k
rs
k
Kk
rs
k
rs
k '
'
'
m a x
.Pr ??
? ?
?
?
?
?
?
?
????
?
tcc
rs
k
rs
k
Kk
rs
k
rs
k '
'
'
m a x
.Pr ??
径路 k 交通量的期望值：
rs
k
rsrs
k
PthE ??)(
径路选择概率守恒条件：
?
?
k
rs
k
P 1
，
??? rs
径路交通量－ＯＤ交通量守恒原则：
?
?
?
Kk
rsrs
k
thE )(
,
??? rs
径 路 交 通 量 － 路 段 交 通 量 守 恒 原 则,
rs
ka
Kk
rs
k
rs
ij
hExE
,
)()( ???
??
???
，
Aa ??
径路交通量的方差：
)1()(
rs
k
rs
k
rsrs
k
PPthV a r ???
径路交通量的协方差：
rs
k
rs
k
rsrs
k
rs
k
PPthhCo v
''
),( ??
2,随机用户均衡分配及其等价最优化问题
(1) 最大熵费用调和模型
m i n
?? ?
???
??
rs
rsrsrs
Aa
a
x
hHtdwwcZ
a
)(
1
)(
0
?
?
..ts
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
其中，
?? ?
?? ??
????
Kk
rs
rs
k
rs
rs
k
Kk rs
rs
k
rs
k
rsrs
t
h
t
h
PPhH lnln)(
?
可以证明，该模型与 Logit m odel 等价 （证明略）。
由以上模型可以看出，该种随机用户均衡模型为
W ar dr op 均衡分配的一般情况。这是因为在该问题中，
当
????
时，表示熵的项 （目标函数中第二项）消失，
与 W ar dr op 均衡分配的等价最优化问题一致。相反，
0??
时，与费用项相比，代表熵的项目大。这时，
与径路的费用无关，各条径路将以相同的概率获得分
配交通量。
(2) 最大熵模型
m a x ? ?
?? ?
??
rs
rsrsrs
Kk
hHtZ )(
?
..ts
? ?
?
?
Aa
x
a
Edwwc
a
?
)(
0
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
其中，
E
?
为用实测交通量推测出的路网总行驶
费用值。
(3) 费用积分最小模型
m i n ? ?
?
?
Aa
a
x
dwwcZ
a
)(
0
..ts
?
??
?
rs
rsrsrs
HhHt
?
)(
?
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
其中，
H
?
为由实测交通量推算出的径路熵值。
径路交通量 rskh 由 L o gi t 模型决定,?
?
?
??
Kk
rs
k
rs
krsrs
k c
cth
)e x p (
)e x p (
?
?
3,随机用户均衡分配的等价最优化问题解法
由上述可知,随机用户均衡问题为非线性规划问
题，直接求解困难。与用户均衡问题相同，通过求解
其等价最优化问题计算均衡交通量，并且求解方法因
模型的性质不同而异。其方法有,（ 1 ）逐次平均法；
（ 2 ）部分线性化法； （ 3 ） Si m plic ia l dec omposit ion 法
等。具体的分配算法有 Dai l 法, 马尔科夫链法 （ Mar ko v
cha in as si gn m ent ）和 Mo nte Car lo si m ulat ion 。以下介
绍逐次平均法，其余方法参阅有关材料。
【 逐次平均法 （ m e tho d of s uc c e s s ive a ve r a ge s ） 】
逐次平均法是一种收敛计算方法求解最大熵费
用调和模型的方法，与 Fr a nk- W ol f e 法类似，不同
的是搜索步长的决定方法。该方法不进行求解最佳
搜索步长的一维搜索，而是实现给定步长。原因是
最大熵费用调和模型中包含径路交通量变量。
【 计算步骤 】
S tep 0 利用 Dail 法, 马尔科夫链法或 Mo nte Carlo
sim u lat ion 求解初始可能解
0
a
x
。
令迭代计算次数
0?k
，路阻函数 )0(
0
aa
cc ?, Aa ??
S tep 1 更新路阻函数
Aaxcc
k
aa
k
a
??? ),(
S tep 2 下降方向搜索
利用 D ail 法, 马尔科夫链法或 Mo nte Carlo
sim u lat ion 求解实行可能解
k
a
y
，求出搜索方向
Aaxyd
k
a
k
a
????,
。
Step 3 一维搜索
k/1??
Step 4 更新试行可能解
)(
1 k
a
k
a
k
a
k
a
xyxx ???
?
?
，
Aa ??
Step 5 收敛判定
设 ε 为任意正小数，并且由下式决定。
??
??
?
??
Aa
k
a
Aa
k
a
k
a
xxx /)(
21
?
mAaxxx
m
x
mk
a
k
a
k
a
k
a
,),(
1
11
??????
???
??
为既
定整数。
系统最优化分配按照 W ar d rop 第二法则，即使得路
网中总行驶时间最小进行交通量分配。
该方法适用于最大限度地使用现有道路系统的场
合。从径路选择角度，该分配方法与用户均衡分配法
中用户一直选择时间上的最短径路不同，它有必要让
用户选择最短径路以外的径路。从此种意义上说，是
道路规划者或道路管理者所希望的分配原则，尤其在
智能交通系统获得广泛应用之后。
１,【 模型 】
m i n
?
?
?
Aa
aaa
xcxZ )(
..ts
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
该模型可以变换成下示与用户均衡分配模型相同的
形式。
这样，系统最优化分配可以完全用用户均衡分配的解
法计算。
m i n ? ?? ?? ?? ?? Aa
x
a dwdwwcwdZ
a
0
/)(
? ?? ?? ?
?
???
Aa
x
aa
a
dwdwwcdwwc
0
/)()(
２,B r a e s s 奇论 （ P a r a do x ）
1
４
２
3
３
1
４
２
奇论,为提高路网的服务水平而制定的交通政策，在用
户均衡状态下反而导致服务水平的下降。
ＯＤ交通量,6 0 013 ?t 辆
路阻函数：
111 01.050)( xxt ?? （分）
222 1.0)( xxt ? （分）
333 01.050)( xxt ??
444 1.0)( xxt ?
解,利用用户均衡分配法和系统均衡分配法得，
径路１ （路段１＋路段２），径路２ （路段３＋路段４）
的交通量：
300,300
21
?? hh （辆）
径路１ （路段１＋路段２），径路２ （路段３＋路段４）
的旅行时间：
83,83
21
?? cc
（分）
目标函数值：
用户均衡分配法
399?
ue
Z
（辆分），系统最优分配法
4 9 8?
so
Z
1
４
２
3
３
1
４
５
２
555 01.010)( xxt ??
现在道路规划部门计划提高该地区道路的服务
水平 ( 减少总行驶时间 ),计划新建一条道路 （路
段５）。假设路段３, 路段５和路段２形成径路
３，这时，使用用户均衡分配法求出的径路交通
量和行驶时间分别为：
200,200,200 321 ??? hhh （辆）
92,92,92 321 ??? ccc （分）
目标函数值：
用户均衡分配法 3 8 6?ueZ （辆分），系统最优分配
法 552?soZ （辆分）
用户均衡分配法,在新路规划之前，目标函数值为
399,之后为 386 。目标函数值向着最佳方向变动，
径路行驶时间在新路规划前 83 分，之后变成了 92 分。
系统最优分配,目标函数值由新路规划前的 498 变成
552 。
结论：
因路网的结构不同，新线道路的建设反而恶化
道路原有的服务水平，这种现象在实际道路规划中
很有可能出现。
【作业】设图示交通网络的 OD 交通需求量为 200?t 辆，
各径路的交通费用函数分别为：
11
10.05 hc ??
,22 0 2 5.010 hc ??,
33
025.015 hc ??
试用 F - W 算法求均衡分配法和系统最优分配
法的分配结果，并对结果进行讨论。
径路 3
径路 1 D
径路 2
o
第 7 节 随机用户均衡分配 (S to chas ti c Use r Eq uili brium
Ass ignm ent )
在用户均衡分配中,假设了所有的用户都完全掌
握路网上的全部信息，并选择最短径路从出发地到目
的地。然而，这种假设在实际的用户径路选择行动过
程中难以实现。
这里，从用户对路网的交通信息的认识角度出
发，应用效用理论假设用户对路网交通信息的遵照随
机效用理论，即研究交通信息的不确定条件下的径路
选择和路网的交通均衡问题。
1,随机用户均衡分配及其模型化
与用户均衡问题相同，这里仍假设径路的交通费
用与其交通量成正比 （ f l o w i n d e p e n d e n t ），并且假设
在用户对径路交通费用的认识中存在随机误差。对图
示简单路网，可观测费用为：
)2,1(),( ?? ihcc
iii
另外，对观测费用，考虑用户的认识误差后，有：
)2,1(,)( ??? ihcc
iiii
?
，各个用户在该费用前提下进行
径路选择，其结果决定路网交通量。
假设用户的交通选择行为可以用随机效用理论表现，那么
径路
i
被选择的概率：
? ?)()(
jjiii
ccp r o bP ?? ????
期望交通量：
)2,1(,??? iPqh
ii
用户在每日的实际交通选择过程中，反复进行两径路择一
的过程，假设用户始终按照使自己认识的交通费用最小而
选择行驶径路。反复这种选择过程，路网的交通流将达到
如下随机用户均衡状态：
所有的用户都相信自己的行驶费用不因为改变行驶径
路而减少。
随机用户均衡的概念拓展了 W a r dr op 均衡的概念。
【随机用户均衡问题的建模】
ＯＤ对径路
k
的效用函数,
rs
k
rs
k
rs
k
cU ????
这里，
rs
k
c
为径路
k
的费用，其值为径路经过路段的
费用和。
?
?
??
Aa
rs
kaij
rs
k
tc
.
?
径路
k
的选择概率：
? ?
?
?
?
?
?
?
??
?
tUUP
rs
k
Kk
rs
k
rs
k
'
'
m a x
.Pr
? ?
?
?
?
?
?
?
??????
?
tcc
rs
k
rs
k
Kk
rs
k
rs
k '
'
'
m a x
.Pr ??
? ?
?
?
?
?
?
?
????
?
tcc
rs
k
rs
k
Kk
rs
k
rs
k '
'
'
m a x
.Pr ??
径路 k 交通量的期望值：
rs
k
rsrs
k
PthE ??)(
径路选择概率守恒条件：
?
?
k
rs
k
P 1
，
??? rs
径路交通量－ＯＤ交通量守恒原则：
?
?
?
Kk
rsrs
k
thE )(
,
??? rs
径 路 交 通 量 － 路 段 交 通 量 守 恒 原 则,
rs
ka
Kk
rs
k
rs
ij
hExE
,
)()( ???
??
???
，
Aa ??
径路交通量的方差：
)1()(
rs
k
rs
k
rsrs
k
PPthV a r ???
径路交通量的协方差：
rs
k
rs
k
rsrs
k
rs
k
PPthhCo v
''
),( ??
2,随机用户均衡分配及其等价最优化问题
(1) 最大熵费用调和模型
m i n
?? ?
???
??
rs
rsrsrs
Aa
a
x
hHtdwwcZ
a
)(
1
)(
0
?
?
..ts
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
其中，
?? ?
?? ??
????
Kk
rs
rs
k
rs
rs
k
Kk rs
rs
k
rs
k
rsrs
t
h
t
h
PPhH lnln)(
?
可以证明，该模型与 Logit m odel 等价 （证明略）。
由以上模型可以看出，该种随机用户均衡模型为
W ar dr op 均衡分配的一般情况。这是因为在该问题中，
当
????
时，表示熵的项 （目标函数中第二项）消失，
与 W ar dr op 均衡分配的等价最优化问题一致。相反，
0??
时，与费用项相比，代表熵的项目大。这时，
与径路的费用无关，各条径路将以相同的概率获得分
配交通量。
(2) 最大熵模型
m a x ? ?
?? ?
??
rs
rsrsrs
Kk
hHtZ )(
?
..ts
? ?
?
?
Aa
x
a
Edwwc
a
?
)(
0
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
其中，
E
?
为用实测交通量推测出的路网总行驶
费用值。
(3) 费用积分最小模型
m i n ? ?
?
?
Aa
a
x
dwwcZ
a
)(
0
..ts
?
??
?
rs
rsrsrs
HhHt
?
)(
?
?
?
????
rs
Kk
rsrs
k
rsth,
??
???
????
rs
rs
k
rs
ka
Kk
a
Aahx
rs
,
,
?
0,0 ??
a
rs
k
xh
其中，
H
?
为由实测交通量推算出的径路熵值。
径路交通量 rskh 由 L o gi t 模型决定,?
?
?
??
Kk
rs
k
rs
krsrs
k c
cth
)e x p (
)e x p (
?
?
3,随机用户均衡分配的等价最优化问题解法
由上述可知,随机用户均衡问题为非线性规划问
题，直接求解困难。与用户均衡问题相同，通过求解
其等价最优化问题计算均衡交通量，并且求解方法因
模型的性质不同而异。其方法有,（ 1 ）逐次平均法；
（ 2 ）部分线性化法； （ 3 ） Si m plic ia l dec omposit ion 法
等。具体的分配算法有 Dai l 法, 马尔科夫链法 （ Mar ko v
cha in as si gn m ent ）和 Mo nte Car lo si m ulat ion 。以下介
绍逐次平均法，其余方法参阅有关材料。
【 逐次平均法 （ m e tho d of s uc c e s s ive a ve r a ge s ） 】
逐次平均法是一种收敛计算方法求解最大熵费
用调和模型的方法，与 Fr a nk- W ol f e 法类似，不同
的是搜索步长的决定方法。该方法不进行求解最佳
搜索步长的一维搜索，而是实现给定步长。原因是
最大熵费用调和模型中包含径路交通量变量。
【 计算步骤 】
S tep 0 利用 Dail 法, 马尔科夫链法或 Mo nte Carlo
sim u lat ion 求解初始可能解
0
a
x
。
令迭代计算次数
0?k
，路阻函数 )0(
0
aa
cc ?, Aa ??
S tep 1 更新路阻函数
Aaxcc
k
aa
k
a
??? ),(
S tep 2 下降方向搜索
利用 D ail 法, 马尔科夫链法或 Mo nte Carlo
sim u lat ion 求解实行可能解
k
a
y
，求出搜索方向
Aaxyd
k
a
k
a
????,
。
Step 3 一维搜索
k/1??
Step 4 更新试行可能解
)(
1 k
a
k
a
k
a
k
a
xyxx ???
?
?
，
Aa ??
Step 5 收敛判定
设 ε 为任意正小数，并且由下式决定。
??
??
?
??
Aa
k
a
Aa
k
a
k
a
xxx /)(
21
?
mAaxxx
m
x
mk
a
k
a
k
a
k
a
,),(
1
11
??????
???
??
为既
定整数。
