On the convergence of the method of successive averages for calculating equilibrium in traffic networks

Richard Mounce, Malachy Carey

Research output: Contribution to journalArticle

11 Citations (Scopus)

Abstract

The traffic assignment problem aims to calculate an equilibrium route flow vector, generally by seeking a zero of an appropriate objective function. If a continuous dynamical system follows a descent direction for this objective function at each non-equilibrium route flow vector, the system converges to equilibrium. It is shown that when this dynamical system is discretised with a fixed step length the system eventually approaches close to equilibrium provided that the objective function is continuously differentiable and that the rate of descent is bounded below. Widely used in traffic assignment is the method of successive averages (MSA), which has a decreasing step size at each iteration. With the same conditions as above, it is shown that the resulting dynamical system converges to equilibrium. In the steady state model the necessary conditions are shown to be satisfied provided that the route cost vector is a continuously differentiable monotone function of the route flow vector. In the dynamic queueing model the necessary conditions for convergence are shown not to hold.
Original languageEnglish
Pages (from-to)535-542
JournalTransportation Science
Volume49
Issue number3
DOIs
Publication statusPublished - Aug 2015

Fingerprint

Dynamical systems
Costs

Keywords

  • method of successive averages
  • equilibrium
  • traffic assignment
  • step length

Cite this

@article{01f2d2f06c1945219ebaa6a065c06b33,
title = "On the convergence of the method of successive averages for calculating equilibrium in traffic networks",
abstract = "The traffic assignment problem aims to calculate an equilibrium route flow vector, generally by seeking a zero of an appropriate objective function. If a continuous dynamical system follows a descent direction for this objective function at each non-equilibrium route flow vector, the system converges to equilibrium. It is shown that when this dynamical system is discretised with a fixed step length the system eventually approaches close to equilibrium provided that the objective function is continuously differentiable and that the rate of descent is bounded below. Widely used in traffic assignment is the method of successive averages (MSA), which has a decreasing step size at each iteration. With the same conditions as above, it is shown that the resulting dynamical system converges to equilibrium. In the steady state model the necessary conditions are shown to be satisfied provided that the route cost vector is a continuously differentiable monotone function of the route flow vector. In the dynamic queueing model the necessary conditions for convergence are shown not to hold.",
keywords = "method of successive averages, equilibrium, traffic assignment, step length",
author = "Richard Mounce and Malachy Carey",
note = "Reference text: Bar-Gera H, Boyce D (2006) Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes. Transportation Res. Part B 40:351–367. Bernstein DH (1990) Programmability of continuous and discrete network equilibria. Unpublished doctoral thesis, University of Illinois at Chicago, Chicago. Dial RB (2006) A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration. Transportation Res. Part B 40:917–936. Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer. Math. 1:269–271. Du J, Wong SC, Shu C, Xiong T, Zhang M, Choi K (2013) Revisiting Jiang’s dynamic continuum model for urban cities. Transportation Res. Part B 56:96–119. Dunn JC (1976) Convexity, monotonicity, and gradient processes in Hilbert space. J. Math. Anal. Appl. 53:145–158. Dunn JC, Harshbarger S (1978) Conditional gradient algorithms with open loop step size rules. J. Math. Anal. Appl. 62:432–444. Kreyszig E (1978) Introductory Functional Analysis with Applications (John Wiley & Sons, New York). LeBlanc LJ, Morlok EK, Pierskalla W (1975) An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Res. Part B 9:309–318. Liu HX, He X, He B (2009) Method of successive weighted averages (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem. Networks and Spatial Econom. 9:485–503. Lyapunov AM (1907) Probl{\`e}me g{\'e}n{\'e}ral de la stabilit{\'e} du mouvement. Ann. Fac. Sci. Univ. Toulouse 9(2):203–474. Reprint (1949) Ann. Math. Studies, no. 17 (Princeton University Press, Princeton, NJ). [Original paper published in 1892 in Comm. Soc. Math. Kharkov (Russian).] Magnanti TL, Perakis G (1997) Averaging schemes for variational inequalities and systems of equations. Math. Oper. Res. 22:568–587. Mounce R (2006) Convergence in a continuous dynamic queueing model for traffic networks. Transportation Res. Part B 40:779–791. Mounce R, Carey M (2010) Route swap processes and convergence measures in dynamic traffic assignment. Tamp{\'e}re CMJ, Viti F, Immers LH, eds. New Developments in Transport Planning: Advances in Dynamic Traffic Assignment (Edward Elgar, Cheltenham, UK), 107–130. Mounce R, Carey M (2011) Route swapping in dynamic traffic networks. Transportation Res. Part B 45:102–111. Mounce R, Smith M (2007) Uniqueness of equilibrium in steady state and dynamic traffic networks. Allsop RE, Bell MGH, Heydecker BG, eds. Transportation and Traffic Theory (Emerald Group Publishing, Bingley, UK), 281–299. Nie Y (2010) A class of bush-based algorithms for the traffic assignment problem. Transportation Res. Part B 44:73–89. Powell WB, Sheffi Y (1982) The convergence of equilibrium algorithms with predetermined step sizes. Transportation Sci. 16:45–55. Schauder J (1930) Der Fixpunktsatz in Funktionalr{\"a}umen. Studia Mathematica 2:171–180. Sheffi Y (1985) Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods (Prentice-Hall, Englewood Cliffs, NJ). Smith MJ (1984a) A descent algorithm for solving monotone variational inequalities and monotone complementarity problems. J. Optim. Theory Appl. 44:485–498. Smith MJ (1984b) The stability of a dynamic model of traffic assignment—An application of a method of Lyapunov. Transportation Sci. 18:245–252. Smith MJ, Wisten MB (1995) A continuous day-to-day traffic assignment model and the existence of a continuous dynamic user equilibrium. Ann. Oper. Res. 60:59–79. Williams JWJ (1964) Algorithm 232: Heapsort. Comm. ACM 7:347–348.",
year = "2015",
month = "8",
doi = "10.1287/trsc.2014.0517",
language = "English",
volume = "49",
pages = "535--542",
journal = "Transportation Science",
issn = "0041-1655",
number = "3",

}

