The travelling salesman problem on randomly diluted lattices: Results for small-size systems

If one places N cities randomly on a lattice of size L; we find that (l) ov er bar(E)root p and (l) over bar(M)root p vary with the city concentration p = N/L-2, where (l) over bar(E) is the average optimal travel distance per city in the Euclidean metric and (l) over bar(M) is the same in the Manhat tan metric. We have studied such optimum tours for visiting all the cities using a branch and bound algorithm, giving the exact optimized tours for sm all system sizes (N less than or equal to 100) and near-optimal tours for b igger system sizes (100 < N less than or equal to 256). Extrapolating the r esults for N --> infinity, we find that (l) over bar(E)root p = (l) over ba r(M)root p = 1 for p = 1, and (l) over bar(E)root p = 0.73 +/- 0.01 and (l) over bar(M)root p = 0.93 +/- 0.02 with (l) over bar(M)/(l) over bar(E) sim ilar or equal to 4/pi p as p --> 0. Although the problem is trivial for p = 1, for p --> 0 it certainly reduces to the standard travelling salesman pr oblem on continuum which is NP-hard. We did not observe any irregular behav iour at any intermediate point. The crossover from the triviality to the NP -hard problem presumably occurs at p = 1.