Keith Briggs

This page was last modified 2013-05-12  


·maths notes « 
·ex libris 
·site map 


The travelling salesman problem for randomly distributed nodes

Suppose n nodes are uniformly distributed (iid) on a unit 2-torus. I use a torus to avoid edge effects. What is the expected path length L(n) of the optimum travelling salesman problem (TSP) tour in Euclidean norm?

It is known that limn→∞ L(n)/sqrt(n) exists and is about 0.7120 (see [1]). Here is my data, which is an attempt to get a better value for this constant. The error bars are standard errors of the means. For each value of n, I solved 105 TSP instances exactly. All TSP data was computed using Concorde.


[1] Allon Percus: The stochastic traveling salesman problem

This website uses no cookies. This page was last modified 2013-05-12 10:17 by Keith Briggs.