V 为网络节点集,即:道路交叉点;A 为路段集,即:道路
交通量—人的个数—OD 矩阵
,a C a A ∈:路段a 的通行能力
()a a t x :路段a 的阻抗,a x 为流量,通常以时间记,假设仅与路段a 有关
系统最优是系统规划者所期望得到的一种平衡状态,其前提是所有网络用户必须互相协作,遵从网络管理者的统一调度,所以是计划指向型分配准则。
出行者的出行决策过程是相互独立的,路网上的交通流的状态是出行者独立选择的结果。
出行者必然转向费用较小的路径.其结果,路网上的交通量分布最终必然趋于用户平衡状态。
所以,用户平衡状态最接近实际的交通状态。
Wardrop 准则的提出标志着网络流平衡分配概念从描述转为严格刻画,不但假设司机都力图选择阻抗最小的路径,而且还假设司机随时掌握整个网络的状态,精确计算每条路径的阻抗,还假设了司机的计算能力与水平是相同的。
在这些假设条件下进行的配流被称为确定性配流,得到的用户平衡条件被称为确定性平衡条件,简称UE 条件。
User Equilibrium System Optimal rs k rs a f q ∑=且0rs
k f ≥(rs k f —O-D 对r-s 之间路径k 上的流量)rs q 等于连接rs 之间
各路径上的路段的交通量的总和。
,rs rs a k a k r s k x f σ=∑∑∑(,rs a k σ—如果弧a 在连接O-D 对r-s 的路径k 上,其值为1,否则为0)路段a 上的流量等于通过a 的路径上分配到a 上的交通量的总和。
1.
目标函数本身并没有什么直观的经济含义或行为含义。
2. 没必要直接求解用户平衡条件方程组,平衡状态可以由求解等价都极小值问题得到。
3.
模型的解关于路段流量唯一,关于路径流不唯一 4. 等价性与唯一性证明略
Frank-Wolfe 算法
对f(X)在X 0处的一阶泰勒展开得
(0)(0)(0)()()()()T f X f X f X X X =+∇-
将f(X)近似表达成线性函数,则规划模型可近似化为下列线性规划模型: (0)(0)(0)min ()min ()()()()
T Z X f X f X f X X X AX B ==+∇-=
等价于线性规划 (0)m i n ()()T Z X f X X
A X B
=∇= 由上式可求得一组最优解X -,该方法认为(0)X 与X -的连线为最速下降方向,然
后根据下列一维极值间题
(0)(0)min [()]f X X X λ-+- 求得的0λ为最优步长。
令 (1)(0)(()X X X X
λ-=+-,得到下一步迭代的起点。
如此循环,直到(1)n X +与()
n X 十分接近为止。
特点:每一步迭代都必须求解一组线性规划问题;只是在近似的线性规划模型易于求解时,该方法才有应用价值,而交通分配模型正好具有这一特点。
缺陷:迭代后期收敛速度较慢,出现震荡现象,原因是采用了最速下降方向,当趋于问题的最优解时,搜索方向将近似垂直于目标函数下{}a x 的梯度方向。
对于模型的改进:
修正UE 基本模型的各种假设条件得到
1.()a a t x ,不仅与a x 有关--路段相互影响的用户平衡配流
2. 含能力约束的交通分配模型
3. 弹性需求分配模型,O-D 交通量的大小是受网络运行状况影响的。
4. 考虑出行者对阻抗估计不确定性的随机用户平衡。