Computer Engineering and Applications ›› 2018, Vol. 54 ›› Issue (9): 213-217.DOI: 10.3778/j.issn.1002-8331.1612-0102

Previous Articles     Next Articles

Improved Frank-Wolfe algorithm for path traffic flows in traffic assignment problems

CHAI Huo1,2, HE Ruichun2, MA Changxi2, DAI Cunjie1,3   

  1. 1.Mechatronics Technology and Research Institute, Lanzhou Jiaotong University, Lanzhou 730070, China
    2.School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou 730070, China
    3.Engineering Technology Center for Informatization of Logistics & Transport Equipment, Lanzhou 730070, China
  • Online:2018-05-01 Published:2018-05-15

用于求解路径交通流量的改进Frank-Wolfe算法

柴  获1,2,何瑞春2,马昌喜2,代存杰1,3   

  1. 1.兰州交通大学 机电技术研究所,兰州 730070
    2.兰州交通大学 交通运输学院,兰州 730070
    3.甘肃省物流及运输装备信息化工程技术研究中心,兰州 730070

Abstract: Frank-Wolfe algorithm is classic algorithm for traffic assignment problem, but cannot get the path traffic flow because it is a link-based algorithm, an improved algorithm is proposed for the path traffic flow computing based on Frank-Wolfe algorithm. The correspondent module for path traffic flow computing is added to the original algorithm, which is used to update traffic flow of all paths between source and destination(OD) by the traffic flow step size from all or nothing assignment procedure in each iteration, at the same time to obtain the results of path flow in the calculate process of link traffic flow. the experimental results show that the improved algorithm is an efficient algorithm for traffic flow assignment, can be used to solve the path traffic flow by a small amount of time and space costs increased in the Frank-Wolfe algorithm and avoid enumerating all path of the traffic network.

Key words: systems engineering, path traffic flow, Frank-Wolfe algorithm, traffic assignment, user equilibrium

摘要: Frank-Wolfe算法是用于求解交通流量分配问题的经典算法,但该算法是基于路段(Link-Based)的交通流量分配算法,无法用于求解路径交通流量。针对此问题,提出一种用于求解路径交通量的改进Frank-Wolfe算法。通过在Frank-Wolfe原算法中增加求解路径交通流量的计算步骤,根据原算法中“全有全无”加载方法获得的步长,更新源-目的(OD)间所有已配流的路径的交通流量,在原算法迭代计算路段流量的同时,同步计算路径流量。通过算例表明,改进算法是一个有效的算法,在Frank-Wolfe原算法的基础上增加少量的时间和空间成本即可求解路径交通流量,避免穷举交通网络中的所有路径,可以很好地用于用户均衡交通流量分配中。

关键词: 系统工程, 路径交通流量, Frank-Wolfe算法, 交通流量分配, 用户均衡