GTSP Instances Library

The Generalized Traveling Salesman Problem (GTSP) is an extension of the Traveling Salesman Problem (TSP), where the node set is partitioned into clusters, and the objective is to find the shortest cycle that visits exactly (or, in some variations) at least) one node in each cluster. The problem is NP-hard. In 1997, Fischetti, Salazar Gonzalez and Toth [2] introduced a simple clustering procedure that can be used for creating GTSP instances out of TSP instances. The TSP instances were taken from a well known TSP instances library, TSPLIB, created by Gerhard Reinelt [3]. Since then, such a testbed became a de facto standard that was used in virtually all the GTSP literature. On this website, you will find these instances in several formats. You will also find the best known solutions for each of these instances.


References in zbMATH (referenced in 12 articles )

Showing results 1 to 12 of 12.
Sorted by year (citations)

  1. Khachai, M. Yu.; Neznakhina, E. D.: Approximation schemes for the generalized traveling salesman problem (2017)
  2. Smith, Stephen L.; Imeson, Frank: GLNS: an effective large neighborhood search heuristic for the generalized traveling salesman problem (2017)
  3. Sundar, Kaarthik; Rathinam, Sivakumar: Generalized multiple depot traveling salesmen problem -- polyhedral study and exact algorithm (2016)
  4. Helsgaun, Keld: Solving the equality generalized traveling salesman problem using the Lin-Kernighan-Helsgaun algorithm (2015)
  5. Tang, Xiaolin; Yang, Chunhua; Zhou, Xiaojun; Gui, Weihua: A discrete state transition algorithm for generalized traveling salesman problem (2015)
  6. Pintea, Camelia-Mihaela: Advances in bio-inspired computing for combinatorial optimization problems (2014)
  7. Isaacs, Jason T.; Hespanha, João P.: Dubins traveling salesman problem with neighborhoods: a graph-based approach (2013)
  8. Karapetyan, Daniel; Gutin, Gregory: Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem (2012)
  9. Karapetyan, D.; Gutin, G.: Lin-Kernighan heuristic adaptations for the generalized traveling salesman problem (2011)
  10. Gutin, Gregory; Karapetyan, Daniel: A memetic algorithm for the generalized traveling salesman problem (2010)
  11. Tasgetiren, M. Fatih; Suganthan, P. N.; Pan, Quan-Ke: An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem (2010)
  12. Gutin, Gregory; Karapetyan, Daniel: A memetic algorithm for the generalized traveling salesman problem (2008) ioport