A Partial Linearization Method for the Traffic Assignment Problem

Torbjörn Larsson, Athanasios Migdalas and Michael Patriksson
Department of Mathematics
Linköping Institute of Technology
S-581 83 Linköping
Sweden

ABSTRACT:

This paper presents a new solution technique for the 
traffic assignment problem. The approach is based on an
iteratively improved nonlinear and separable approximation of 
the originally nonseparable objective function,
and resembles the Frank-Wolfe algorithm in the sense
that the subproblem separates with respect to commodities.
Since the single-commodity subproblems are strictly
convex, the new algorithm will not suffer from the poor
convergence behaviour of the Frank-Wolfe algorithm, which is a
consequence of the extreme solutions of its linear subproblems.
The solution method is outlined along with convergence results,
and a dual approach to the solution of the strictly convex
subproblems is described. The performance of the algorithm is 
illustrated with two numerical examples.
 
KEY WORDS: Traffic Assignment, Convex Multi-Commodity Network Flows,
Feasible Direction Methods, Frank-Wolfe Algorithm, Partial Linearization, 
Lagrangean Duality, Coordinate Ascent