Remember Me
Or use your Academic/Social account:


Or use your Academic/Social account:


You have just completed your registration at OpenAire.

Before you can login to the site, you will need to activate your account. An e-mail will be sent to you with the proper instructions.


Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version of the site upon release.

Thank you for your patience,
OpenAire Dev Team.

Close This Message


Verify Password:
Verify E-mail:
*All Fields Are Required.
Please Verify You Are Human:
fbtwitterlinkedinvimeoflicker grey 14rssslideshare1
Bowler, Neill E.; Fink, Thomas M. A.; Ball, Robin (2003)
Publisher: American Physical Society
Languages: English
Types: Preprint
Subjects: QA, Physics - General Physics, Physics - Computational Physics
We show that stochastic annealing can be successfully applied to gain new results on the probabilistic traveling salesman problem. The probabilistic "traveling salesman" must decide on an a priori order in which to visit n cities (randomly distributed over a unit square) before learning that some cities can be omitted. We find the optimized average length of the pruned tour follows E((L) over bar (pruned))=rootnp(0.872-0.105p)f(np), where p is the probability of a city needing to be visited, and f(np)-->1 as np-->infinity. The average length of the a priori tour (before omitting any cities) is found to follow E(L-a priori)=rootn/pbeta(p), where beta(p)=1/[1.25-0.82 ln(p)] is measured for 0.05less than or equal topless than or equal to0.6. Scaling arguments and indirect measurements suggest that beta(p) tends towards a constant for p<0.03. Our stochastic annealing algorithm is based on limited sampling of the pruned tour lengths, exploiting the sampling error to provide the analog of thermal fluctuations in simulated (thermal) annealing. The method has general application to the optimization of functions whose cost to evaluate rises with the precision required.
  • The results below are discovered through our pilot algorithms. Let us know how we are doing!

    • [1] R. C. Ball, T. M. Fink, and N. E. Bowler, submitted to Physical Review Letters, available at http://arXiv.org/abs/cond-mat/0301179 (unpublished).
    • [2] T. W. Jonsbraten, Journal of the operational research society 49, 811 (1998).
    • [3] H. Robbins and S. Munro, The annals of mathematical statistics 22, 400 (1951).
    • [4] A. Benveniste, M. M´etivier, and P. Priouret, Adaptive algorithms and stochastic approximation (Springer-Verlag, New York, 1990).
    • [5] H. J. Kushner and F. J. V´asquez, SIAM Journal on Control and Optimization 34, 712 (1996).
    • [6] P. L'Ecuyer and G. Yin, SIAM Journal on Optimization 8 No. 1, 217 (1998).
    • [7] H. J. Kushner, SIAM Journal on Applied Mathematics 47, 169 (1987).
    • [8] W. B. Gong, Y. C. Ho, and W. Zhai, in Proceedings of the 31st IEEE conference on decision and control (IEEE, PO Box 1331, Piscataway, NJ, 1992), pp. 795-802.
    • [9] D. Yan and H. Mukai, SIAM journal on control and optimization 30 No. 3, 594 (1992).
    • [10] L. P. Devroye, IEEE Transactions on Information Theory 24, 142 (1978).
    • [11] S. Yakowitz and E. Lugosi, SIAM Journal on Scientific and Statistical Computing 11, 702 (1990).
    • [12] S. Andrad´ottir, SIAM Journal on Optimization 6 No. 2, 513 (1996).
    • [13] J. Haddock and J. Mittenthal, Computers and Industrial Engineering 22 No. 4, 387 (1992).
    • [14] A. A. Bulgak and J. L. Sanders, in Proceedings of the 1988 Winter Simulation Conference (IEEE, PO Box 1331, Piscataway, NJ, 1988), pp. 684-690.
    • [15] M. H. Alrefaei and S. Andrad´ottir, Management Science 45 No. 5, 748 (1999).
    • [16] T. M. A. Khamis, M. A. Ahmed, and V. K. Tuan, European Journal of Operational Research 116 No. 3, 530 (1999).
    • [17] W. J. Gutjahr and G. C. Pflug, Journal of global optimization 8, 1 (1996).
    • [18] S. B. Gelfand and S. K. Mitter, J. Optimization Theory and Applications 62, 49 (1989).
    • [19] S. Rees and R. C. Ball, J. Phys. A 20, 1239 (1987).
    • [20] J. D. Nulton and P. Salamon, Phys. Rev. A 37 No. 4, 1351 (1988).
    • [21] P. Salamon, J. D. Nulton, J. R. Harland, J. Pedersen, G. Ruppiener, and L. Liao, Computer Physics Communications 49, 423 (1988).
    • [22] D. J. Bertsimas, P. Jaillet, and A. R. Odoni, Operations Research 38 No. 6, 1019 (1990).
    • [23] J. Beardwood, J. H. Halton, and J. M. Hammersley, Proceedings of the Cambridge Philosophical Society 55, 299 (1959).
    • [24] J. M. Steele, Annals of Probability 9, 365 (1981).
    • [25] J. Lee and M. Y. Choi, Phys. Rev. E 50, R651 (1994).
    • [26] P. Jaillet, Ph.D. thesis, M.I.T., 1985.
    • [27] P. Jaillet, Operations research 36, 929 (1988).
    • [28] D. J. Bertsimas and L. H. Howell, Eur. J. of Operational Research 65, 68 (1993).
    • [29] G. Laporte, F. V. Louveaux, and H. Mercure, Operations research 42 No. 3, 543 (1994).
    • [30] D. J. Bertsimas, Ph.D. thesis, M.I.T., 1988.
    • [31] F. A. Rossi and I. Gavioli, in Advanced school on stochastics in combinatorial optimization, edited by G. Andreatta, F. Mason, and P. Serafini (World Scientific, Singapore, 1987), pp. 214-227.
    • [32] D. J. Bertsimas, P. Chervi, and M. Peterson, Transportation science 29 No. 4, 342 (1995).
    • [33] J. J. Bartholdi and L. K. Blatzman, Operations Research Lett. 1, 121 (1982).
    • [34] S. Lin, Bell Systems Technological Journal 44, 2245 (1965).
    • 100 np 150 200
  • No related research data.
  • No similar publications.

Share - Bookmark

Cite this article