论文标题
瞬时动态平衡流的有限时间组合算法
A Finite Time Combinatorial Algorithm for Instantaneous Dynamic Equilibrium Flows
论文作者
论文摘要
瞬时动态平衡（IDE）是动态交通分配中的标准游戏理论概念，在该概念中，单个流动粒子在当前通往其目的地的最短路径上近距离选择。我们分析了Vickrey瓶颈模型中的IDE，其中当前沿着路径的旅行时间包括物理旅行时间以及沿路径所有队列中的等待时间之和。尽管已经研究了IDE数十年，但尚不清楚有关平衡计算和复杂性的几个基本问题。特别是，所有存在的结果和计算方法均基于定理和数值离散方案，并且尚无确切的有限时间算法用于均衡计算。作为我们的主要结果，我们表明，天然扩展算法只需要有限的许多阶段即可收敛，从而导致第一个有限的时间组合算法计算IDE。我们通过几个硬度结果来补充这一结果，表明具有自然特性的计算IDE是NP- hard。
Instantaneous dynamic equilibrium (IDE) is a standard game-theoretic concept in dynamic traffic assignment in which individual flow particles myopically select en route currently shortest paths towards their destination. We analyze IDE within the Vickrey bottleneck model, where current travel times along a path consist of the physical travel times plus the sum of waiting times in all the queues along a path. Although IDE have been studied for decades, several fundamental questions regarding equilibrium computation and complexity are not well understood. In particular, all existence results and computational methods are based on fixed-point theorems and numerical discretization schemes and no exact finite time algorithm for equilibrium computation is known to date. As our main result we show that a natural extension algorithm needs only finitely many phases to converge leading to the first finite time combinatorial algorithm computing an IDE. We complement this result by several hardness results showing that computing IDE with natural properties is NP-hard.
