Network equilibrium models and algorithms. (English) Zbl 0864.90042

Florian, Michael; Hearn, Donald

Ball, M. O. (ed.) et al., Network routing. Amsterdam: North-Holland. Handb. Oper. Res. Manage. Sci. 8, 485-550 (1995).

The general network equilibrium model (NEM) is concerned with determining flow patterns in a network where cost and demand functions governing the flows are nonlinear. The NEM has application to problems in transportation planning, spatial economics, water pipe networks and electrical networks. This chapter provides an overview of the models and algorithms for network equilibrium problems which have been developed over the past 20 years.
The first two sections concentrate on the basic NEM model, giving standard numerical examples from urban traffic assignment. The NEM is formulated as a variational inequality problem and the equivalence with nonlinear complementarily and fixed point formulations is given. Conditions for existence and uniqueness of solutions are then proven. Section 3 contains several optimization reformulations, especially for the case where the cost and demand functions are symmetric. The following two sections describe basic algorithms for symmetric and asymmetric versions of the NEM, including linear approximation, path equilibration, simplicial decomposition, projection and relaxation methods, and dual methods.
Section 6 contains specific examples of NEMs for spatial price equilibrium, water pipe and electrical networks. The final section contains reference notes, including a subsection on specialized topics not covered. The chapter concludes with references to 227 articles and texts in the field.
For the entire collection see [Zbl 0829.00010].

Reviewer: D.Hearn (Gainesville, U.S.A.)

MSC:

90B06	Transportation, logistics and supply chain management
90B10	Deterministic network models in operations research
90C35	Programming involving graphs or networks
49J52	Nonsmooth analysis
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90C33	Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
91D25	Spatial models in sociology

Keywords:

general network equilibrium model; transportation planning; spatial economics; electrical networks; overview; urban traffic assignment; nonlinear complementarily; fixed point; simplicial decomposition