Simultaneous Perturbation Stochastic Approximation Algorithm for Solving Stochastic Problems of Transportation Network Analysis

Abstract

Stochastic optimization has become one of the important modeling approaches in transportation network analysis. For example, for traffic assignment problems based on stochastic simulation, it is necessary to use a mathematical algorithm that iteratively seeks out the optimal, the suboptimal solution, or both, because an analytical (closed-form) objective function is not available. Therefore, efficient stochastic approximation algorithms that can find optimal or suboptimal solutions to these problems are needed. The method of successive averages (MSA), a well-known algorithm, is used to solve both deterministic and stochastic equilibrium assignment problems. As found in previous studies, the MSA has questionable convergence characteristics, especially when the number of iterations is not sufficiently large. In fact, the stochastic approximation algorithm is of little practical use if the number of iterations to reduce the errors to within reasonable bounds is arbitrarily large. An efficient method to solve stochastic approximation problems is the simultaneous perturbation stochastic approximation (SPSA), which can be a viable alternative to the MSA because of its proven power to converge to sub-optimal solutions in the presence of stochasticities and its ease of implementation. The performance of MSA and SPSA algorithms is compared for solving traffic assignment problems with varying levels of stochastic-ities on a small network. The utmost importance is given to comparison of the convergence characteristics of the two algorithms as well as to the computational times. A worst-case scenario is also studied to check the efficiency and practicality of both algorithms in terms of computational times and accuracy of results.

Get full access to this article

View all access options for this article.

References

Spall

J. C.

An Overview of the Simultaneous Perturbation Method for Efficient Optimization. Johns Hopkins APL Technical Digest, Vol. 19, No. 4, 1998, pp. 482–492.

Maryak

J. L.

and Chin

D. C.

Global Random Optimization by Simultaneous Perturbation Stochastic Approximation. Johns Hopkins APL Technical Digest, Vol. 25, No. 2 2004, pp. 91–100.

Spall

J. C.

Stochastic Optimization, Stochastic Approximation and Simulated Annealing. In Wiley Encyclopedia of Electrical and Electronics Engineering, John Wiley & Sons, Inc., 1999, Vol. 20, pp. 529–542.

Gelfand

S. B.

and Mitter

S. K.

Recursive Stochastic Algorithms for Global Optimization in IR^d. Proc., 29th Conference on Decision and Control, IEEE, 1990, pp. 220–221.

Robbins

and Monro

A Stochastic Approximation Method. Annals of Mathematical Statistics, Vol. 22, No. 3 1951, pp. 400–407.

Kiefer

and Wolfowitz

Stochastic Estimation of the Maximum of a Regression Function. Annals of Mathematical Statistics, Vol. 23, No. 3 1952, pp. 462–466.

Wolfowitz

On the Stochastic Approximation Method of Robbins and Monro. Annals of Mathematical Statistics, Vol. 23, No. 3 1952, pp. 457–461.

Blum

J. R.

Multidimensional Stochastic Approximation Methods. Annals of Mathematical Statistics, Vol. 25, No. 4 1954, pp. 737–744.

Blum

J. R.

Approximation Methods Which Converge with Probability One. Annals of Mathematical Statistics, Vol. 25, No. 2 1954, pp. 382–386.

10.

Andradottir

A New Algorithm for Stochastic Optimization. Proc., 1990 Winter Simulation Conference, IEEE, 1990, pp. 151–158.

11.

Andradottir

A Review of Simulation Optimization Techniques. Proc., 1998 Winter Simulation Conference, IEEE, 1998.

12.

Sheffi

and Powell

W. B.

A Comparison of Stochastic and Deterministic Traffic Assignment over Congested Networks. Transportation Research, Vol. 15B, 1981, pp. 53–64.

13.

Sheffi

and Powell

W. B.

An Algorithm for the Equilibrium Assignment Problem with Random Link Times. Networks, Vol. 12, 1982, pp. 191–207.

14.

Powell

W. B.

and Sheffi

