The Markov chain heuristic is applied by the acceptance process of the simulated annealing algorithm for the traveling salesman problem. So, the state space of the established discrete time Markov chain contains some solutions in every iteration of the algorithm, those are obtained by exactly one traversed arc. Therefore, it is guaranteed no repeated state will be visited during the algorithm implementation. The proposed method is implemented on an initial approximated solution as well as an initial random solution. Thus, the proposed method could escape from an approximate solution as a good local optimal solution, and it obtains a nearby optimal solution whenever the initial random solution is far from the optimal solution.
