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

Abstract

If one places N cities randomly on a lattice of size L, we find that and vary with the city concentration p=N/L ², where is the average optimal travel distance per city in the Euclidean metric and is the same in the Manhattan metric. We have studied such optimum tours for visiting all the cities using a branch and bound algorithm, giving the exact optimized tours for small system sizes () and near-optimal tours for bigger system sizes (). Extrapolating the results for , we find that for p=1, and and with as . Although the problem is trivial for p=1, for it certainly reduces to the standard travelling salesman problem on continuum which is NP-hard. We did not observe any irregular behaviour at any intermediate point. The crossover from the triviality to the NP-hard problem presumably occurs at p=1.