The Convergence of Equilibrium Algorithms with Predetermined Step Sizes. Transportation Science, Vol. 16, No. 1 1982, pp. 45–55.

15.

Sheffi

Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice Hall Inc., Upper Saddle River, N.J., 1985.

16.

TransCAD, Transportation Planning GIS Software. Caliper Corporation, Newton, Mass. http://www.caliper.com/.

17.

EMME 3, Travel Forecasting Software. INRO, http://www.inro.ca/.

18.

Transportation Planning Plus (TP+), Transportation Planning Software. http://www.citilabs.com/tpplus/.

19.

Cascetta

and Postorino

M. N.

Fixed Point Approaches to the Estimation of O/D Matrices Using Traffic Counts on Congested Networks. Transportation Science, Vol. 35, No. 2 2001, pp. 134–147.

20.

Bar-Gera

and Boyce

Solving a Non-Convex Combined Travel Forecasting Model by the Method of Successive Averages with Constant Step Sizes. Transportation Research, Vol. 40B, 2006, pp. 351–367.

21.

Boyce

and Florian

Workshop on Traffic Assignment with Equilibrium Models. Northwestern University and University of Montreal, 2005.

22.

Cominetti

and Baillon

J-B.

Stochastic Equilibrium in Traffic Networks. Presented at VIIth French–Latin American Congress on Applied Mathematics, 2005.

23.

Walker

W. T.

Rossi

T. F.

and Islam

Method of Successive Averages Versus Evans Algorithm: Iterating a Regional Travel Simulation Model to the User Equilibrium Solution. In Transportation Research Record 1645, TRB, National Research Council, Washington, D.C., 1998, pp. 32–40.

24.

Peeta

and Mahmassani

H. S.

System Optimal and User Equilibrium Time-Dependent Traffic Assignment in Congested Networks. Annals of Operations Research, Vol. 60, 1995, pp. 81–113.

25.

Mahmassani

H. S.

and Peeta

Network Performance Under System Optimal and User Equilibrium Dynamic Assignments: Implications for Advanced Traveler Information Systems. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 83–93.

26.

Sbayti

C. C.

and Mahmassani

H. S.

Efficient Implementation of Method of Successive Averages in Simulation-Based Dynamic Traffic Assignment Models for Large-Scale Network Applications. In Transportation Research Record: Journal of the Transportation Research Board, No. 2029, Transportation Research Board of the National Academies, Washington, D.C., 2007, pp. 22–30.

27.

Mahmassani

H. S.

Abdelghany

A. F.

Huynh

Zhou

Chiu

Y.-C.

and Abdelghany

K. F.

DYNASMART-P (version 0.926) User's Guide. Technical Report STO67-85-PIII. Center for Transportation Research, University of Texas, Austin, 2001.

28.

Ben-Akiva

Koutsopoulos

H. N.

, and Mishalani

DynaMIT: A Simulation-Based System for Traffic Prediction. Presented at DACCORD Short Term Forecasting Workshop, 1998.

29.

Mahut

Florian

and Tremblay

Comparison of Assignment Methods for Simulation-Based Dynamic Equilibrium Traffic Assignment. Presented at the 6th Triennial Symposium on Transportation Analysis, IEEE, 2007.

30.

Bottom

Ben-Akiva

Bierlaire

Chabini

Koutsopoulos

and Yang

Investigation of Route Guidance Generation Issues by Simulation with DYNAMIT. In Transportation and Traffic Theory: Proceedings of the 14th International Symposium on Transportation and Traffic Theory, Elsevier Science, 1999.

31.

Crittin

and Bierlaire

New Algorithmic Approaches for the Anticipatory Route Guidance Generation Issues. Presented at First Swiss Transport Research Conference, 2001.

32.

Dong

Mahmassani

H. S.

and Lu

C. C.

How Reliable Is the Route? Predictive Travel Time and Reliability for Anticipatory Traveler Information Systems. In Transportation Research Record: Journal of the Transportation Research Board, No. 1980, Transportation Research Board of the National Academies, Washington, D.C., 2006, pp. 117–125.

