An Augmented Lagrangean Dual Algorithm for Link Capacity
 Side Constrained 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

ABSTRACT:

As a means to obtain a more accurate description of traffic flows than
that provided by the basic model of traffic assignment, there have
been suggestions to impose upper bounds on the link flows.  This can
be done either by introducing explicit link capacities or by employing
travel time functions with asymptotes at the upper bounds.  Although
the latter alternative has the disadvantage of inherent numerical
ill-conditioning, the capacitated assignment model has been studied
and applied to a limited extent, the main reason being that the
solutions can not be characterized by the classical Wardrop
equilibrium conditions; they may, however, be characterized as Wardrop
equilibria in terms of a well-defined, natural generalized travel
cost.

The introduction of link capacity side constraints makes the problem
computationally more demanding.  The availability of efficient
algorithms for the basic model of traffic assignment motivates the use
of dualization approaches for handling the capacity constraints. We
propose and evaluate an augmented Lagrangean dual method in which the
uncapacitated traffic assignment subproblems are solved with the
disaggregate simplicial decomposition algorithm. This algorithm fully
exploits the subproblem's structure and has very favourable
reoptimization capabilities; both these properties are necessary for
achieving computational efficiency in iterative dualization schemes.
The dual method exhibits a linear rate of convergence under a standard
nondegeneracy assumption. The efficiency of the overall algorithm is
demonstrated through experiments with capacitated versions of
well-known test problems, with the conclusion that the introduction of
link capacities increases the computing times with no more than a
factor of four.

The introduction of capacities and the algorithm suggested can be used
to derive tolls for the reduction of flows on overloaded links. The
solution strategy can be applied also to other types of traffic
assignment models where side constraints have been added in order to
refine a descriptive or prescriptive assignment model.

KEY WORDS: Capacitated Traffic Assignment; User Equilibrium; 
Generalized Wardrop Conditions; Queue Equilibrium; Augmented Lagrangean;
Disaggregate Simplicial Decomposition