Abstract: Among existing solution methods for the non-additive traffic assignment problem (NaTAP), only the gradient projection (GP) algorithm solves large-scale networks, indicating an urgent need to explore efficient algorithms that are suitable for real-world traffic networks. In contrast, numerous mature algorithms have been developed for the traditional additive traffic assignment problem (TAP) that efficiently solve large-scale networks. Since NaTAP needs to be modeled and solved in the path flow space, only path-based TAP algorithms such as Greedy, improved social pressure (ISP), path equilibration (PE), projected gradient (PG), and reduced gradient (RG) have potential applicability. To apply ISP, PE, PG, and RG algorithms to NaTAP, a nonlinear programming model is formulated with path flows as variables. In addition, it introduces the Greedy algorithm by exploiting the equivalence between NaTAP and the variational inequality problem (VIP) and proposes a simplex projection (SP) algorithm based on the simplex structure of the VIP feasible set. Within a unified computational framework, the applicability of these algorithms to large-scale NaTAP is systematically evaluated. Numerical experiments demonstrate that GP and SP achieve higher convergence speed and stability, while Greedy and PE exhibit relatively weak stability, and ISP, PG, and RG are inefficient.

Key words: non-additive traffic assignment problem, path-based algorithms, nonlinear programming problem, variational inequality problem, numerical study

摘要： 现有非可加交通分配问题（NaTAP）求解方法中，仅有GP（gradient projection）算法可计算大规模网络，因此亟需探索适用于实际交通网络的高效算法。相较于NaTAP，传统的可加性交通分配问题（TAP）已发展出多种可高效处理大规模网络的成熟算法。由于NaTAP需在路径流空间中建模和求解，TAP算法中，只有Greedy、ISP（improved social pressure）、PE（path equilibration）、PG（projected gradient）和RG（reduced gradient）等基于路径的算法具备潜在适用性。为实现ISP、PE、PG和RG算法在NaTAP中的应用，构建了以路径流量为变量的非线性规划模型；此外，利用NaTAP与变分不等式问题（VIP）的等价性，引入了Greedy算法，并结合VIP可行集的单纯形结构，介绍了一种单纯形投影（simplex projection，SP）算法。在统一的计算框架下，系统评估了上述算法在大规模NaTAP中的适用性。数值实验结果显示，GP和SP具有较高的收敛速度和稳定性，而Greedy与PE的稳定性相对不足，ISP、PG和RG效率较低。

关键词: 非可加交通分配问题, 基于路径的算法, 非线性规划问题, 变分不等式问题, 数值研究