33.

Spall

J. C.

A Stochastic Approximation Technique for Generating Maximum Likelihood Parameters. Proc., American Control Conference, 1987, pp. 1161–1167.

34.

Spall

J. C.

Multivariate Stochastic Approximation Using a Simultaneous Perturbation Gradient Approximation. IEEE Transactions on Automatic Control, Vol. 37, No. 3 1992, pp. 332–341.

35.

Spall

J. C.

Implementation of the Simultaneous Perturbation Algorithm for Stochastic Optimization. IEEE Transactions on Aerospace and Electronic Systems, Vol. 34, No. 3 1998, pp. 817–823.

36.

Maryak

J. L.

and Chin

D. C.

Efficient Global Optimization Using SPSA. Proc., American Control Conference, 1999, pp. 890–894.

37.

Whitney

J. E.

Wairia

Hill

S. D.

and Bahari

Comparison of the SPSA and Simulated Annealing Algorithms for the Constrained Optimization of Discrete Non-separable Functions. Proc., American Control Conference, 2003, pp. 3260–3262.

38.

Hutchison

D. W.

and Spall

J. C.

Stopping Stochastic Approximation. Presented at PerMIS Workshop, Conference on Information Sciences and Systems, 2003.

39.

Kleinman

N. L.

Hill

S. D.

and Ilenda

V. A.

SPSA/SIMMOD Optimization of Air Traffic Delay Cost. Proc., American Control Conference, Vol. 2, 1997, pp. 1121–1125.

40.

Gerencser

Kozmann

Vago

and Haraszti

The Use of the SPSA Method in ECG Analysis. IEEE Transactions on Biomedical Engineering, Vol. 49, No. 10 2002, pp. 1094–1101.

41.

Xing

X. Q.

and Damodaran

Application of Simultaneous Perturbation Stochastic Approximation Method for Aerodynamic Shape Design Optimization. AIAA Journal, Vol. 43, No. 2 2005, pp. 284–294.

42.

Chin

D. C.

and Smith

R. H.

A Neural Network Application in Signal Timing Control. IEEE International Conference on Neural Networks, 1996, pp. 2010–2106.

43.

Srinivasan

Choy

M. C.

and Cheu

R. L.

Neural Networks for Real-Time Traffic Signal Control. IEEE Transactions on Intelligent Transportation Systems, Vol. 7, No. 3 2006, pp. 261–272.

44.

Choy

M. C.

Srinivasan

and Cheu

R. L.

Simultaneous Perturbation Stochastic Approximation Based Neural Networks for Online Learning. IEEE Intelligent Transportation Systems Conference, 2004, pp. 1038–1044.

45.

Kushner

H. J.

and Yin

G. G.

Stochastic Approximation Algorithms and Applications. Springer-Verlag, New York, 1997.

46.

EMME2 Resources Web Center. www.emme2.spiess.ch/e2news/news02/node3.html.

47.

Pflug

G. C.

On the Convergence of a Penalty-Type Stochastic Optimization Procedure. Journal of Information and Optimization Sciences, Vol. 2, 1981, pp. 249–258.

48.

Wang

and Spall

J. C.

A Constrained Simultaneous Perturbation Stochastic Approximation Algorithm Based on Penalty Functions. Proc., IEEE ISIC/CIRA/ISAS Joint Conference, 1998, pp. 452–458.

49.

Wang

and Spall

J. C.

Stochastic Optimization with Inequality Constraints Using Simultaneous Perturbations and Penalty Functions. Proc., 42nd IEEE Conference on Decision and Control, 2003, pp. 3808–3813.

50.

Fiacco

A. V.

and McCormick

G. P.

Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons Inc., New York, 1968.

51.

Spall

J. C.

Introduction to Stochastic Search and Optimization: Estimation, Simulation and Control. Wiley-Interscience Series in Discrete Mathematics and Optimization, 2005.