A simulated annealing heuristic for the online symmetric traveling salesman problem

An online tour is created in online manner, and some nodes are decided to traverse those will be fixed and unchangeable for the next times. The exact values of costs are not available for decision maker; however, they are symmetric and satisfying the triangular inequality. A discrete time Markov chain is established in online policy times by permutation of some unfixed nodes. Then, a simulated annealing heuristic is applied to select the best state. The competitive analysis of the proposed method shows the remarkable competitive ratio 1.4203 rho - 0.4203 against the previous ones, where the initial obtained solution is rho-approximated. The experimental results reveal improvement capability of the algorithm for limited iterations.