快速收敛的牛顿路径算法在交通分配中的应用

交通运输系统工程与信息 ›› 2014, Vol. 14 ›› Issue (6): 101-106.

快速收敛的牛顿路径算法在交通分配中的应用

程琳^*，孙超, 邵娟

东南大学交通学院，南京210096

收稿日期:2014-04-13 修回日期:2014-09-14 出版日期:2014-12-25 发布日期:2014-12-30
作者简介:程琳（1963-），男，江苏泰州人，教授.
基金资助:
国家自然科学基金（51078085，51178110，51378119）

Path-based Rapid Convergent Newton Algorithm in Traffic Assignment

CHENG Lin, SUN Chao, SHAO Juan

School of Transportation, Southeast University, Nanjing 210096, China

Received:2014-04-13 Revised:2014-09-14 Online:2014-12-25 Published:2014-12-30

摘要/Abstract

摘要：

以确定性交通网络用户均衡问题为研究对象，从理论上推导出以路径费用函数为基础的用户均衡模型，在这基础上，提出快速收敛的牛顿路径算法.该算法每次仅对一OD 对进行牛顿型流量转移，转移完再更新道路流量，提出“更快速度接近均衡解原则”，运用这一原则来简化Hessian 阵，从而得到迭代方向，并通过对原函数二阶泰勒展开式进行一维搜索，寻找出最优步长.将该算法运用于实际交通分配问题，分别对小、中、大三种网络类型进行测试.结果表明，相比于传统的梯度投影算法，快速收敛的牛顿路径算法具有更快的收敛速度和更高的精度，在迭代前期尤为明显.

关键词: 交通工程, 牛顿路径算法, 优化步长, 交通分配, 简化方向

Abstract:

This paper proposes a method for solving the deterministic user equilibrium assignment problem. The UE model based on route cost function is established. Base on this model, path-based rapid convergent Newton (RCN) algorithm is proposed. Each time the traffic flow is diverted for only one OD, and then the flow is updated. We propose the principle of faster speeds approaching equilibrium. Then we simplify the Hessian matrix which can deduce the iterative direction. And through the second-order Taylor expansion, the optimal step size is found. The algorithm is applied to the real traffic assignment problem. Three types (small, medium, large) of traffic networks are tested respectively. Compared to the traditional gradient projection algorithm, path-based rapid convergent Newton algorithm has faster convergence and higher precision, especially in the early iterations.

Key words: traffic engineering, path-based Newton algorithm, optimal step size, traffic assignment, simplified direction

中图分类号:

U491

程琳，孙超, 邵娟. 快速收敛的牛顿路径算法在交通分配中的应用[J]. 交通运输系统工程与信息, 2014, 14(6): 101-106.

CHENG Lin, SUN Chao, SHAO Juan. Path-based Rapid Convergent Newton Algorithm in Traffic Assignment[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(6): 101-106.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: http://www.tseit.org.cn/CN/abstract/abstract18894.shtml

http://www.tseit.org.cn/CN/Y2014/V14/I6/101

参考文献

[1] Meyer M D, Miller E J. Urban transportation planning: a decision- oriented approach[M]. Second Edition. McGraw-Hill Companies, New York, 2001.

[2] Sheffi Y. Urban transportation networks[M]. Englewood Cliffs, New Jersey: Prentice-Hall, 1985.

[3] LeBlanc L J, Morlok E K, Pierskalla W P. An efficient approach to solving equilibrium traffic assignment problem[J]. Transportation Research, 1975, 9: 309-318.

[4] Hearn D W, Lawphongpanich S, Vebtura J A. Restricted simplicial decomposition: Computation and extensions[J]. Mathematical Programming Study, 1987, 31: 99-118.

[5] Larsson T, Patriksson M. Simplicial decomposition with disaggregated representation for the traffic ssignment problem[J]. Transportation Science, 1992, 26: 4-17.

[6] Jayakrishnan R, Tsai W K, Prashker J N, et al. A faster path- based algorithm for traffic assignment[J]. Transportation Research Record, 1994, 1443: 75-83.

[7] Chen A, Jayakrishnan R. A path- based gradient projection algorithm: Effects of equilibration with a restricted path set under two flow update policies[C]. Preprint #981560, in: Proceedings of the Transportation Research Board Annual Meeting, Washington, D.C., 1998.

[8] Cheng L, Xu X D, Qiu S L. Constrained newton methods for transport network equilibrium analysis[J]. Tsinghua Science and Technology, 2009, 14(6): 765-775.

[9] Lee D, Nie Y, Chen A. A conjugate gradient projection algorithm for the traffic assignment problem[J]. Mathematical and Computer Modelling, 2003, 37: 863- 878.

[10] Florian M, Constantin I, Florian D. A new lood at projected gradient method for equilibrium assignment[J]. Transportation Research Record: Journal of the Transportation Research Board, Transportation Research Board of the National Academies, 2009, 2090：10-16.

[11] Bar-Gera H. Origin-based algorithms for transportation network modeling[D]. Chicago：University of Illinois, 1999.

[12] Bar-Gera H. Origin-based algorithm for the traffic assignment problem[J]. Transportation Science, 2002, 36: 398-417.

[13] Chen A, Lee D, Jayakrishnan R. Computational study of state-of-the-art path-based traffic assignment algorithms[J]. Mathematics and Computers in Simulation, 2002, 59:509–518.

[14] 孙超，王欣，童蔚苹，等. 用户均衡与系统最优原则下交通分配模型的建立与分析[J]. 中国科技论文，2013， 8（11）：1073-1077. [SUN C, WANG X, TONG W P, et al. Establishment and analysis of traffic assignment model under the user equilibrium and system optimization principle[J]. China Science Paper, 2013, 8 (11): 1073-1077.]

[15] Nguyen S, Dupuis C. An efficient method for computing traffic equilibria in networks with asymmetric transportation costs[J]. Transportation Science, 1984, 18: 185-202.

[16] LeBlanc L J, Morlok E K, Pierskalla W P. An efficient approach to solving equilibrium traffic assignment problem [J]. Transportation Research, 1975, 9: 309-318.

[17] 郑中元. 城市道路交通网络空间拥堵瓶颈识别[D]. 南京: 东南大学, 2009. [ZHENG Z Y. Identification of bottlenecks in urban road network[D]. Nanjing: Southeast University, 2009.]