Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (31): 43-45.DOI: 10.3778/j.issn.1002-8331.2009.31.014

• 研究、探讨 • Previous Articles     Next Articles

Hybrid tabu-simulated approach to solve traveling salesman problem

LIU Yi,XIONG Sheng-wu   

  1. College of Computer Science,Wuhan University of Technology,Wuhan 430070,China
  • Received:2008-11-21 Revised:2009-02-27 Online:2009-11-01 Published:2009-11-01
  • Contact: LIU Yi

TSP问题的禁忌模拟退火求解

刘 毅,熊盛武   

  1. 武汉理工大学 计算机科学与技术学院,武汉 430070
  • 通讯作者: 刘 毅

Abstract: Based on the existing smiulated annealing algorithm,the paper proposes a hybrid tabu-smiulated approach which introducing a new cooling schedule to solve Traveling Salesman Problem.With this new temperature control scheme,a higher chance of an uphill move is given at the end of search.Combined with the excellent local search ability of tabu search and the fine solution quality of simulated annealing,the proposed approach is less dependent on the specific information of problem compared with conventional simulated annealing.The performance of proposed approach is evaluated and favorably compared with the conventional simulated annealing.Numerical results of Benchmark TSPLib illustrate that this algorithm has better convergence speed and easy to find out the best answer.

Key words: smiulated annealing algorithm, tabu search, Traveling Salesman Problem(TSP)

摘要: 提出了一种加入了禁忌表、并且采用了新的温度控制机制的用于求解TSP问题的模拟退火算法。新算法增加了搜索结束阶段进行“爬坡”移动的概率,吸收了禁忌搜索具有较强局部搜索能力的优点和模拟退火算法产生优质解的能力,并且对问题的依赖性低于传统的模拟退火算法。对标准的TSPLib中不同国家的城市数据进行测试的实验结果表明,新的算法比传统的模拟退火算法在求解TSP问题上有更快的收敛速度,在解的质量上也有一定程度的提高。

关键词: 模拟退火, 禁忌搜索, 旅行商问题

CLC Number: