×

zbMATH — the first resource for mathematics

Method of successive weighted averages (MSWA) and self-regulated averaging schemes for solving stochastic user equilibrium problem. (English) Zbl 1178.90066
Summary: Although stochastic user equilibrium (SUE) problem has been studied extensively in the past decades, the solution convergence of SUE is generally quite slow because of the use of the method of successive averages (MSA), in which the auxiliary flow pattern generated at each iteration contributes equally to the final solution. Realizing that the auxiliary flow pattern is in fact approaching to the solution point when the iteration number is large, in this paper, we introduce the method of successive weighted averages (MSWA) that includes a new step size sequence giving higher weights to the auxiliary flow patterns from the later iterations. We further develop a self-regulated averaging method, in which the step sizes are varying, rather than fixed, depending on the distance between intermediate solution and auxiliary point. The proposed step size sequences in both MSWA and self-regulated averaging method satisfy the Blum theorem, which guarantees the convergence of SUE problem. Computational results demonstrate that convergence speeds of MSWA and self-regulated averaging method are much faster than those of MSA and the speedup factors are in a manner of magnitude for high accuracy solutions. Besides SUE problem, the proposed methods can also be applied to other fixed-point problems where MSA is applicable, which have wide-range applications in the area of transportation networks.

MSC:
90B15 Stochastic network models in operations research
90C15 Stochastic programming
Software:
DynaMIT
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Akamatsu T (1996) Cyclic flows, Markov process and stochastic traffic assignment. Transp Res Part B 30(5):369–386 · doi:10.1016/0191-2615(96)00003-3
[2] Bar-Gera H, Boyce D (2006) Solving a non-convex combined travel forecasting model by the method of successive averages with constant step sizes. Transp Res Part B 40(5):351–367 · doi:10.1016/j.trb.2005.05.002
[3] Bell MGH (1995) Alternative to Dial’s logit assignment algorithm. Transp Res Part B 29(4):287–295 · doi:10.1016/0191-2615(95)00005-X
[4] Blum JR (1954) Multidimensional stochastic approximation methods. Ann Math Stat 25(4):737–744 · Zbl 0056.38305 · doi:10.1214/aoms/1177728659
[5] Bottom J, Ben-Akiva M, Bierlaire M, Chabini I, Koutsopoulos H, Yang Q (1999) Investigation of route guidance generation issues by simulation with DynaMIT. In: Ceder A (ed) Transportation and traffic theory. Proceedings of the 14th International Symposium on Transportation and Traffic Theory, Pergamon, Amsterdam, pp 577–600
[6] Bottom J, Chabini I (2001) Accelerated averaging methods for fixed point problems in transportation analysis and planning. Triennial Symposium on Transportation Analysis (TRISTAN IV). São, Miguel, Azores, Preprints 1, 69–74
[7] Cascetta E, Postorino MN (2001) Fixed point approaches to the estimation of O/D matrices using traffic counts on congested networks. Transp Sci 35(2):134–147 · Zbl 1069.90505 · doi:10.1287/trsc.35.2.134.10138
[8] Chen M, Alfa AS (1991) Algorithms for solving Fisk’s stochastic traffic assignment model. Transp Res Part B 25(6):405–412 · doi:10.1016/0191-2615(91)90033-F
[9] Daganzo CF, Sheffi Y (1977) On stochastic models of traffic assignment. Transp Sci 11(3):253–274 · doi:10.1287/trsc.11.3.253
[10] Fisk C (1980) Some developments in equilibrium traffic assignment. Transp Res Part B 14(3):243–255 · doi:10.1016/0191-2615(80)90004-1
[11] Frees E, Ruppert D (1990) Estimation following a sequentially designed experiment. J Am Stat Assoc 85:1123–1129 · Zbl 0741.62075 · doi:10.2307/2289610
[12] Magnanti TL, Perakis G (1997) Averaging schemes for variational inequalities and system of equations. Math Oper Res 22(3):568–587 · Zbl 0879.49025 · doi:10.1287/moor.22.3.568
[13] Maher MJ (1998) Algorithms for logit-based stochastic user equilibrium assignment. Transp Res Part B 32(8):539–549 · doi:10.1016/S0191-2615(98)00015-0
[14] Maher MJ, Hughes PC (1998) Recent developments in stochastic assignment modeling. Traffic Eng Control 39(3):174–179
[15] Nagurney A, Zhang D (1996) Projected dynamical systems and variational inequalities with applications. Kluwer, Boston, Massachusetts · Zbl 0865.90018
[16] Nocedal J, Wright SJ (1999) Numerical optimization. Springer, New York · Zbl 0930.65067
[17] Polyak BT (1990) New method of stochastic approximation type. Autom Remote Control 51(7):937–946 · Zbl 0737.93080
[18] Robbins H, Monro S (1951) A stochastic approximation method. Ann Math Stat 22(3):400–407 · Zbl 0054.05901 · doi:10.1214/aoms/1177729586
[19] Sheffi Y (1985) Urban transportation networks: equilibrium analysis with mathematical programming methods. Prentice-Hall, New York
[20] Sheffi Y, Powell WB (1982) An algorithm for the equilibrium assignment problem with random link times. Networks 12(2):191–207 · Zbl 0485.90082 · doi:10.1002/net.3230120209
[21] Wong SC (1999) On the convergence of Bell’s logit assignment formulation. Transp Res Part B 33(8):609–616 · doi:10.1016/S0191-2615(99)00015-6
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.