Many complex transportation models can be formulated as fixed-point problems. Typical examples are the
“equilibrium-like” models, motivated by the need to capture the interaction between the transport supply
(that is, the infrastructure) and transport demand (that is, travelers’ behavior) in various ways.
In this paper, we propose a new approach for solving fixed-point problems and, equivalently, systems of
nonlinear equations. It is a generalization of secant methods, and uses several previous iterates to generate a
linear approximation of the nonlinear function. Although it belongs to the quasi-Newton family of methods, our
algorithm is matrix free, allowing it to solve large-scale systems of equations without derivative and without
any particular assumption about the structure of the problem or its Jacobian.
Computational experiments on standard problems show that this algorithm outperforms classical, large-scale
quasi-Newton methods in terms of efficiency and robustness. Its numerical performances are similar to Newton-
Krylov methods currently considered as the best algorithms to solve large-scale nonlinear systems of equations.
Furthermore, our approach, using multiple previous iterates to build a linear approximation of the nonlinear
function, exhibits robust behavior in the presence of noise in the equations, which makes it particularly well
adapted to transportation problems.
We run our algorithm on a simple origin-destination (OD) matrix estimation problem and on some instances
of the consistent anticipatory route guidance (CARG) problem, to illustrate the applicability of the proposed
method and to show its significant superiority to the classical method of successive averages (MSA). Regarding
size, we were able to solve a CARG problem with more than 120,000 variables. We were also able to solve
classical problems with up to two million variables.
@Article{BierCrit06,
author = {Michel Bierlaire and Frank Crittin},
title = {Solving noisy large scale fixed point problems and systems of nonlinear equations},
journal = {Transportation Science},
year = {2006},
volume = {40},
number = {1},
pages = {44-63},
DOI = {10.1287/trsc.1050.0119}}}
