Characterisation of the probabilistic travelling salesman problem

Preprint, Article English OPEN
Bowler, Neill E. ; Fink, Thomas M. ; Ball, Robin C. (2000)
  • Publisher: American Physical Society
  • Related identifiers: doi: 10.1103/PhysRevE.68.036703
  • Subject: 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.
  • References (35)
    35 references, page 1 of 4

    [1] R. C. Ball, T. M. Fink, and N. E. Bowler, submitted to Physical Review Letters, available at (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).

  • Metrics
    No metrics available
Share - Bookmark