Hybrid simulated annealing algorithm based on adaptive cooling schedule for TSP

ABSTRACT

The traveling salesman problem is one of the most notoriously intractable NP-complete optimization problems. Over the last 10 years, simulated annealing and tabu search have emerged as an effective algorithm for the TSP. However, the quality of solutions found by using tabu search approach depends on the initial solution and the iteration process of simulated annealing is slow. To overcome this problem and provide an efficient methodology for the TSP, the heuristic search approach based on simulated annealing which combining tabu search strategy and two neighborhood perturbation factor is developed. The proposed hybrid algorithm is tested on standard benchmark sets and compared with the conventional simulated annealing algorithm. The computational results show that the proposed algorithm has significantly better convergence speed compared with conventional simulated annealing algorithm and can obtain high-quality solutions within reasonable computing times.

REFERENCES

• 1: R. Durbin and D. Willshaw. An anlaogue approach to the traveling salesman problem using an elastic net approach. Nature, 326(6114):689--691, 1987.
• 2: Guo Tao , Zbigniew Michalewicz, Inver-over Operator for the TSP, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.803-812, September 27-30, 1998
• 3: Z.C.Huang, X.L.Hu, and S.D.Chen. Dynamic traveling salesman problem based on evolutionary computation. In Proceedings of Congress on Evolutionary Computation, pages 1283--1288. IEEE, May 2001.
• 4: Aimin Zhou, Lishan Kang, and Zhenyu Yan. Solving dynamic tsp with evolutionary approach in real time. In Proceedings of Congress on Evolutionary Computation, pages 951--957. IEEE, December 2003.
• 5: Fred Glover, Future paths for integer programming and links to artificial intelligence, Computers and Operations Research, v.13 n.5, p.533-549, May 1986 [doi>10.1016/0305-0548(86)90048-1]
• 6: C. D. Gelatt Jr S. Kirkpatrick and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598):671--680, 1983.
• 7: Nader Azizi , Saeed Zolfaghari, Adaptive temperature control for simulated annealing: a comparative study, Computers and Operations Research, v.31 n.14, p.2439-2451, December 2004 [doi>10.1016/S0305-0548(03)00197-7]
• 8: S. Lin and B.W. Kernighan. An effective heuristic algorithm for the traveling--salesman problem. Computers and Operations Research, 21(2):498--516, 1973.
• 9: P. Tian, H. Wang, and D. Zhang. Solving the travelling salesman problem by simulated annealing. Journal of Shanghai Jiaotong University, 29(12):111--116, 1995.
• 10: Fred Glover , Fred Laguna, Tabu Search, Kluwer Academic Publishers, Norwell, MA, 1997
• 11: John Knox, Tabu search performance on the symmetric traveling salesman problem, Computers and Operations Research, v.21 n.8, p.867-876, Oct. 1994 [doi>10.1016/0305-0548(94)90016-7]
• 12: T. H. Wu and C. C. Chang. A tabu search heuristic for the traveling salesman problem. Journal of Da-Yeh University, 19(1):87--99, 1997.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Simulated annealing

General Terms:
Algorithms

Keywords:
adaptive, simulated annealing algorithm, tabu search