A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths

The considered stochastic travelling salesman problem is defined where the costs are distributed exponentially. The costs are symmetric and they satisfy the triangular inequality. A discrete time Markov chain is established in some periods of time. A stochastic tour is created in a dynamic recursive way and the best node is detected to traverse in each period. Then, a simulated annealing based heuristic method is applied to select the best state. All the nodes should be traversed exactly once. An initial \rho-approximate solution is applied for some benchmark problems and the obtained solutions are improved by a simulated annealing heuristic method.

Keywords:

Travelling salesman problem , discrete time Markov chain , approximation algorithms , Simulated Annealing