优化Frank-Wolfe算法：交通分配问题中的流量更新与线搜索策略对比

"本文主要探讨了Frank-Wolfe算法在解决交通分配问题中的应用，重点关注了不同流量更新策略和线搜索技术对算法效率的影响。研究中对比了all-at-once、one-origin-a-time、one-OD-a-time这三种流量更新策略，并结合精确线性搜索（如二分法、黄金分割法、成功失败法）和不精确线性搜索（如基于Wolfe-Powell收敛准则及非单调线性搜索方法）进行了分析。实验结果表明这些策略和搜索方法在不同规模的交通网络中有各自的优劣，并给出了适合不同情况的最佳组合。" Frank-Wolfe算法，又称Frank-Wolfe（FW）算法或梯度下降投影算法，是一种在凸优化问题中广泛应用的迭代算法，特别适合处理那些具有稀疏最优解的大型线性规划问题。在交通分配问题中，FW算法因其简洁的编程实现和较低的内存需求而受到青睐。然而，该算法的收敛速度较慢，且无法直接获得最优路径信息，因此需要通过优化流量更新策略和步长搜索技术来提高效率。 流量更新策略是决定算法性能的关键因素之一。all-at-once策略是指在每次迭代时更新所有边的流量；one-origin-a-time策略则按每个起始点依次更新流量；而one-OD-a-time策略则是针对每一对起源地-目的地（OD对）单独更新流量。每种策略都有其独特的优势和适用场景，例如one-OD-a-time策略可能在处理大规模网络时能减少计算量，而all-at-once策略可能在某些情况下能更快达到全局最优。 线搜索技术用于确定每一步迭代的步长，以平衡算法的收敛速度和精度。精确线性搜索方法如二分法、黄金分割法和成功失败法能确保找到全局最优步长，但计算成本较高；不精确线性搜索方法如基于Wolfe-Powell收敛准则的搜索和非单调线性搜索则在保证一定收敛性的前提下，寻求更高效的步长选择，减少了计算负担。 在实际应用中，研究者将上述策略和搜索技术应用于四种不同规模的交通网络，通过对比分析，得出了最佳的组合方案，这对于实际交通管理和优化提供了有价值的参考。通过这种针对性的研究，可以进一步提升FW算法在交通分配问题中的求解效率，同时为其他类似问题的解决提供借鉴。 关键词：交通分配问题；Frank-Wolfe算法；流量更新策略；线搜索技术。