A Primal-Dual Traffic Assignment Algorithm

A new algorithm for solving the traffic assignment problem is presented. This is a primal-dual algorithm which utilizes a flow augmentation primal and a shortest path dual procedure. At each iteration a feasible solution is known together with a measure of “goodness” of the solution.

It is shown that the algorithm converges to an optimal solution. Experience with the algorithm suggests that this convergence is very rapid.