Cost scaling based successive approximation algorithm for the traffic assignment problem |
| |
Affiliation: | 1. University of Luxembourg, FSTC, 6 rue Richard Coudenhove-Kalergi, L-1359 Luxembourg, Luxembourg;2. KU Leuven, L-Mob Leuven Mobility Research Centre, Celestijnenlaan 300A, 3001 Leuven, Belgium;1. Department of Civil and Environmental Engineering, National University of Singapore, Singapore;2. School of Transportation, Southeast University, China |
| |
Abstract: | This paper presents a cost scaling based successive approximation algorithm, called ε-BA (ε-optimal bush algorithm), to solve the user equilibrium traffic assignment problem by successively refining ε-optimal flows. As ε reduces to zero, the user equilibrium solution is reached. The proposed method is a variant of bush-based algorithms, and also a variant of the min-mean cycle algorithm to solve the min-cost flow by successive approximation. In ε-BA, the restricted master problem, implying traffic equilibration restricted on a bush, is solved to ε-optimality by cost scaling before bush reconstruction. We show that ε-BA can reduce the number of flow operations substantially in contrast to Dial’s Algorithm B, as the former operates flows on a set of deliberately selected cycles whose mean values are sufficiently small. Further, the bushes can be constructed effectively even if the restricted master problem is not solved to a high level of convergence, by leveraging the ε-optimality condition. As a result, the algorithm can solve a highly precise solution with faster convergence on large-scale networks compared to our implementation of Dial’s Algorithm B. |
| |
Keywords: | Traffic assignment Successive approximation Cost scaling Min-mean cycle Bush |
本文献已被 ScienceDirect 等数据库收录! |
|