Transfer optimization via simultaneous perturbation stochastic approximation

ABSTRACT

We consider the problem of optimizing a transit network with respect to customer service, when simulation of the network is necessary to accurately characterize performance. In particular, we consider the transfer optimization problem, where the goal is to minimize the total expected waiting time of riders by coordinating transfers in the network. We apply the technique of simultaneous perturbation stochastic approximation to optimize system performance. For a simple test case, we provide simulation results and discuss difficulties in applying the technique to this problem, specifically with regard to the smoothness of the objective function.

REFERENCES

• 1: Bookbinder, J.tt. and D~silets. A., Transfer optimization in a transit network. Transportation Science 26, No. 2, May 1992: 106-118.
• 2: Cassandras, C.G. 1993. Discrete Event Systems: Modeling and Performance Analysis. Irwin.
• 3: Fu, M.C.. 1994. Optimization via simulation: a review. Annals of Operations Research 53: 199-248.
• 4: Michael C. Fu , Yu-Chi Ho, Using perturbation analysis for gradient estimation, averaging and updating in a stochastic approximation algorithm, Proceedings of the 20th conference on Winter simulation, p.509-517, December 12-14, 1988, San Diego, California, United States [doi>10.1145/318123.318244]
• 5: Hill, S.D. and M. C. Fu. 1994. Optimizing discrete event systems with the simultaneous perturbation stochastic approximation algorithm, Proceedings of the 33rd IEEE Conference on Decision and Control: 2631-2632.
• 6: Stacy D. Hill , Michael C. Fu, Simulation optimization via simultaneous perturbation stochastic approximation, Proceedings of the 26th conference on Winter simulation, p.1461-1464, December 11-14, 1994, Orlando, Florida, United States
• 7: Spall, J.C. 1992. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation, IEEE Transactions on Automatic Control 37." 332-341.
• 8: Spall, J.C. and J.A. Cristion. 1994. Nonlinear Adaptive Control Using Neural Networks: Estimation with a Smoothed Simultaneous Perturbation Gradient Approximation, Stat~stzca Sinica ~:1-27.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
      G.1.6 Optimization
          Subjects: Gradient methods

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.3 Applications

General Terms:
Experimentation, Measurement, Performance