Fast Traffic Assignment by Focusing on Changing Edge Flows (Extended Abstract)

SOCS-22 Volume 15

Volume

Vol. 15 No. 1 (2022): Fifteenth International Symposium on Combinatorial Search

Extended Abstracts

This paper presents a novel algorithm for solving the traffic assignment problem (TAP). Contrary to traditional algorithms, which use the one-to-all shortest path algorithm to solve the problem for all origin destinations (OD) pairs, this algorithm tracks the changes of the edges and (at certain iterations) solves the problem only for critical edges whose flows have changed substantially using a state-of-the-art edge p2p shortest path algorithm. When additionally, only OD pairs with larger flows are considered, this enhancement halves the time needed to optimize the solution with a very small error in a large-scale network.

10.1609/socs.v15i1.21781