Engineering Academic Area, Autonomous University of Hidalgo, Pachuca, Hidalgo, Mexico.
PLoS One. 2018 Aug 22;13(8):e0201868. doi: 10.1371/journal.pone.0201868. eCollection 2018.
This article finds feasible solutions to the travelling salesman problem, obtaining the route with the shortest distance to visit n cities just once, returning to the starting city. The problem addressed is clustering the cities, then using the NEH heuristic, which provides an initial solution that is refined using a modification of the metaheuristic Multi-Restart Iterated Local Search MRSILS; finally, clusters are joined to end the route with the minimum distance to the travelling salesman problem. The contribution of this research is the use of the metaheuristic MRSILS, that in our knowledge had not been used to solve the travelling salesman problem using clusters. The main objective of this article is to demonstrate that the proposed algorithm is more efficient than Genetic Algorithms when clusters are used. To demonstrate the above, both algorithms are compared with some cases taken from the literature, also a comparison with the best-known results is done. In addition, statistical studies are made in the same conditions to demonstrate this fact. Our method obtains better results in all the 10 cases compared.
本文针对旅行商问题（TSP），找到可行的解决方案，以最短距离访问 n 个城市一次，并返回起始城市。所解决的问题是对城市进行聚类，然后使用 NEH 启发式算法提供一个初始解决方案，再使用元启发式多重启迭代局部搜索（MRSILS）的修改来进行细化；最后，通过连接聚类来结束路线，以达到 TSP 的最短距离。本研究的贡献在于使用了元启发式 MRSILS，据我们所知，该算法以前并未用于使用聚类来解决 TSP 问题。本文的主要目的是证明在使用聚类时，所提出的算法比遗传算法更有效。为了证明这一点，将两种算法与文献中的一些案例进行了比较，还与最知名的结果进行了比较。此外，还在相同条件下进行了统计研究，以证明这一事实。在比较的 10 个案例中，我们的方法在所有案例中都得到了更好的结果。
