Origin-Based Algorithm for the Traffic Assignment Problem

We present an origin-based algorithm for the traffic assignment problem, which is similar conceptually to the algorithm proposed by Gallager and Bertsekas for routing in telecommunication networks. Apart from being origin-based, the algorithm is different from other algorithms used so far for the traffic assignment problem by its restriction to acyclic solutions and by the use of approach proportions as solution variables. Projected quasi-Newton search directions are used to shift flows effectively and to eliminate residual flows. Experimental results comparing the proposed algorithm with the state-of-the-practice algorithm of Frankand Wolfe demonstrate the algorithm's excellent convergence performance, especially when highly accurate solutions are needed. Reasonable memory requirements make this algorithm applicable to large-scale networks. The resulting solution has an immediate route flow interpretation, thus providing equivalent detail to route-based solutions.