Frank-Wolfe算法实现交通平衡配流

资 源 简 介

Frank-Wolfe算法实现交通平衡配流

详 情 说 明

Frank-Wolfe算法是一种用于求解凸优化问题的经典方法，特别适合处理交通平衡配流这类带有线性约束的大规模问题。在交通工程中，平衡配流的目标是根据道路阻抗（如通行时间）将出行需求合理地分配到路网中的各条路径上，最终达到用户均衡状态——即没有任何出行者能够通过单方面改变路径来降低自身出行成本。

Frank-Wolfe算法通过迭代方式逼近最优解。其核心思想是：在每次迭代中，先利用当前解计算目标函数的梯度（即路径阻抗），然后求解一个线性子问题（通常是全有全无分配）生成下降方向，最后通过线搜索确定步长并更新当前解。这种方法的优势在于子问题通常容易求解，且仅需存储当前解而非完整路径流，适合大规模路网。

在交通平衡配流中的应用流程可概括为： 初始化：通常采用自由流状态（零流量）作为起点； 全有全无分配：基于当前阻抗计算最短路径，将所有流量加载到该路径； 线搜索：沿新解方向寻找最优步长，平衡新老路径的阻抗； 迭代终止：当流量变化或阻抗差异小于阈值时停止。

该算法的扩展性较强，可结合启发式步长策略加速收敛，或与BPR函数等非线性阻抗模型配合使用。其局限性在于后期收敛速度较慢，常通过混合算法（如梯度投影）改进。