阮姗娜，陈俊风，顾 菁，王思睿

（河海大学物联网工程学院，常州213022）

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

阮姗娜，陈俊风，顾 菁，王思睿

（河海大学物联网工程学院，常州213022）

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

旅行商问题；邻域；随机搜索；概率搜索；循环倒置；最优路径

1 引 言

旅行商问题（Traveling Salesman Problem，TSP）是组合优化［1］中一个易于描述但至今尚未彻底解决的古老而又困难的问题，是著名的NP－hard［2］问题。旅行商问题在工程上具有广泛的实际应用背景，最早应用于校车路线的优化。目前旅行商问题已广泛应用于电路板设计、城市规划、交通运输、物流配送等领域。因此，对旅行商问题进行研究具有重要意义，一直以来受到学者们的大量关注，是组合优化领域中的研究热点。

针对目前不同的实际应用背景衍生出了多种不同类型的旅行商问题，如非对称旅行商问题、多旅行商问题、多目标旅行商问题、黑白旅行商问题等，它们都可以转换成旅行商问题进行求解。……