The stochastic traveling salesman problem: Finite size scaling and the cavity prediction

A. G. Percus 1, O. C. Martin 2

Journal of Statistical Physics 94 (1999) 739-758

We study the random link traveling salesman problem, where lengths l_ij between city i and city j are taken to be independent, identically distributed random variables. We discuss a theoretical approach, the cavity method, that has been proposed for finding the optimal tour length over this random ensemble, given the assumption of replica symmetry. Using finite size scaling and a renormalized model, we test the cavity predictions against the results of simulations, and find excellent agreement over a range of distributions. We thus provide numerical evidence that the replica symmetric solution to this problem is the correct one. Finally, we note a surprising result concerning the distribution of kth-nearest neighbor links in optimal tours, and invite a theoretical understanding of this phenomenon.

  • 1. CIC-3 and Center for Nonlinear Studies,
    Los Alamos National Laboratory
  • 2. Division de Physique Théorique, IPN,
    Université Paris XI - Paris Sud