利用改进的随机松弛法求解旅行商问题

摘要：

旅行商问题是一个典型的组合优化问题,也是多种复杂问题的一种简化形式.因此,寻求一种有效的算法来求解此问题成为研究热点.随机松弛法是一种基于Metropolis迭代法求解的启发式随机搜索算法.针对该算法在求解旅行商问题时,存在易陷入局部最优的缺点,本文提出了三种不同的改进方法.即就是说,在解变换产生新解的过程中,首先,随机选择三个城市.然后,分别给出了三种不同的随机处理方法.最后,在仿真研究中,与已有方法相比,结果表明所给的三种方法的路径更短,结果更优.

关键词：旅行商问题、组合优化、Metropolis准则、随机松弛法启发式算法

所属期刊栏目：25

分类号：TP3;TN9

资助基金：国家自然科学基金61273127;陕西省自然科学基础研究计划2014JM8325;陕西省教育厅科研计划14JK1538

在线出版日期：2016-08-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：167-172