Linearized simplicial decomposition methods for computing traffic equilibria on networks

Abstract

Abstract This article discusses the solution of the fixed‐demand traffic equilibrium problem by certain linearized simplicial decomposition methods. These methods are derived from the family of linear approximation methods for solving a general variational inequality problem. The central idea of a linearized simplicial decomposition method is that instead of solving linear variational inequality subproblems over the entire set of feasible flows as in a typical linear approximation method, one solves the same subproblems over subsets of feasible flows where each such subset is defined explicitly by certain extreme points of the (polyhedral) set of feasible flows. A global convergence result of the linearized decomposition methods will be established under suitable assumptions on the change of the set of “working” extreme points in each iteration plus some standard conditions on the linear approximating mappings used. Extensive computational results with the use of such methods are reported. Sizes of problems solved range from relatively small to reasonably large.