A dual scheme for traffic assignment problems

Abstract

A solution method based on Lagrangean dualization and subgradient optimization for the symmetric traffic equilibrium assignment problem is presented. Its interesting feature is that it includes a simple and computationally cheap procedure for calculating a sequence of feasible flow assignments which tend to equilibrium ones. The Lagrangean subproblem essentially consists of shortest route searches, and it is shown that one may compute an equilibrium flow by taking the simple average of all the shortest route flows obtained during the subgradient optimization scheme, provided that its step lengths are chosen according to a modified harmonic series. The new method is compared to the Frank-Wolfe algorithm and the method of successive averages on a medium-scale problem; its computational performance is at least comparable to that of the two other methods. The main motive for considering this computational methodology is that it may easily be extended and applied to more complex traffic problems; this feature is shared by neither the Frank-Wolfe method nor the state-of-the-art methods for traffic assignment. We outline its extensions to several well-known network models, and illustrate the methodology numerically on one of these, an equilibrium model with link counts; the results obtained are encouraging.