Traveling Salesman Problem (TSP)

The Traveling Salesman Problem (TSP) is one of the most well-known and well-studied problems in optimization and computer science. Its classical formulation and as many of its variations have been widely used to model problem in various fields, such as genetics, electronics, and logistics.  In this website, we intend to collect and publish educational and practical material about TSP and some of its useful variations. Along with some material about variations of TSP, the download section of the website contains various solvers and benchmark sets for TSP and its variations. Currently, these variations include the Hamiltonian cycle problem (HCP), a well-known NP-complete variation of TSP with theoretical importance in complexity theory, and Clustered Generalized Traveling Salesman Problem (CGTSP), an extended variation of TSP, CTSP, and GTSP. We have two long term objectives.  First, we intend to provide basic educational material for anyone interested in TSP and it...

Hamiltonian Cycle Problem The Hamiltonian cycle (HCP) problem is the problem of determining whether a Hamiltonian cycle ( a cycle in an undirected or directed graph that visits each vertex exactly once ) exists in a given graph (whether directed or undirected).  HCP is NP-complete and it is a special case of the traveling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance traveled is equal to the number of vertices. Learning Resources: An introduction on NP-complete Problems and the Hamiltonian Cycle Problem Algorithms: Snakes and Ladders algorithm v2.49 for the Hamiltonian Cycle Problem Download links for SLH2:  Windows - Linux Related article: Baniasadi, P., Ejov, V., Filar, J. A., Haythorpe, M., & Rossomakhine, S. (2014). Deterministic “Snakes and Ladders” Heuristic for the Hamiltonian cycle problem. Mathematical Programming Computation , 6(1)...

Clustered Generalized Traveling Salesman Problem Given a list of cities, suppose the cities are partitioned into mutually exclusive clusters, and each cluster is further partitioned into mutually exclusive sets of nodes called subclusters. Then the Clustered Generalized Traveling Salesman Problem (CGTSP) is the problem of finding the shortest cycle that satisfied the following: (1) the cycle visits exactly one node per subcluster, and, (2) within each cluster, all of the visited nodes are visited consecutively. For a detailed study of CGTSP see: Baniasadi, P., Foumani, M., Smith-Miles, K., & Ejov, V. (2020). A transformation technique for the clustered generalized traveling salesman problem with applications to logistics. European Journal of Operational Research. Benchmark set: STSP Solver Description Download Random CGTSP instances The instances of the benchmark set consist of randomly generated vertices in a  1000  ×  1000 ...

Traveling Salesman Problem Suppose a salesman plans to visit a set of cities. The classical formulation of the Traveling Salesman Problem (TSP) is as follows.  Given a set of cities and a set of distances between the cities, find the route of the minimal length that visits each city exactly once and returns to the initial city. The TSP is one of the most well-studied problems in combinatorial optimization thanks both to its theoretical importance and its applications in many important fields such as logistics, genome sequencing, and data clustering. Learning Resources: This youtube video contains a well-explained introductory material about the basic methods for solving the TSP Downloads Please see the downloads page to access TSP solvers. 

Contents:                1. Algorithms                               1.1 - TSP algorithms                               1.2 - Sparse TSP algorithms                2. Benchmark sets for TSP and its variations                               2.1 - TSP and HCP benchmark sets                               2.2 - CGTSP benchmark sets                               2.3 - TDTSP benchmark set 1. Algorithms                          1...