Adaptation of Network Simplex for the Traffic Assignment Problem

作者：Zheng Hong^*

来源：Transportation Science, 2015, 49(3): 543-558.

DOI：10.1287/trsc.2014.0574

• traffic assignment
• user equilibrium
• network simplex
• spanning tree
• cycles

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.

• 出版日期2015-8