Solving the Clustered Traveling Salesman Problem via TSP methods
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Traveling Salesman ProblemSimilar Papers 제목 키워드 기반
Solving the clustered traveling salesman problem with d-relaxed priority rule
The Clustered Traveling Salesman Problem with a Prespecified Order on the Clusters, a variant of the well-known traveling salesman problem is studied in literature. In this problem, delivery locations are divided into cl…
Traveling Salesman ProblemSolving Traveling Salesman Problem by Marker Method
In this paper we use marker method and propose a new mutation operator that selects the nearest neighbor among all near neighbors solving Traveling Salesman Problem.
Traveling Salesman ProblemNew mechanism of combination crossover operators in genetic algorithm for solving the traveling salesman problem
Traveling salesman problem (TSP) is a well-known in computing field. There are many researches to improve the genetic algorithm for solving TSP. In this paper, we propose two new crossover operators and new mechanism of …
Traveling Salesman ProblemAMR-to-text generation as a Traveling Salesman Problem
The task of AMR-to-text generation is to generate grammatical text that sustains the semantic meaning for a given AMR graph. We at- tack the task by first partitioning the AMR graph into smaller fragments, and then gener…
AMR-to-Text GenerationText GenerationTranslationTraveling Salesman ProblemSteiner Traveling Salesman Problem with Quantum Annealing
The Steiner Traveling Salesman Problem (STSP) is a variant of the classical Traveling Salesman Problem. The STSP involves incorporating steiner nodes, which are extra nodes not originally part of the required visit set b…
Traveling Salesman Problem