https://doi.org/10.1007/PL00011064
The travelling salesman problem on randomly diluted lattices: Results for small-size systems
Saha Institute of Nuclear Physics, 1/AF Bidhan Nagar, Calcutta 700 064, India
Received:
15
April
2000
Published online: 15 August 2000
If one places N cities randomly on a lattice of size L,
we find that 
and 
vary with
the city concentration 
, 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.
PACS: 05.50.+q – Lattice theory and statistics (Ising, Potts, etc.)
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2000
