Intelligent simulation for alternatives comparison and application to air traffic management

Abstract

We present a simulation run allocation scheme for improving efficiency in simulation experiments for decision making under uncertainty. This scheme is called Optimal Computing Budget Allocation (OCBA). OCBA advances the state-of-the-art by intelligently allocating a computing budget to the candidate alternatives under evaluation. The basic idea is to spend less computational effort on simulating non-critical alternatives to save computation cost. In particular, OCBA is employed to intelligently provide the smallest number of simulation runs for a desired accuracy. In this paper, we present a new and more general OCBA scheme which can consider cases that users are interested not only the best design, but also any one in a good design set. In addition, this paper also presents the application of our OCBA to a design problem in US air traffic management. The national air traffic system in US is modeled as a large, complex, and stochastic network. The numerical examples show that the computation time can be reduced by 54% to 88% with the use of OCBA.

Keywords

Stochastic simulation / stochastic optimization / air traffic management

References

[1] Bechhofer R. E., T. J. Santner, and D. M. Goldsman, Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons, John Wiley & Sons, Inc., 1995.

[2] Chen C. H.. A lower bound for the correct subset-selection probability and its application to discrete event system simulations. IEEE Transactions on Automatic Control, 1996, 41(8): 1227-1231.

[3] Chen C. H., Lin J., Yücesan E., Chick S. E.. Simulation budget allocation for further enhancing the efficiency of ordinal optimization. Journal of Discrete Event Dynamic Systems: Theory and Applications, 2000, 10: 251-270.

[4] Chen C. H., Wu S. D., Dai L.. Ordinal comparison of heuristic algorithms using stochastic optimization. IEEE Transactions on Robotics and Automation, 1999, 15(1): 44-56.

[5] Chen, C. H., E. Yücesan, Y. Yuan, H. C. Chen and L. Dai, “Computing budget allocation for simulation experiments with different system structures”, Proceedings of the 1998 Winter Simulation Conference, pp735–741, December 1998.

[6] Cheng R. C. H.. The use of antithetic variates in computer simulations. Journal of Operational Research Society, 1984, 15: 227-236.

[7] Chick S., Inoue K.. New two-stage and sequential procedures for selecting the best simulated system. Operations Research, 2001, 49: 1609-1624.

[8] DeGroot M. H.. Optimal Statistical Decisions, 1970, New York, NY: McGraw-Hill Book Co..

[9] Fishman, G. Monte Carlo: Concepts, Algorithms, and Applications, Springer-Verlag, 1996.

[10] Glasserman P., Yao D. D.. Some guidelines and guarantees for common random numbers. Management Science, 1992, 38(6): 884-908.

[11] Heidelberger, P. “Fast simulation of rare events in queueing and reliability models”, In Performance Evaluation of Computer and Communication Systems, ed. L. Donatiello and R. Nelson, pp165–202, Springer Verlag, 1993.

[12] Hyden, P. and L. Schruben, “Improved decision processes through simulatneous simulation and time dilation”, Proceedings of the 2000 Winter Simulation Conference, pp743–748, 2000.

[13] Le, L., G. L. Donohue, and C. H. Chen, “Using auction-based slot allocation for traffic demand management at hartsfield atlanta international airport: a case study”, to appear in Journal of the Transportation Research Board, 2004.

[14] Lee, L. H., and E. P. Chew “A simulation study on sampling and selecting under fixed computing budget”, Proceedings of 2003 Winter Simulation Conference, pp. 535–542, December 2003.

[15] Rinott Y.. On two-stage selection procedures and related probability inequalities. Communications in Statistics, 1978, A7: 799-811.

[16] Trailovic L., Pao L. Y.. Computing budget allocation for efficient ranking and selection of variances with application to target tracking algorithms. IEEE Transactions on Automatic Control, 2004, 49(1): 58-67.