论文标题
通过稳定动力学模型和贝克曼模型的原始偶梯度方法在交通分配问题中找到平衡
Finding Equilibria in the Traffic Assignment Problem with Primal-Dual Gradient Methods for Stable Dynamics Model and Beckmann Model
论文作者
论文摘要
在本文中，我们考虑了多种梯度方法在交通分配问题中的应用：我们在稳定的动态模型（Nesterov和de Palma，2003年）和Beckmann模型中搜索平衡。与著名的弗兰克（Frank）不同 - 沃尔夫（Wolfe）算法广泛用于贝克曼（Beckmann）模型，这些渐变方法解决了双重问题，然后重建了原始方法的解决方案。我们处理通用梯度方法，类似三角形的通用方法以及加权双平均值的方法，并估计其对问题的复杂性。由于这些方法的原始偶性性质，我们在停止标准中使用偶性差距。特别是，我们提出了一种新颖的方法，可以重建可允许的流动（即满足容量约束并在路径上的流量引起的容量约束），这为我们提供了可计算的偶性差距。
In this paper we consider the application of several gradient methods to the traffic assignment problem: we search equilibria in the stable dynamics model (Nesterov and De Palma, 2003) and the Beckmann model. Unlike the celebrated Frank--Wolfe algorithm widely used for the Beckmann model, these gradients methods solve the dual problem and then reconstruct a solution to the primal one. We deal with the universal gradient method, the universal method of similar triangles, and the method of weighted dual averages, and estimate their complexity for the problem. Due to the primal-dual nature of these methods, we use a duality gap in a stopping criterion. In particular, we present a novel way to reconstruct admissible flows (i.e.,\ meeting the capacity constraints and induced by flows on the paths) in the stable dynamics model, which provides us with a computable duality gap.
