论文标题
通过TSP方法解决聚类的旅行推销员问题
Solving the Clustered Traveling Salesman Problem via TSP methods
论文作者
论文摘要
聚集的旅行推销员问题（CTSP）是由许多现实生活应用引起的流行旅行推销员问题（TSP）的变体。在这项工作中，我们探索了一种转换方法，该方法通过将其转换为良好的TSP来解决CTSP。为此，我们首先研究了一种将CTSP实例转换为TSP的技术，然后应用强大的TSP求解器（包括精确和启发式求解器）来求解所得的TSP实例。我们想回答以下问题：最新的TSP求解器如何在从CTSP转换的群集实例上执行？最先进的TSP求解器与专门为CTSP设计的最佳性能方法竞争吗？为此，我们对各种基准实例进行了密集的计算实验，以得出结论。
The Clustered Traveling Salesman Problem (CTSP) is a variant of the popular Traveling Salesman Problem (TSP) arising from a number of real-life applications. In this work, we explore a transformation approach that solves the CTSP by converting it to the well-studied TSP. For this purpose, we first investigate a technique to convert a CTSP instance to a TSP and then apply powerful TSP solvers (including exact and heuristic solvers) to solve the resulting TSP instance. We want to answer the following questions: How do state-of-the-art TSP solvers perform on clustered instances converted from the CTSP? Do state-of-the-art TSP solvers compete well with the best performing methods specifically designed for the CTSP? For this purpose, we present intensive computational experiments on various benchmark instances to draw conclusions.
