一种基于邻域搜索机制的旅行商问题求解

摘要：

旅行商问题是一个经典的数学组合优化问题，其广泛的工程应用背景促进了旅行商问题求解方法的快速发展。针对旅行商问题中最优路径的连接特点，提出了两种邻域搜索方法：邻域随机性搜索法和邻域概率性搜索法。这两种邻域搜索法对旅行商问题解的质量具有一定的提高能力，其中，为了加快搜索速度，在算法前期采用了循环倒置算子。实验结果表明算法在求解小规模旅行商问题时具有良好的寻优性能。最后将该算法与标准遗传算法结合，并进行了实验结果对比。实验数据显示结合后的算法搜索性能优于单一的两种优化算法，提高了算法搜索解的能力。

关键词：旅行商问题、邻域、随机搜索、概率搜索、循环倒置、最优路径

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金61403121

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

页数：共3页

页码：44-46