TOWARDS AN OPTIMAL ALGORITHM FOR COMPUTING FIXED POINTS:
DYNAMICAL SYSTEMS APPROACH, WITH APPLICATIONS TO TRANSPORTATION
ENGINEERING
Vladik Kreinovich, Ruey Cheu, Gang Xiang
In many practical problems, it is desirable to find an equilibrium.
For example, equilibria are important in transportation engineering.
Many urban areas suffer from traffic congestion. Intuitively, it may
seem that a road expansion (e.g., the opening of a new road) should
always improve the traffic conditions. However, in reality, a new
road can actually worsen traffic congestion. It is therefore
extremely important that before we start a road expansion project,
we first predict the effect of this project on traffic congestion.
When a new road is built, some traffic moves to this road to avoid
congestion on the other roads; this causes congestion on the new
road, which, in its turn, leads drivers to go back to their previous
routes, etc. What we want to estimate is the resulting equilibrium.
In many problems -- e.g., in many transportation problems -- natural
iterations do not converge. It turns out that the convergence of the
corresponding fixed point iterations can be improved if we consider
these iterations as an approximation to the appropriate dynamical
system.