The travelling salesman problem on a dilute lattice: a simulated annealing study

Abstract

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 α_E and α_C as functions of lattice site occupation (city) concentration ρ, 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 α _C/α _E reduces from about 1.27 for p to 0 to 1 for p=1, indicating A_c approximately=(4. pi )A_E.