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

作者：徐猛; 屈云超; 高自友

来源：交通运输系统工程与信息, 2008, (03): 14-22.

DOI：10.16097/j.cnki.1009-6744.2008.03.005

• 交通分配问题
• Frank-Wolfe算法
• 流量更新策略
• 线搜索 traffic assignment problem
• Frank-Wolfe algorithm
• flow update
• line search

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

• 单位
  交通运输学院; 轨道交通控制与安全国家重点实验室; 北京交通大学