r∈R, s∈S, k∈P,
(3a)
∂L (f , u ) = 0, ∂ urs
考 虑(1d)和 守 衡 约 束 , (3)可 以 写 成
k k f rs ( crs − urs ) = 0 , k crs − urs ≥ 0 , r∈R,
r∈R, s∈S.
(3b)
r∈R, s∈S, k∈P, s∈S, k∈P, r∈R, s∈S,
a∈A.
(1d)
7
黄海军
在 公式 (1)中 ， 路 段时 间 函 数 被 假 定 成 是 路 段 流 量 的 连 续 、 单 调 上 升 函 数 ， 并 只 与 自 己 路 段流量 相关 。公 式 (1)被称 为 UE 条 件的 Beckmann(1956)变换。很 容易 证明 ，问 题 (1)的解 满 足 Wardrop 的 UE 条 件 ， 为 此 ， 我 们 定 义 一 个 Lagrangean 函 数 如 下
min Z(x) = 约束
k ∈P rs
a∈A 0
∑ ∫ ta(w)dw ,
r∈R, s∈S,
xa
(1a)
∑ frsk = qrs ,
பைடு நூலகம்
(1b)
k frs ≥ 0,
r∈R, s∈S, k∈P,
(1c)
其中路段流量x 由下式定义
k xa = ∑∑ ∑ frs δak , rs r∈R s∈S k ∈P rs
可证：用户均衡配流等价于求解下述极值问题
min
∑∫
a
xa 0
c a ( w )d w
(10)
s.t. (8)—(9) and
黄海军
xa ≥ 0, ∀a.
2 3
UE分配的核心思想体现在 对拥挤效应的考虑
黄海军
4
时间 理论函数 近似函数
零流时间
通行能力 流量
图 1 典型的路段时间函数
黄海军
5
N A R S P a r s k Prs qrs xa ta
于给定的一个 OD 对，对应的 Lagrange 乘子总是小于或等于所有路径的时间。显然，数学 ardrop 的UE 条件， 在任意一个OD之间， 规划问题的一阶条件确实描述了W 即： 所有被使 用了的路径具有该OD 对之间最小的时间。
黄海军
9
可以证明(1)的路段流量解是唯一的。 目标函数(1a)相对于 x 是严格凸的， 因为其 Hessian 矩阵
(4a) (4b) (4c)
k ∈Prs
∑
k f rs − qrs = 0 ,
k 其 中 crs =
a ∈A
ak ∑ ta ( xa )δ rs ，是 OD 对(r,s)之 间 路 径 k 的 时 间 。
黄海军
8
k 条件(4c)就是流量守衡约束(1b)。(4a)告诉我们，有正值路径流量的路径，即 frs >0，其时间 k 等于常数urs；否则，如果 frs =0，该路径的时间必定大于这个常数，如(4b)所示。所以，对
n n 步 1. 更新路段时间ta = ta (xa ) , a∈A. n 步 2. 寻找下降方向。在[ ta ]基础上寻找最短路径并进行全有全无分配，产生增广路段
流量yn. 步 3. 确定最优迭代步长αn，即求解下列一维优化问题 min
∑
a
n n n xa +α( ya −xa )
∫ ta(w)dw , s.t. 0 ≤ α ≤ 1.
k f rs Crs = OD 对(r,s)之间的路径 k 上的流量
δak = {1，若路段 a 在(r,s)之间的路径 k 上；否则为零}. rs
黑体符号将表示向量或矩阵。除特别说明之外，假设一个出行者就是一辆车。
黄海军 6
1。确定性用户均衡交通分配
关键点是假设出行者遵循什么样的行为准则。有两个广泛使用的原则，即 Wardrop(1952)第一和第二原则。第一原则假定，所有出行者独立地做出令自己的行 驶时间最小的决策，在所导致的网络流量分布状态里，同一OD对之间所有被使用的 路径的时间是相等的，并不大于任何未被使用路径的时间。这样一种流量分布状态 被称为用户均衡态，在这种状态下，没有人能够通过单方面改变自己的路径来达到 降低自己时间的目的 。
c ij = min
( p)
∑ δ apij c a ( x a ) =
a
⎧ c pij = ∑ δ apij c a ( x a ) = c ij , if h pij > 0 ⎪ a ⎨ c = ∑ δ c ( x ) ≥ c , if h = 0 apij a a ij pij ⎪ pij ⎩ a
黄海军 10
2、算法
在优化理论中，有许多算法可以用来解决我们的问题(1)，其中基于可行方向的凸组合 算法是最适合的算法， 因为迭代过程中寻找可行下降方向这一步对应于一个最短路问题。 在 第 n 次迭代中，目标函数 Z(x)对路段流量的梯度是 ∂Z(xn)/∂x = t(xn)，寻找可行下降方向的线 性规划（LP）问题就成为 min Z n(y) = ∇Z (xn ) T y = 约束
k ∑ grs = qrs , k
k grs ≥ 0,
∑ (∂Z (xn ) / ∂xa ) ya = ∑ tan ya ,
a a
(9a)
r∈R, s∈S,
(9b)
r∈R, s∈S, k∈P,
k
(9c)
其中 ya =
r ∈R s∈S k ∈Prs
k ∑ ∑ ∑ grsδak , rs
a∈A, 叫增广路段流量，而 grs 就叫增广路径流量。LP 问题(9)
L (f , u ) = Z (x) +
r ∈R s ∈S
∑ ∑ urs ( qrs − ∑
k ∈Prs
k f rs ) ,
(2)
其 中 u rs 是 对 应 于 约 束 (1b)的 Lagrange 乘 子 。 最 小 化 (2)的 一 阶 条 件 是
k f rs
∂L (f , u ) ∂L (f , u ) = 0 and ≥ 0, k k ∂ f rs ∂ f rs
The convergence rate of the above Frank-Wolfe algorithm is sub-linear and the marginal contribution of each successive iteration becomes smaller and smaller as the algorithm proceeds. The algorithm converges rapidly in the first several iterations, but very slowly in the later stages, because the search direction
∂ 2 Z (x) ∂ (∂Z (x) / ∂xa ) ∂ta ( xa ) ′ = = = {ta ( xa ) 若 b = a; 否则为0} , ∂xa ∂xb ∂xb ∂xb
(8)
此式成立是因为我们这里不考虑路段之间的流量交叉影响。(7)又称为路段时间函数对流量 的 Jacobian 矩阵。 由于数学规划问题的可行域是由线性等式与非负约束条件构成的，它是凸的，所以(1)是严 格凸规划问题， 有满足 UE 原则的唯一路段流量解。 该问题对于路径流量不是严格凸的， 但， 所以路径流量解不唯一。
若路段 a 在从 i 至 j 的路径 p 上，否则为零}
配流方法： 最短路径的概念，司机的择路原则 全有全无法 (all—or—nothing) 比例递增法 (incremental assignment) 均衡分配法
黄海军
2
UE (user equilibrium assignment, Wardrop 1952), 考虑了拥挤效应，令
k
= 所有节点的集合 = 所有路段的集合 = 所有出发地的集合 = 所有目的地的集合 = 所有路径的集合 = 表示一条路段, a∈A = 表示一个出发地, r∈R = 表示一个目的地, s∈S = 表示一条路径, k∈P = r 与 s 之间所有路径的集合, Prs∈P = 单位时间段内从 r 到 s 的交通需求量 = 路段 a 上的交通流量 ，有时用 va 表示 = 行驶路段 a 所需的平均时间
(y
(n)
− x ( n ) ) tends eventually to be orthogonal
to the gradient of Z ( x( n ) ) at x ( n ) . The number of iterations required for convergence is significantly affected by the initial solution, the congestion level and the stopping criterion. In relatively un-congested networks, the flow pattern after a few iterations approaches the equilibrium state, since the updated link flows can not heavily change link travel times and then the set of shortest paths basically remains unchanged in the iterative process. As congestion builds up, more iterative works are required to equalize the costs on potentially possible-used paths. However, in most actual large-size applications with typical congestion levels, only six to ten iterations are usually sufficient to find the equilibrium link-flow pattern in terms of the tradeoffs among analytical accuracy, data limitations, and computer budget.