Adaptation of Network Simplex for the Traffic Assignment Problem.

This paper presents an algorithm for the traffic assignment problem. The algorithm is characterized by the "origin-based" feature, which solves the user equilibrium flow that is restricted to a single-origin network and loops among origins to produce the all-origin to all-destination equilibrium flow. In contrast to most prior traffic assignment problem algorithms, our method maintains a general spanning tree rooted at each origin, where in-tree arcs can be directed either away from or toward the root. Leveraging an optimality condition in the cycle space, the algorithm uses the network simplex method to identify and cancel a set of negative cost cycles. Numerical experiments demonstrate that the algorithm can generate highly precise solutions with fast convergence on large-scale networks. [ABSTRACT FROM AUTHOR]