Frank-Wolfe算法求解交通分配问题: 比较不同流量更新策略和线搜索技术

交通运输系统工程与信息 ›› 2008, Vol. 8 ›› Issue (3): 14-22 .

• 智能交通系统与信息技术 • 上一篇下一篇

Frank-Wolfe算法求解交通分配问题: 比较不同流量更新策略和线搜索技术

徐猛^*a;屈云超^a;高自友^b

(北京交通大学:a. 交通运输学院系统科学所;b.轨道交通控制与安全国家重点实验室。北京 100044

收稿日期:2007-12-17 修回日期:2008-02-26 出版日期:2008-06-25 发布日期:2008-06-25
通讯作者: 徐猛
作者简介:徐猛（1976-），男，湖北松滋人，博士.
基金资助:
国家自然科学基金（70771005）；国家重点基础研究发展计划（973计划，2006CB705503）；教育部博士点新教师基金（20070004045）.

Implementing Frank-Wolfe Algorithm for Traffic Assignment Problem under Different Flow Update Strategies and Line Search Technologies

XU Meng^a;QU Yun-chao^a;GAO Zi-you^b

a.School of Traffic and Transportation,b. State Key Laboratory of Rail Traffic Control and Safety, Beijing Jiaotong University, Beijing, 100044, China

Received:2007-12-17 Revised:2008-02-26 Online:2008-06-25 Published:2008-06-25
Contact: XU Meng

摘要/Abstract

摘要： Frank-Wolfe(FW)算法是一类广泛应用于求解交通分配问题的算法。它具有容易编程实现，所需内存少的特点。但是该算法收敛速度较慢，不能得到路径信息。为了提高算法的效率，本文研究三种流量更新策略(all-at-once, one-origin-at-a-time, one-OD-at-a-time)以及不同的步长搜索策略下的FW算法，其中步长搜索策略包括精确线性搜索方法(包括二分法、黄金分割法、成功失败法)和不精确的线性搜索方法(包括基于Wolfe-Powell收敛准则的搜索方法和Gao等提出的非单调线性搜索方法)。最后，本文将上述策略应用于四种不同规模的交通网络中，并给出较适合求解的组合。

关键词: 交通分配问题, Frank-Wolfe算法, 流量更新策略, 线搜索

Abstract: Frank-Wolfe (FW) algorithm is widely used to solve traffic equilibrium assignment problems. It has the characteristics of simple implementing and modest memory requiring. However, it also faces some problems such as slow convergence, no providing path information, and so on.In order to improve its implementation efficiency, the FW algorithm is further studied from three flow update strategies (all-at-once, one-origin-at-a-time, one-OD-at-a-time) and different step search methods, which includes deterministic line search methods (bisection method, golden-section method, success-failure method) and non-deterministic line search methods (a search method based on the basis of Wolfe-Powell convergent criterion, and a nonmonotone line search method). Four different scales transportation networks are used to test the different update strategies finally.

Key words: traffic assignment problem, Frank-Wolfe algorithm, flow update, line search

中图分类号:

U491

徐猛,屈云超,高自友. Frank-Wolfe算法求解交通分配问题: 比较不同流量更新策略和线搜索技术[J]. 交通运输系统工程与信息, 2008, 8(3): 14-22 .

XU Meng,QU Yun-chao,GAO Zi-you. Implementing Frank-Wolfe Algorithm for Traffic Assignment Problem under Different Flow Update Strategies and Line Search Technologies[J]. Journal of Transportation Systems Engineering and Information Technology, 2008, 8(3): 14-22 .

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

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

http://www.tseit.org.cn/CN/Y2008/V8/I3/14

参考文献

[1] Chen, A., Jayakrishnan R, Tsai W K., Accelerating the convergence of the frank-wolfe algorithm for the traffic assignment problem with one-at-a-time flow update strategy[J]. Journal of Transportation Engineering, 2002,128(1), 31-39.

[2] Chen A., Effects of flow update strategies on the implementation of the frank-wolfe algorithm for the traffic assignment problem[R], Transportation Research Record, 2001 1771:132-139.

[3] Jayakrishnan, R, Tsai, W K., Prashker, J N., Rajadhyaksha S. A Faster Path-based Algorithm for Traffic Assignment[R], Transportation Research Record, 1994 1443: 75-83.

[4] Sheffi Y. Urban Traffic Networks: Equilibrium Analysis with Mathematical Programming Methods[M], Prentice-Hall, Englewood Cliffs, NJ, 1985.

[5] 王京元，程琳, 最短路拍卖算法在交通分配中的应用[J], 交通运输系统工程与信息, 2006, 6 (6): 79-82.[WANG Jin-yuan, CHEN Lin, Application of auction algorithm for shortest paths in traffic assignment[J], Journal of Transportation Systems Engineering and Information Technology, 2006, 6 (6): 79-82.]

[6] 司徒惠源，罗康锦, 动态交通分配:回顾及前瞻[J], 交通运输系统工程与信息, 2005, 5 (5): 85- 95.[Szeto,W Y, Lo H K., Dynamic traffic assignment: review and future research directions[J], Journal of Transportation Systems Engineering and Information Technology, 2005, 5 (5): 85- 95.]

[7] 李志纯，黄海军, 随机交通分配中有效路径的确定方法[J], 交通运输系统工程与信息, 2003, 3 (1): 28-32. [LI Zhi-chun, HUANG Hai-jun, Determining the efficient paths in stochastic traffic assignment[J], Journal of Transportation Systems Engineering and Information Technology, 2003, 3 (1): 28-32.]

[8] 李峰，王书宁，基于终点的路径交通量求解方法[J]，清华大学学报(自然科学版）,2006,46(1):149-152[LI Feng, WANG Shu-ning, Destination-based approach for routing traffic flows in traffic assignment problems[J], Journal of Tsinghua University (Science and Technology), 2006,46(1):149-152.]

[9] Patriksson, M., The Traffic Assignment Problem: Models and Methods[M], VSP, Utrecht, The Netherlands, 1994.

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

[11] Boyce D., Bar-Gera H., Convergence of traffic assignments: how much is enough[J]. Journal of Transportation Engineering, 2004,130(1), 49-55.

[12] Frank M, Wolfe P. An algorithm for quadratic programming[J], Naval Research Logistics Quarterly, 1956, 3: 95-110.

[13] 黄海军, 城市交通网络平衡分析——理论与实践[M], 北京：人民交通出版社, 1994. [HUAGN Hai-jun, Urban Transportation Network Equilibrium Analysis: Theory and Practice[M],Beijing: China Communications Press, 1994.]

[14] Miller R E., Optimization[M], Wiley, New York, 2000.

[15] Wolfe P. Convergence Theory in Non-linear Programming, Integer and Non-linear Programming[M], North Holland, Amsterdam, 1970.

[16] Gao, Z Y., Lam, W H K., Wong, S C., Yang, H, The convergence of equilibrium algorithm with non-monotone line search technique[J], Applied Mathematics and Computation, 2004,148(1), 1-13.

Frank-Wolfe算法求解交通分配问题: 比较不同流量更新策略和线搜索技术

Implementing Frank-Wolfe Algorithm for Traffic Assignment Problem under Different Flow Update Strategies and Line Search Technologies

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张雷元, 吴晓峰, 徐棱. 城市交通信号一体化管理平台研究与应用[J]. 交通运输系统工程与信息, 2012, 12(增1): 50-55.
[2]	王许涛, 姚恩建, 邱奉翠, 李建军. 基于交通信息路网覆盖率的浮动车配置优化研究[J]. 交通运输系统工程与信息, 2012, 12(增1): 62-67.
[3]	张万安, 肖跃秀. 机动车驾驶人道路交通违法行为的博弈分析[J]. 交通运输系统工程与信息, 2012, 12(增1): 86-90.
[4]	胡江碧, 朱强斌. 高速公路立交区交通安全系统技术研究[J]. 交通运输系统工程与信息, 2012, 12(增1): 99-105.
[5]	龚峻峰, 苏奎, 何兆成, 沙志仁, 陈晓翔. 广州市路网交通状态评价方法及其在亚运交通管控分析中的应用[J]. 交通运输系统工程与信息, 2012, 12(增1): 106-112.
[6]	张国伍. 枢纽机场与区域经济发展——机场对区域经济发展影响 ——“交通7+1论坛”第二十六次会议纪实[J]. 交通运输系统工程与信息, 2012, 12(2): 1-8.
[7]	杨珍珍, 干宏程. 车载导航系统的市场渗透率仿真研究[J]. 交通运输系统工程与信息, 2012, 12(2): 53-61.
[8]	饶宗皓, 姚恩建. 基于路段属性变量的浮动车覆盖率模型研究[J]. 交通运输系统工程与信息, 2012, 12(2): 62-66.
[9]	孙华, 高自友. 基于走行时间鲁棒可靠性的随机交通均衡问题[J]. 交通运输系统工程与信息, 2012, 12(2): 76-84.
[10]	梁肖, 毛保华, 许奇. 自行车微观行为的心理生理力模型[J]. 交通运输系统工程与信息, 2012, 12(2): 91-97.
[11]	诸葛承祥, 邵春福, 李霞, 孟梦. 通勤者出行时间与出行方式选择行为研究[J]. 交通运输系统工程与信息, 2012, 12(2): 126-131.
[12]	张蕊, 杨静, 雷熙文. 城市交通出行方式选择的随机弹性分析[J]. 交通运输系统工程与信息, 2012, 12(2): 132-136.
[13]	王孝之, 赵胜川, 闫祯祯. 基于Rank Logit模型对城际交通分担率的计算方法研究[J]. 交通运输系统工程与信息, 2012, 12(2): 137-143.
[14]	宋晓梅, 于雷. 常规公交微观区间运行时间可靠性评价模型研究[J]. 交通运输系统工程与信息, 2012, 12(2): 144-149.
[15]	高万宝, 吴坚, 邹娇. 基于实时密度的入口匝道控制算法研究[J]. 交通运输系统工程与信息, 2012, 12(2): 150-155.