User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Characteristic functions of directed graphs and applications to stochastic equilibrium problems

Primary tabs

Nesterov, Yurii [UCL]

In this paper we introduce the notions of characteristic and potential functions of directed graphs and study their properties. The main motivation for our research is the stochastic equilibrium traffic assignment problem, in which the drivers choose their routes with some probabilities. Since the number of the strategies in this game is very big, we need to find an efficient way of computation of the expected arc flows in the network. We show that the characteristic functions of the graphs are very useful in this respect. Using this technique we can form and solve numerically the equilibrium traffic assignment problem in a reasonable computational time. As a byproduct of our results we show that the spectral radius of a matrix with non-negative elements admits a convex parametrization as a function of its entries.

Document type Article de périodique (Journal article) – Article de recherche
Publication date 2007
Language Anglais
Journal information "Optimization and Engineering" - Vol. 8, no. 2, p. 193-214 (Juin 2007)
Peer reviewed yes
Publisher Springer New York LLC (New York, USA)
issn 1389-4420
e-issn 1573-2924
Publication status Publié
Affiliations UCL - EUEN/CORE - Center for operations research and econometrics
UCL - FSA/INMA - Département d'ingénierie mathématique
Keywords Stochastic transportation models ; User equilibrium ; Traffic assignment ; Convex optimization
Links
  1. Akamatsu T (1996) Cyclic flows Markov process and stochastic traffic assignment. Transp Res B 30:369–386
  2. Akamatsu T (1997) Decomposition of path choice entropy in general transport networks. Transp Sci 31(4):349–362
  3. Anderson SP, de Palma A, Thisse J-F (1992) Discrete choice theory of product differentiation. MIT, Cambridge
  4. Bell M (1995) Alternatives to dial’s logit assignment algorithm. Transp Res B 298(4):287–295
  5. Nemirovskii A (1995) Polynomial time methods in convex programming. In: Renegar J, Schub M, Smale S (eds) The mathematics of numerical analysis. AMS–SIAM summer seminar in applied mathematics, Park City, UT, 17 July–11 August 1995. Lectures in applied mathematics, vol. 32. Amer Math Soc, Providence
  6. Nesterov Y (2000) Stable traffic equilibria: properties and applications. Optim Eng 1(1):29–50
  7. Nesterov Y, de Palma A (2003) Static equilibrium in congested transportation networks. Networks Spatial Econ 3(3):371–395
  8. Nesterov Yurii, Nemirovskii Arkadii, Interior-Point Polynomial Algorithms in Convex Programming, ISBN:9780898713190, 10.1137/1.9781611970791
  9. Sheffi Y (1985) Urban Transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, Englewood Cliffs
  10. Wardrop JG (1952) Some theoretical aspects of road traffic research. In: Proceedings of the Institute of Civil Engineers, part II, pp. 325–378
Bibliographic reference Nesterov, Yurii. Characteristic functions of directed graphs and applications to stochastic equilibrium problems. In: Optimization and Engineering, Vol. 8, no. 2, p. 193-214 (Juin 2007)
Permanent URL http://hdl.handle.net/2078.1/23373