Abstract: The nearest neighbour relation between cities on random triangle lattice has been used to construct a tour subspace and to solve the traveling salesman problem. With importance sampling simulated annealing method and subtour optimization method, the efficiency has been raised obviously. Near optimal solutions are obtained in shorter computation time.

Key words: random triangle lattice, importance sampling, simulated annealing, traveling salesman problem