改进Frank-Wolfe算法解决路径交通流量问题

"本文主要讨论了在交通流量分配问题中对Frank-Wolfe算法的改进，以解决路径交通流量的问题。传统Frank-Wolfe算法主要用于路段流量分配，而提出的改进算法则能够处理路径流量。通过在原算法基础上增加计算路径流量的步骤，并利用‘全有全无’加载方法更新OD对之间已分配路径的流量，该改进算法在迭代计算路段流量时同步计算路径流量。实验证明，改进算法效率高，只需付出少量额外的时间和空间成本，即可有效解决用户均衡交通流量分配问题，避免了对所有可能路径的穷举。" 在交通工程领域，交通流量分配是一项至关重要的任务，它涉及到城市交通需求预测和网络规划。Wardrop平衡分配原则在此类问题中占有核心地位，分为用户均衡（UE）和系统最优（SO）两种情况。用户均衡考虑的是个体驾驶者寻求最小化其旅行时间，而系统最优则是追求整个交通网络的总体效率最大化。 Frank-Wolfe算法，又称为梯度上升路径算法或局部线性化算法，是LeBlanc首次引入到交通分配问题中的。该算法是一种迭代优化方法，适用于解决凸优化问题，尤其适用于稀疏数据结构。然而，原版的Frank-Wolfe算法仅能处理基于路段的流量分配，不能直接应用于路径级别的流量计算。 针对这一局限，本文提出了一种改进的Frank-Wolfe算法，该算法扩展了原算法的功能，能够同时处理路径交通流量。改进之处在于，在每次迭代过程中，不仅更新路段流量，还根据“全有全无”策略计算和更新OD对之间的路径流量。这种策略意味着如果某个路径在当前迭代中被选择，那么其流量将是满载；如果不被选择，则流量为零。通过这种方式，算法能够在不显著增加计算复杂性的前提下，求解路径级的交通流量分配问题。 实验结果证明，改进后的算法是有效的，能够在保持Frank-Wolfe算法基本效率的同时，增加少量时间和空间成本来解决路径交通流量问题。这为解决大规模交通网络中的用户均衡流量分配提供了新的工具，避免了对所有可能路径进行穷举搜索，从而极大地提高了计算效率。这项工作为交通工程领域的路径流量分配问题提供了一个实用且高效的解决方案。