Combinatorial Traveling Salesman Problem Algorithms

Given a set of cities, and the cost of traveling between each pair of them, the Traveling Salesman Problem, TSP for short, calls for finding a unique tour visiting all cities at minimum cost. Besides being for sure the best known combinatorial optimization problem, the TSP has many applications, not only in Operations Research/Management Science (especially in transportation and logistics), but also in many other fields, such as genome sequencing or drilling of printed circuits boards. We review some of the TSP ancestors, including the famous Hamiltonian cycle problem, of which the TSP is the weighted version. We examine the most famous formulations for both symmetric and asymmetric TSP, and the main combinatorial approaches for its solution.