改进的交通分配起点用户均衡算法
第45卷第4期 2011年4月
上海交通大学学报
JO U RN A L OF SH A N GH AI JIA O T O NG U N IV ERSIT Y
Vol. 45No. 4 Apr. 2011
文章编号:1006-2467(2011) 04-0510-07
改进的交通分配起点用户均衡算法
张天然
(上海市城市综合交通规划研究所, 上海200040)
摘 要:对起点用户均衡算法的流量转移、起点限制子网(Bush) 的更新、成本更新策略及计算流程
等关键问题进行了分析改进. 探讨了Bush 的最长和最短路径对查找方法, 提出了流量转移的步长搜索方法及加速算法收敛的Bush 更新方法. 该方法优化了适合多线程开发的算法流程, 并用不同规模的城市交通网络模型对算法进行效率测试和与其他算法进行对比. 结果表明, 该算法效率有较大的提高, 可满足大规模城市交通网络模型计算速度和精度的要求. 关键词:用户均衡交通分配; 起点用户均衡算法; 无环网络中图分类号:U 491 文献标志码:A
Improved Origin User Equilibrium Algorithm for Traffic Assignment
ZH A N G T ian -r an
(Shanghai City Comprehensive Transportation Planning Institute, Shang hai 200040, China) Abstract:Key tactics of an or ig in user equilibrium (OU E) alg orithm such as flow shift from max -to m in -paths, bush update and the alg orithm . s pro cedure w ere studied. The finding of m ax -and min -paths seg -mentation pair, the step size of bush flow shift and bush co nstructio n w ere studied to speed up the conver -gence. T he algor ithm . s procedure w as also optimized to take the advantage o f mult-i thread pro cess. Con -vergence per for mances w ere compared w ith other algo rithms by different size of urban tr ansportatio n net -w ork. The improv ed OUE alg orithm is more efficient and co nverg es satisfactorily in a pr actical applica -tion.
Key words:traffic assig nm ent; o rigin user equilibrium algorithm; acyclic netw ork
交通分配是交通需求模型的重要构成部分, 它描述的是出行者如何在交通网络上选择出行路径. 假定在信息完全的情况下, 出行者会选择成本最小的路径. Wardro p 早在1952年给出了用户均衡
[2]
(U E) 的定义, Beckmann 等随后构建了用户均衡交通分配的数学模型, 但这一理论直到1975年Leblance 等[3]将Frank -Wolfe(F -W) 算法应用到交通分配问题. 从模型应用的角度, 交通规划师和软件工作者面临2个实际问题, 即交通分配达到什么样的精确度才能满足定量分析的要求和是否有更为高
收稿日期:2010-06-17
[1]
效的算法在最短时间内达到所要的精度. Boyce 等以费城的2条快速路间的一对匝道建设方案使
用交通分配模型进行影响范围分析为例, 指出相对误差至少要小于10-4, 交通分配解的结果才比较可靠. Slavin 等对华盛顿都市规划区路网进行分析,
-4
也发现相对误差达到10以后, 路段的流量解才能和算法高度收敛后得出的精确解基本一致, 否则不能满足规划分析的需要. 众所周知, F -W 算法的一个很大的缺点是算法后期收敛很慢, 特别是针对大型交通网络, 很难在短时间内收敛到理想的精确度.
[5]
[4]
作者简介:张天然(1980-) , 男, 浙江省绍兴市人, 博士, 主要研究交通与运输系统规划. E -mail:zhangtian rantj@163. com.
第4期
张天然:改进的交通分配起点用户均衡算法
511
交通分配模型需要对不同的需求状态、基础设施供给方案及其他模型参数进行调试运算, 大量的运算时间已经成为有效应用交通模型的一个瓶颈. 半个多世纪以来, 国外学者一直在寻求更为高效和高精度的算法, 并形成了基于路段、路径和起点3大类算法. 因为基于路段的F -W 算法存在精度低、收敛慢的缺点, 所以寻求改进的算法是十分必要的. Daneva 等[6]提出了改进的F -W 算法) ) ) 共轭F -W 算法, 测试结果表明, 其收敛速度稍逊于Bar -Ger a [7]提出的基于起点的算法(Orig in Based As -sig nm ent, OBA). 共轭F -W 算法也是基于路段的, 保持了内存要求低的优点, 受到了TransCAD 和Cube 等软件的青睐而得到了商业化开发. Bar -Gera 的OBA 算法比F -W 算法在计算速度和精度上有了突破性的改进, 从而使基于起点的交通分配算法成为新的研究热点. Dial 提出了基于起点的B 算法, 其效率相比OBA 算法又有了明显提高. 同时, T ransCAD 软件以B 算法为原型, 开发了起点用户均衡(Origin User Equilibrium, OUE ) 算法; SAT -URN 软件则开发了Bar -Gera 的OBA 算法, Flo -rain
[9]
[8]
E x ij =x ij , P (i, j ) I A , r I R
r r
(1c )
q j =
r
E d
s
rs
, j =r
j =s P j I N , r I R , s I S (1d )
-d rs ,
0, 其他
式中:A 和N 分别为路段和节点的集合; R 和S 分别为起点r 和讫点s 的集合; d rs 为起点到讫点(OD ) 的交通需求, q j 为起点r 到节点j 的交通需求; x ij 为从起点r 出发到所有讫点经过路段的流量, x ij 为路段的总流量; c ij (#) 为严格单调递增的成本函数; P(j ) 和O(j ) 分别为进入节点j 和从j 出发的路段集合.
定义:
(1) 起点r 和网络中的所有节点能单向连通, 有向无环的网络称为起点r 的Bush .
(2) 对一个有向无环网络进行拓扑排序, 将网络中所有节点排成一个序列, 若i 和j 分别是同一路段的起点和讫点, 则i 在序列中总出现在j 之前. 规定起点r 的拓扑顺序为1.
OU E 算法的基本思想:
(1) 一个起点到所有讫点的出行所使用到的路网是一个无环网络, Bar -Gera 称之为限制子网(Re -stricting Sub -Netw or k) , Dial 则称之为Bush. 利用无环网络的节点拓扑排序, 可以十分高效地同时计算最短和最长路径.
(2) 流量从成本大的路径转移到成本小的路径, 并在保证Bush 无环的基础上, 更新Bush 以求找到成本更小的路径. Dial 与Bar -Gera 的算法的不同之处在于前者只将最长路径的流量转移到最短路径, 后者则将所有路径的流量转移到最短路径, 显然, Dial 的方法比较简洁. LU CE 算法是基于讫点的, 其本质和基于起点是相同的, 也是保证有一个无环的Bush, 另外, 流量转移量是将路径成本线性化后计算得到的, 并增加了寻找最优流量转移步长的步骤.
Dial 的流量转移方法如图1所示. 在当前流量解下, 最长和最短路径的成本相差很大, 采用一阶导数近似表示2条路径的成本, 求解流量转移量$x r , 得到近似的均衡解D , 即2条直线的交点. D 点和实际均衡点E 十分接近, 如此往复, 很快能够使2条路径的成本相等. F -W 算法是将所有流量分配到最短路径, 然后通过步长搜索转移流量. F -W 算法在循环迭代的后期, 搜索方向基本和目标函数的梯度方向接近垂直, 收敛速度大为减慢.
r
r
随后也改进了基于路径的投影算法
[10]
, 并在
EM ME 软件中开发了新的模块. Gentile [11]又提出了基于终点的LUCE 算法, 并开发到VISU M 软件中. Bar -Gera 新近又提出了T APAS 算法, 并保证了路径流量的熵值最大化. 不同商业软件开发者和学者的测试结果受到算法自身的特点、代码编写过程、测试用的输入数据和计算机硬件等因素的影响, 使得这些算法很难有一个公平的平台进行比较. M ar -co
[12]
最近分别编写了OBA 和OUE 算法的代码并
对多个路网在同一台计算机上进行了测试, 结果表明OUE 算法比较优秀. 本文基于上述各种算法的优点, 提出了对OUE 算法的改进方法, 讨论算法实现的关键问题, 并在大规模交通网络上来测试算法的效率.
1 OUE 模型及算法
OUE 算法的基本思想是将整个均衡分配问题分解为一个起点到所有讫点的均衡分配问题. Bar -Ger a 指出, Beckmann 的变换式可以改写成基于起点路段流量的形式:min z (x ) =s. t.
k I O(j) [7]
E Q c
ij
x
ij
ij r
(w ) d w
r
(1a ) (1b )
E
x jk -
r
i I P(j)
E
x ij =q j
P j I N , r I R
512
上 海 交 通 大 学 学 报
第45卷
上述流程需要多次循环(即外循环) 才能达到所有起点Bush 达到均衡. Dial 则建议迭代到一个起点的Bush 不再更新为止, 再进入下一个起点.
(2) 一个起点Bush 的均衡解是整个交通分配的子问题, 方法(1) 在每次内循环中求解一个起点Bush 的精确值解对整个算法的收敛效果并不明显. Marco 建议起点Bush 的流量转移需要设置内循环, 只有当一个起点Bush 的流量转移内循环使得局部均衡达到较高程度时, 才进行Bush 的网络更
图1 最长和最短路径之间的流量转移方法F ig. 1 Flo w shift metho d fr om the max -to min -pat h
新. Bar -Gera 则指出他的OBA 算法中, 起点的限制子网(即Bush) 能够很快稳定, 故增加流量转移的内循环是高效的. 因为Bush 更新要比流量转移的计算开销小得多, OU E 算法测试中, 只对一个起点Bush 的流量转移循环2次, 并不考虑其收敛精度. 不同内循环次数下的算法总体收敛测试结果表明,
同一网络并不是内循环的次数越多收敛越快; 次数相同的内循环, 在不同网络中相对于2次内循环的收敛速度有快有慢.
2. 1. 2 成本和成本导数更新流程 在OUE 算法主程序的流量转移步骤¹中, 本文经过多个大型交通网络测试发现, 每个起点Bush 流量更新后, 立即更新路段的成本有利于收敛加速. 另外, 每个起点Bush 流量更新后, 更新路段成本的导数值反而会使收敛大大减慢, 这可能与本文所用的流量更新量计算方法有关. 当然, 为了给Bush 的网络更新做准备, 步骤º的成本和成本导数值更新是必需的. 这是因为Bush 网络更新需要准确的最长和最短路径成本值以保证在更新过程中, Bush 网络保持无环特性.
2. 1. 3 最长和最短路径流量转移方法 首先讨论转移量的计算, 设C 为最长路径成本, 为最短路径成本, z 为当前流量解, $x r 为流量转移量. Dial 使用一阶导数展开后得
z -$x r ) -z +$x r ) U
z ) -(z ) $x r -z ) -(z ) $x r 由此可见, 最长路径转移至最短路径的流量为
$x r =
C(z ) -z ) C c (z ) +(z )
(3)
r
基于上述基本思想, OUE 算法的步骤如下:初始化 对每个起点进行最短路径分配, 最短路径树的所有路段加入到Bush, 并将起点到i 节点最小成本小于j 节点最小成本的路段i -j 加入到Bush, 起点Bush 中的节点进行拓扑排序. 对于热启动计算方法, 则可以将上一次计算结果中Bush 保存的路段作为Bush 初始状态.
算法主程序步骤
(1) 流量转移内循环(Bush 得到稳定后, 流量转移内循环是必要的) .
¹对每个起点的Bush 进行流量转移, 计算起点的最长和最短路径, 反拓扑顺序方向扫描所有节点, 如果进入节点的最长和最短路径的路段相同, 则跳到下一个节点; 否则, 寻找该节点上游最近的最长、最短路径共同节点, 得到2条路径段并转移流量.
º更新路段的成本和成本导数值. 满足内循环收敛条件则转(2) ; 否则, 转¹.
(2) 对所有起点的Bush 进行更新. 先计算流量转移后Bush 的最短和最长路径, 删除Bush 中无流量的路段, 将新的路段加入Bush 中, 以产生成本更小的路径. 如果Bush 得到更新, 则要重新拓扑排序; 如果满足收敛条件, 则退出; 否则, 转(1).
2 算法实现的关键问题及效率测试
2. 1 流量和成本更新策略
2. 1. 1 流量更新流程 OUE 算法是将整个均衡分配问题分解为一个起点到所有讫点的均衡分配问题. 计算方法为:
(1) 一个起点Bush 进行流量转移, 接着更新Bush, 循环操作直至起点Bush 到达设定的均衡解, 更新成本和导数值后, 再对下一个起点的Bush 进行均衡分配, 直至所有起点的Bush 执行完毕. 由于成本更新, 先执行的起点Bush 均衡会受到破坏, 故
(2)
上述拟牛顿法可以通过图1来解释. 如果最长路径(P L ) 上流量最小的路段的起点路段流量x ij 均小于$x r , 则$x r =a min (x a ) , 该规则对目标函数的I P
L
r
下降影响以及搜索步长的研究是必要的(Dial 并没有提出步长搜索方法). 另外, 有些路段可能包含在起点r 到一个讫点的最长路径中, 但同时也包含在
第4期
张天然:改进的交通分配起点用户均衡算法
513
到该讫点的最短路径中. 这样, 有些路段的流量转移可能是无效的或者说是多余的. 根据测试发现, 直接使用最长和最短路径流量转移方法而没有步长搜索, 交通分配模型很难得到收敛. Marco [12]提出了一个启发式的流量转移步长:
if(1. 1@LastRgap
(4)
大于0的路段上构建, 这样对流量转移才有意义, 能加速收敛; 二是路段残余流量会影响Bush 的更新和算法收敛. 如果流量转移后确实是一个很小的流量, 那么在流量转移时需要事先把它完全转移干净. Flor ain 的投影算法中, 建议去除OD 对流量较小的交通需求(如小于0. 1) , 以提高算法收敛速度. 这种方法并不合适, 即使是很小的OD 对流量, 大量的OD 对可能会累加成较大的路段流量, 与路段流量的微小流量去除本质上是不同的.
2. 2 Bush 构建和更新策略
2. 2. 1 Bush 更新的无环保证手段 只有保证Bush 的无环特性, 才能进行节点的拓扑排序, 高效率计算最短和最长路径, 这是OUE 算法的一个重要特征. Dial 指出, 要加入路段a ij 到Bush 中去, 并保证Bush 无环的条件Rule1:
i +C ij
(6)
事实上, 式(6) 并不实用, M ar co 指出只有达到高精度的均衡状态时, 才能保证Bush 无环, 但这样又大大增加了子问题计算开销. 因此, 考虑Bar -Ger a 的无环条件Rule2:
C i
(7)
Marco 进一步修改了Bar -Gera 的无环条件, 认为Bar -Gera 的方法添加了一些无效的路段到Bush 中, 修改的条件Rule3:
C i +C ij
(8)
式中:LastRg ap 为上一次迭代的相对误差; Cur -rentRgap 为当前相对误差; Last K 为上一次流量转移的步长. M arco 使用这种方法使他所编的程序得到了收敛, 但本文采用此方法则没有得到收敛, 这可能和计算流程以及具体的代码实现有关. 因此, 本文则采用Kupiszew ska 和Van Vliet 提出的社会压力来确定步长. 即要寻找一个K , 使得整个起点Bush 的目标函数值在流量转移后得到减小. 条件如下:
$x ij C(x +K $x ij ) [0
r
r
(5)
搜索的步长则可以采用Armijo 规则, 即K =1, , , , , 依次递减. 此方法和Gentile 的LU CE
242算法、Bar -Gera 的OBA 算法步长搜索异曲同工, 是在Dial 的B 算法优点的基础上, 吸取了上述2个算法的长处.
流量转移算法的步骤如下:
(1) 计算起点Bush 的最短和最长路径, 记录起点到节点i 的最短和最长路径成本分别为i 和C i ,
i 和C c i , 如果路径成本差小于设定值, 即导数值 Marco 建议如果Rule1H Rule3=Á, 则采用Rule3. 根据程序试验, M arco 的方法并不能很好地
收敛. 因此, 本文采用的方法是Rule1H Rule3.
在流量转移过程中, 要求最长路径是在流量大于0的路段上构建的, 即这个最长路径树并不包含Bush 中的所有节点. 因此, 遇到没有流量的节点, Rule3很难直接应用. 没有流量的节点, 完全有可能在流量转移后, 经过Bush 更新后, 成为起讫点之间最短路径的组成部分. 单独采用Rule1很容易破坏Bush 的无环特性. 另外, 这样也限制了一些路段的加入, Bush 达不到最优化, 经测试表明, 多数交通网网络相对误差10-4或10-5后就达到极限. 尽管达到这样的精度就可以认为是收敛了, 但毕竟Bush 还没有得到优化, 求解受到了人为约束条件, 并不可取. 因此, 在整个起点Bush 中(即也包含没有流量的路段) 的寻找最长路径也是十分必要的, 这样就可以直接使用Rule3. 可见, OUE 算法实际上要计算2种最长路径树, 分别用于流量转移和Bush 更新. 2. 2. 2 零流量路段的去除 为了保持Bush 的无环性和提高流量转移的效率, 在Bush 更新前, 应该
max (C i -)
成; 否则, 转(2).
(2) 反拓扑顺序, 扫描所有节点i, 如果进入节点i 的最长和最短路径包含的路段相同, 则扫描下一节点; 否则, 转¹.
¹设节点i 为路径段头节点h, 找到2条路径的上游共同节点即路径段尾节点t.
º计算临时流量转移值
C i -r
, min (x $x r =m in a ) a I P
C c i +L
在节点h 至节点t 的最长和最短路径段中记路段临时转移流量$x ij (下一个节点i 执行时, 若路段遇到
重复转移流量, 则需要累加临时转移流量) .
(3) 令K =1,
r
r r
, , , , n , 修改临时流量转移242
r
r
值$x ij z K $x ij , 直至$x ij C (x +K $x ij ) [0.
(4) 对起点Bush 中所有路段执行最后的流量转移值$x ij .
流量转移2个技巧:一是最长路径必须在流量
r
在保证Bush 连通性的基础上, 删除流量为0的路段. 对于有流量的节点, 删除所有进入该节点的非最短路径零流量路段; 对于无流量的节点, 保留进入节点的最短路径路段, 删除其他零流量路段. 这里被包含在最短路径的零流量路段都被保留下来是非常重要的, 可以加速算法收敛.
2. 2. 3 算法优化 算法过程中应该尽量减少不必要的计算, 如零流量路段去除过程, 是对Bush 删除路段. 因此, Bush 的拓扑顺序仍然可用, 没有必要重新排序. 但在Bush 中增加路段后, 则必须重新进行拓扑排序.
2. 3 收敛指标相关问题
交通分配的收敛指标一般用相对误差来表示, Dial 指出可以用OD 对之间的最长和最短路径之差来衡量, 这种方法比较形象地表述了用户均衡分配的概念, 不过F -W 算法没有最长路径计算, 得不到这个指标. 本次测试的收敛指标和T ransCAD 相同:
RelativeGap =
型的特征情况, 体现了路段数、节点数、交通小区数以及OD 需求总量的不同规模.
表1 算法效率测试的交通模型案例Tab. 1 Urban network sizes in algorithm tests
模型苏福尔斯
路段数76
节点数[***********]921847
交通小区数
[***********]59
PCU 总量360600. 001260907. 44369513. 681360427. 8818503872. 005483847. 00
芝加哥骨架网2950惠州
15066
芝加哥区域网39018费城上海
4000362421
由于OU E 算法存在起点Bush 的流量转移和Bush 更新的前后问题, 故很难完全采用多线程的程
序设计, 但可以利用多线程的优势, 对程序计算流程进行适当优化实现局部的多线程. 限于篇幅, 在此不再展开讨论. 表2所示为多线程优化下各算例在相对误差10-2~10-5的不同计算时间.
表2 OUE 算法(多线程) 效率分析
Tab. 2 Eff iciency analysis of the improved OUE algorithm
模型计算时间/s
相对误差10-210-310-410-5
苏福尔斯0. 0050. 0160. 0310. 078
芝加哥骨架网0. 1250. 3681. 2452. 356
惠州1. 9855. 0375. 829
芝加哥区域网29. 160175. 500473. 520
费城20. 76075. 360
上海11. 10052. 560
x
UE
t -
E
x
x UE t
A ON
t
(9)
式(9) 表示当前解与当前流量状态下最短路径解成本的相对差异, 如果这个数值很小, 则说明出行者几乎无法通过改变路径来降低自己的出行成本, 而描述的是一种用户均衡状态. 值得一提的是, 讫点Bush 的最短路径是在限定的Bush 中计算出来的, 如果Bush 还可以优化而没有很好地优化, 则程序计算后期就变成在非最优的Bush 中进行流量转移, 此时式(9) 的相对误差值仍然可以不断减小, 从而造成了算法收敛的假象. 因此, 在整个网络中计算OD 对的最短路径成本, 式(9) 的值也能不断减小才说明收敛是真实的. 2. 4 算法效率测试
本文的OU E 及F -W 算法程序均采用C 语言环境编写, 并采用相同的数据结构, 最短路径算法采用了适合交通网络的双端队列数据结构. 各种算法测试的平台统一是H P XW Workstation, Intel Xe -on(X5460) 8核3. 16GH z 的CPU , 内存为32GB, 操作系统为Window s XP 64位. 为了测试算法的收敛速度, 本文用国内外多个不同规模的交通网络进行了测试. 为了使不同算法具有同样的运算环境, 可以将上海的多车种OD 合并为标准小汽车当量(PCU ) 的单车种OD 进行分配. 所有算例都采用美国联邦公路局的BPR 函数作为路阻函数, 函数的乘数和指数分别为0. 15和4. 0. 表1所示为各交通模
191. 220127. 920390. 720247. 680
42. 4521011. 180
一般地, 相对误差达到10-4时能满足精度要求, 表3给出了4个大型交通网络相对误差达到10-4时采用不同算法所需要的时间. Bar -Gera 的OBA 算法是他提供的可执行文件进行测试的. 要使
相对误差达到10-4, OBA 算法比F -W 算法的时间要多得多, OBA 算法在后期才有优势. OU E 算法则在整个过程都比F -W 算法有优势, Florian 的投影算法和Tr ansCAD 的OUE 算法也有类似性质. 通过改进后的多线程OUE 算法, 计算速度要快于TransCAD5. 0的OU E 算法. 大规模城市交通网络在几分钟内使相对误差达到10-4, 可以满足交通模型调试的需要.
一般情况下, 相对误差10-6以上的精度已经没有太大的实际应用价值, 但是从研究算法的收敛特性来看, 还是值得观察其收敛速度的. 图2和3给出了费城和芝加哥区域网络的更高精度收敛情况. TransCAD5. 0的状态栏中可以看到OUE 算法相
表3 大型网络算法效率对比分析(RelativeGap=10-4)
Tab. 3 Comparison of algorithms in larg e urban
networks(RelativeGap=10-4)
模型计算时间/s
算法
惠州
F -W
Bar -Gera OBA T ran sCAD 5. 0OUE OUE
多线程OU E_MT
213. 127) 6. 28032. 8755. 829
芝加哥区域网3217. 14025854. 060823. 560764. 100473. 520
费城
上海
1870. 020580. 0206872. 280
)
575. 760138. 960336. 480391. 260191. 220127. 920
对误差不断变小的过程, 但由于报告文件中, 没有给出精度在10-6以上的相对误差, 2个图中对应的收敛曲线只能绘制到相对误差10. 图3还给出了TransCAD2006年的OU E 收敛曲线, 但计算使用的CPU 和本次测试不同, 仅作为参考. 从算法后期的收敛情况来看, Bar -Gera 的OBA 算法的收敛具有线性特征. OUE 算法在费城网络中也表现出线性收敛特征, 但在芝加哥区域网中随着精度的提高, 收敛速度略有减慢
.
-6
图2 费城交通网络收敛情况
F ig. 2 T he conver gence in Philadelphia netw
ork
图3 芝加哥区域网收敛情况
Fig. 3 T he converg ence in Chicago reg ional netw or k
从收敛曲线的性质特征来看, OUE 算法的振荡特性要比F -W 算法更为明显. 另外, OUE 算法存在起点Bush 均衡求解的前后问题, 如果算法精度设置太低, 得到的结果是不稳定的. 因此, 在粗略计算交通分配模型, 采用F -W 算法较为合适, OU E 算法比较适合计算精度较高的情形, 如相对误差为10-4左右.
题进行了分析改进, 得到以下结论:
(1) 适当的起点Bush 流量转移内循环次数可以提高算法收敛速度, 但如何优化内循环次数或者起点Bush 的局部收敛精度值得进一步研究.
(2) 流量转移的步长搜索方法可以保证收敛并提高收敛速度.
(3)OUE 算法可以部分地进行多线程流程优化. 本文探讨了Bush 的最长和最短路径对查找方法, 加速收敛的Bush 更新方法. 使用不同规模的城市交通网络模型进行了算法效率测试. 结果表明, 算法效率有较大的提高, 可满足大规模城市交通网络
3 结 论
本文对OUE 算法的流量转移、起点限制子网(Bush) 的更新、成本更新策略及计算流程等关键问
516
上 海 交 通 大 学 学 报
r opean T ranspo rt and contr ibuto rs, 2006.
第45卷
模型计算速度和精度的要求. 算法在多用户多模式分配、路段使用分析功能等模块有待进一步开发.
致谢 感谢美国西北大学M ar co Nie, Citilabs 公司的Zhong ZH OU , Caliper 公司杨齐等人对算法的探讨. 参考文献:
[1] Wa rdrop J G. So me theor etical aspect s o f road traff ic
r esear ch[J]. Proceedings of the Institute of C ivil Eng-i neers , 1952:1(3) :325-378.
[2] Beckmann M , M cG uire C B, W insten C B. Studies in
the eco no mics of tr anspor tation [M ]. New Hav en, Connecticut:Yale U niversit y P ress, 1956.
[3] L eblance L J, M o rlok E K , Pier skalla W. A n eff-i
cient a ppro ach to solving the ro ad netw or k equilibr-i um t raffic assig nment problem [J]. Transportation Research , 1975, 9(5) :309-318.
[4] Bo yce D, R alevic -Dekic B, Bar -Ger a H. Conver gence
of tr affic assignment s:H ow much is enoug h? [J ].Journal of Transportation Engineering , 2004, 130(1) :49-55.
[5] Slav in H B, Rabino wicz A. An empir ical compar ison
of alternativ e user equilibr ium tr affic assignment methods[DB/CD ].Strasbourg :A ssociatio n for Eu -
[6] Danev a M , L indberg P O. A co njug ate direction
Frank -Wo lfe metho d with applicatio ns t o the t raffic assig nment pr oblems [C ]//International C onference on Operations Research 2002. N ew Y or k:Spr inger , 2002:133-138.
[7] Bar -G era H. O r igin -based algo rithm for the t raffic
assig nment pro blem [J ].2002, 36(4) :398-417.
[8] Dial R B. A path -based user -equilibrium traffic as -sig nment alg or ithm that obviates path sto rag e and enumeratio n [J]. Transportation Research Part B , 2006:40(10) :917-936.
[9] Flo rian M. N ew look at pro jected g radient method fo r
equilibr ium
assig nment [D B/CD ].
Washing ton:
T ranspo rtat ion Research Boar d, 2009.
[10] Chen D H , Jayakrishnan L R. Computatio nal study
of state -of -the -art path -based tr affic assignment algo -r ithms[J]. Mathematics and C omputers in Simulation , 2002, 59:509-518.
[11] G ent ile G. L inear user cost equilibrium:A new algo -r ithm fo r t raffic assignment [DB/CD ].Washing ton:
T ranspo rtat ion Research Boar d, 2008.
[12] M arco Y N. A class o f bush -based alg o rithms for the
traffic assignment pr oblem [J]. Transportation Re -search Part B , 2010:44(1) :73-89.
Transportation Science ,
(上接第509页)
[3] Y ang C J, T amashima M , W ang G Q , et al . Predic -tion o f the unsteady perfor mance of co nt ra -ro tating pr opellers by lifting surface theor y[J]. Transactions of the Wes-t Japan Society of Naval Architects , 1992, 83:47-65.
[4] 乔志德, 钟伯文, 吉州. 低噪声对转螺旋桨的翼型-螺旋
桨一体化设计方法[J].西北工业大学学报, 1997, 15(1) :31-36.
QI AO Z h-i de, ZH O NG Bo -w en, JI Zhou. A n inte -g rated design metho d of low no ise contrar otat ing pr o -pellers[J].Journal of Northwestern Polytechnical Un-i versity , 1997, 15(1) :31-36.
[5] 辛公正, 丁恩宝, 唐登海. 对转螺旋桨升力面设计方法
[J].船舶力学, 2006, 10(2) :40-46.
XIN Gong -zheng, DIN G En -bao, T AN G Deng -hai. A desig n method for contr a -rot ating pro peller by lifting -surface method[J]. Journal of Ship Mechanics , 2006, 10(2) :40-46.
[6] Gr eeley D S, Ker w in J E. N umer ical methods fo r pro -peller desig n and analysis in steady flow [J]. SNAME Transactions , 1982, 90:415-453.
[7] 王国强, 胡寿根, 杨晨俊. 螺旋桨性能计算及设计的升
力面方法[J]. 上海交通大学学报, 1988, 22(2) :61-74. W AN G Guo -qiang , H U Sho u -g en, Y A N G Chen -jun. Pr opeller analysis and desig n metho ds by numer ical lifting -surface theor y[J]. Journal of Shanghai Jiaotong University , 1988, 22(2) :61-74.
[8] 张涛, 杨晨俊, 宋保维. 基于M RF 模型的对转桨敞水
性能数值模拟方法探讨[J]. 船舶力学, 2010, 14(8) :847-853.
ZH A NG T ao , YA N G Chen -jun, SON G Bao -wei. In -vestig ations on t he numer ical simulatio n method for the open -water perfo rmance o f contra -r otating propellers based on the M RF mo del[J].Journal of Ship Mechan -ics , 2010, 14(8) :847-853.