• ×

    人物专栏 >> 全部专家列表

    改进的交通分配起点用户均衡算法
    2014-10-11 18:44:36   来源:tranbbs.com      作者:张天然    评论:0 点击:

    摘  要:对起点用户均衡算法的流量转移、起点限制子网(Bush)的更新、成本更新策略及计算流程等关键问题进行了分析改进。探讨了Bush的最长最短路径对查找方法,提出了流量转移的步长搜索方法及加速算法收敛的Bush更新方法,优化了适合多线程开发的算法流程。使用不同规模的城市交通网络模型进行了算法效率测试,并和其他算法进行了对比,结果表明算法效率有较大的提高,可满足大规模城市交通网络模型计算速度和精度的要求。

    关键词:用户均衡交通分配,起点用户均衡算法,无环网络

    Abstract: Key tactics of Origin User Equilibrium (OUE) algorithm such as flow shift from max- to min-paths, bush update and the algorithm’s procedure are studied. The finding of max- min-paths segmentation pair, the step size of bush flow shift and bush construction are studied to speed up the convergence. The algorithm’s procedure is also optimized to take the advantage of multi-thread process. Convergence performances are compared with other algorithms by different size of urban transportation network. The improved OUE algorithm is more efficient and converges satisfactorily in a practical application.

    Key Words: Traffic Assignment, Origin User Equilibrium Algorithm, Acyclic Network

    1        研究背景

    交通分配是交通需求模型的重要构成部分,它描述的是出行者如何在交通网络上选择出行路径。假定在信息完全的情况下,出行者会选择成本最小的路径。Wardrop[1]早在1952年给出了用户均衡(UE)的定义,1Beckmann[2]随后构建了用户均衡交通分配的数学模型,但这一理论直到1975年Leblanc[3]将Frank-Wolfe 算法(简称FW算法)应用到交通分配问题,才得到了广泛地应用。从模型应用的角度,交通规划师和软件工作者面临两个实际问题:交通分配达到什么样的精确度才能满足定量分析的要求?是否有更为高效的算法在最短的时间内达到所要的精度?Boyce等[4]以费城的两条快速路间的一对匝道建设方案使用交通分配模型进行影响范围分析为例,指出相对误差至少要小于1.0e-4,交通分配解的结果才比较可靠。Slavin等[5]等对华盛顿都市规划区路网进行分析,也发现相对误差达到1.0e-4以后,路段的流量解才能和算法高度收敛后得出的精确解基本一致,否则不能满足规划分析的需要。最近Slavin等又用交通分配模型对华盛顿的交通改善项目进行评估,例如增加一个路段的车道数目、新建一座桥梁等。结果表明,相对误差在1.0e-2和1.0e-3的时候,项目的影响范围杂乱无章,毫不相干的某些地区的局部道路的交通量也会有很大的变化,这明显不符合实际情况。而同样的模型输入,当相对误差达到1.0e-4或1.0e-5后,项目的影响主要结果主要集中其周边地区和相关路段,给出的评价结果是可信的。由此可见交通分配求解精确度的需要达到一定程度的重要性。众所周知,FW算法的一个很大的缺点是算法后期收敛很慢,特别是针对大型交通网络,很难在短时间内收敛到理想的精确度。例如上海的多车种分配模型,即使是性能很好的工作站,用FW算法大约需要3个小时才能得到上述相对满意的精度。随着交通网络拥挤程度的增加,收敛速度将变得更慢。交通分配模型需要对不同的需求状态、基础设施供给方案及其他模型参数进行调试运算,大量的运算时间已经成为有效应用交通模型的一个瓶颈。

    责任编辑:millay

    相关热词搜索: 算法 起点 交通

    上一篇:基于GIS的公交模型数据库构建和维护研究
    下一篇:最后一页

    分享到: 收藏
    [专栏文章:4 篇]人物简介
      张天然,博士、高级工程师,毕业于同济大学交通运输规划与管理专业。现任上海市城市规划设计研究院交通模型室副主任。主要研究方向为交通政策和交通模型,交通地理信息等。主持研发上海市交通规划模型,规划信息系统。主持或参与了上海、宁波、深圳等地的交通大调查和数据综合校核工作,上海市轨道交通网络规划等专项规划上海,芜湖、淮安、惠州等地的综合交通规划等多项工作。主持中国铁路改革研究,负责国家863项目城市综合交通规划和政策评价通用软件开发的模型和算法研究。