• Same authors
• Same keywords
• Recommend this article
• Download citation

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/π) ΩE (0,0) ≅ 0.65 and ΩC (0,1)(4/π) ΩE (0,1) ~ 0, 95 for Cartesian (C) metric.

Résumé
Nous étudions le problème du voyageur de commerce sur des réseaux dilués où les villes sont représentées par des sites d'un réseaux aléatoire occupés avec une concentration p, et le voyageur n'envisage de visiter qu'une fraction f du nombre total des villes. Nous étudions la variation de la distance optimale moyenne parcourue par ville L (p, f) en fonction de f pour plusieurs valeurs de p. Nous montrons que la distance normalisée par ville Ω (p, f) = √pL ( p, f) est bornée par ΩE (1,f) = ΩC( 1,f) = 1 pour tout f et ΩE (0, 0) ≅ 0, 54, Ω E (0,1) ≅ 0, 75 pour une métrique euclidienne (E) et Ω C (0,0) ≅ (4/π) ΩE (0, 0) = 0, 65 et Ω C (0, 1) (4/π) ΩE (0,1) ~ 0, 95 pour une métrique cartésienne (C) .