On the convergence of the method of successive averages for calculating equilibrium in traffic networks. / Mounce, Richard; Carey, Malachy.

In: Transportation Science, Vol. 49, No. 3, 08.2015, p. 535-542.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On the convergence of the method of successive averages for calculating equilibrium in traffic networks

AU - Mounce, Richard

AU - Carey, Malachy

N1 - Reference text: Bar-Gera H, Boyce D (2006) Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes. Transportation Res. Part B 40:351–367. Bernstein DH (1990) Programmability of continuous and discrete network equilibria. Unpublished doctoral thesis, University of Illinois at Chicago, Chicago. Dial RB (2006) A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration. Transportation Res. Part B 40:917–936. Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer. Math. 1:269–271. Du J, Wong SC, Shu C, Xiong T, Zhang M, Choi K (2013) Revisiting Jiang’s dynamic continuum model for urban cities. Transportation Res. Part B 56:96–119. Dunn JC (1976) Convexity, monotonicity, and gradient processes in Hilbert space. J. Math. Anal. Appl. 53:145–158. Dunn JC, Harshbarger S (1978) Conditional gradient algorithms with open loop step size rules. J. Math. Anal. Appl. 62:432–444. Kreyszig E (1978) Introductory Functional Analysis with Applications (John Wiley & Sons, New York). LeBlanc LJ, Morlok EK, Pierskalla W (1975) An efficient approach to solving the road network equilibrium traffic assignment problem. Transportation Res. Part B 9:309–318. Liu HX, He X, He B (2009) Method of successive weighted averages (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem. Networks and Spatial Econom. 9:485–503. Lyapunov AM (1907) Problème général de la stabilité du mouvement. Ann. Fac. Sci. Univ. Toulouse 9(2):203–474. Reprint (1949) Ann. Math. Studies, no. 17 (Princeton University Press, Princeton, NJ). [Original paper published in 1892 in Comm. Soc. Math. Kharkov (Russian).] Magnanti TL, Perakis G (1997) Averaging schemes for variational inequalities and systems of equations. Math. Oper. Res. 22:568–587. Mounce R (2006) Convergence in a continuous dynamic queueing model for traffic networks. Transportation Res. Part B 40:779–791. Mounce R, Carey M (2010) Route swap processes and convergence measures in dynamic traffic assignment. Tampére CMJ, Viti F, Immers LH, eds. New Developments in Transport Planning: Advances in Dynamic Traffic Assignment (Edward Elgar, Cheltenham, UK), 107–130. Mounce R, Carey M (2011) Route swapping in dynamic traffic networks. Transportation Res. Part B 45:102–111. Mounce R, Smith M (2007) Uniqueness of equilibrium in steady state and dynamic traffic networks. Allsop RE, Bell MGH, Heydecker BG, eds. Transportation and Traffic Theory (Emerald Group Publishing, Bingley, UK), 281–299. Nie Y (2010) A class of bush-based algorithms for the traffic assignment problem. Transportation Res. Part B 44:73–89. Powell WB, Sheffi Y (1982) The convergence of equilibrium algorithms with predetermined step sizes. Transportation Sci. 16:45–55. Schauder J (1930) Der Fixpunktsatz in Funktionalräumen. Studia Mathematica 2:171–180. Sheffi Y (1985) Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods (Prentice-Hall, Englewood Cliffs, NJ). Smith MJ (1984a) A descent algorithm for solving monotone variational inequalities and monotone complementarity problems. J. Optim. Theory Appl. 44:485–498. Smith MJ (1984b) The stability of a dynamic model of traffic assignment—An application of a method of Lyapunov. Transportation Sci. 18:245–252. Smith MJ, Wisten MB (1995) A continuous day-to-day traffic assignment model and the existence of a continuous dynamic user equilibrium. Ann. Oper. Res. 60:59–79. Williams JWJ (1964) Algorithm 232: Heapsort. Comm. ACM 7:347–348.

PY - 2015/8

Y1 - 2015/8

N2 - The traffic assignment problem aims to calculate an equilibrium route flow vector, generally by seeking a zero of an appropriate objective function. If a continuous dynamical system follows a descent direction for this objective function at each non-equilibrium route flow vector, the system converges to equilibrium. It is shown that when this dynamical system is discretised with a fixed step length the system eventually approaches close to equilibrium provided that the objective function is continuously differentiable and that the rate of descent is bounded below. Widely used in traffic assignment is the method of successive averages (MSA), which has a decreasing step size at each iteration. With the same conditions as above, it is shown that the resulting dynamical system converges to equilibrium. In the steady state model the necessary conditions are shown to be satisfied provided that the route cost vector is a continuously differentiable monotone function of the route flow vector. In the dynamic queueing model the necessary conditions for convergence are shown not to hold.

AB - The traffic assignment problem aims to calculate an equilibrium route flow vector, generally by seeking a zero of an appropriate objective function. If a continuous dynamical system follows a descent direction for this objective function at each non-equilibrium route flow vector, the system converges to equilibrium. It is shown that when this dynamical system is discretised with a fixed step length the system eventually approaches close to equilibrium provided that the objective function is continuously differentiable and that the rate of descent is bounded below. Widely used in traffic assignment is the method of successive averages (MSA), which has a decreasing step size at each iteration. With the same conditions as above, it is shown that the resulting dynamical system converges to equilibrium. In the steady state model the necessary conditions are shown to be satisfied provided that the route cost vector is a continuously differentiable monotone function of the route flow vector. In the dynamic queueing model the necessary conditions for convergence are shown not to hold.

KW - method of successive averages

KW - equilibrium

KW - traffic assignment

KW - step length

UR - https://pure.ulster.ac.uk/en/publications/on-the-convergence-of-the-method-of-successive-averages-for-calcu-3

U2 - 10.1287/trsc.2014.0517

DO - 10.1287/trsc.2014.0517

M3 - Article

VL - 49

SP - 535

EP - 542

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 3

ER -