A Dual Scheme for Traffic Assignment Problems

Torbjörn Larsson
Division of Optimization
Department of Mathematics
Linköping Institute of Technology
S-581 83 Linköping
Sweden

Michael Patriksson
Department of Mathematics
Chalmers University of Technology
S-412 96 Gothenburg
Sweden

Zhuangwei Liu
Department of Mathematics 
National University of Singapore
10 Kent Ridge Crescent, 0511
Singapore

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 proce dure for calculating a sequence of
feasible flow assignments which tend to equilibriu m 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 serie s.  The new method is
compared to the Frank--Wolfe algorithm and the method of successive
averages on a medium-scale problem; its computation al performance is
at least comparable to that of the two other methods.

The main motive for considering this computational methodology is that
it may ea sily be extended and applied to more complex traffic
problems; this feature is not share d by neither the Frank--Wolfe
method nor the state-of-the-art methods for traffic ass ignment.  We
outline its extensions to several well-known network models, and
illustrate t he methodology numerically on one of these, an
equilibrium model with link counts; the results obtained are
encouraging.

KEY WORDS: Traffic Assignment, Traffic Equilibrium, Lagrangean
Duality, Subgradient Optimization, Frank--Wolfe Algorithm, Method of
Successive Averages