An Improved Simulated Annealing Algorithm for Travelling Salesman Problem

Authors

  • Y. Wang North China Electric Power University, Beijing, China
  • D. Tian North China Electric Power University, Beijing, China
  • Y.H. Li North China Electric Power University, Beijing, China

DOI:

https://doi.org/10.3991/ijoe.v9i4.2822

Abstract


Traveling salesman problem (TSP) is one well-known NP-Complete problem. The basic simulated annealing algorithm is improved with the four vertices and three lines inequality to search the optimal Hamiltonian circuit (OHC) or approximate OHC. The four vertices and three lines inequality is taken as the heuristic information to convert the local Hamiltonian paths in the Hamiltonian circuit (HC) into the local optimal Hamiltonian paths and the HC become shorter. The HCs are generated with the basic simulated algorithm first. Then the local Hamiltonian paths are changed into the local optimal Hamiltonian paths with the four vertices and three lines inequality. The algorithm of the improved simulated annealing is designed and tested with twenty TSP instances. The experimental results show that the better approximate OHCs are found than those searched with the basic simulated annealing algorithm under the same preconditions.

Downloads

Published

2013-07-23

How to Cite

Wang, Y., Tian, D., & Li, Y. (2013). An Improved Simulated Annealing Algorithm for Travelling Salesman Problem. International Journal of Online and Biomedical Engineering (iJOE), 9(4), pp. 28–32. https://doi.org/10.3991/ijoe.v9i4.2822

Issue

Section

Special Focus Papers