Travelling salesman problem on dilute lattices: visit to a fraction of cities

Abstract

We study the travelling salesman problem on dilute lattices where the cities are represented by random lattice sites, occupied with concentration p, and the salesman intends to visit a finite fraction f of the total number of cities. The variation of the average optimal travel distance per city L (p, f) against f are investigated here for various values of p. The values of the normalised travel distance per city Ω (p, f )=√pL (p,f) are shown to be bounded within ΩE (1,f)=Ωc(1, f)=1 for all f and ΩE (0,0) ∓ 0.54, Ω E (0, 1) ∓ 0.75 for Euclidean (E) metric and CC (0, 0)=(4/p) OE (0,0) ∓ 0.65 and ΩC (0,1)(4/p) ΩE (0,1) ~ 0, 95 for Cartesian (C) metric.