The travelling salesman problem on a dilute lattice: a simulated annealing study
M Ghosh, S. S. Manna, Bikas K. Chakrabarti · Journal of Physics A Mathematical and General · 1988
The authors have studied the travelling salesman problem on a dilute square lattice of size 15 * 15, using the simulated annealing technique. They determined the average optimised travel distances per city alpha E and alpha C as functions of lattice site occupation (city) concentration p, using Euclidean and 'Cartesian' type metrics (denoted by E and C respectively) for the calculation of travel distances. alpha square root p is found to have a monotonic variation from a constant A to 1 as p varies from 0 to 1 with A E =0.80+or-0.05 and A c =1.00+or-0.05. The authors also show that the ratio alpha C / alpha E reduces from about 1.27 for p to 0 to 1 for p=1, indicating A c approximately=(4. pi )A E .