Combinatorial Traveling Salesman Problem Algorithms
Claudia D’Ambrosio, Andrea Lodi, Silvano Martello · Wiley Encyclopedia of Operations Research and Management Science · 2011
Abstract The traveling salesman problem (TSP) is a fundamental and well‐known problem in combinatorial optimization. We start by reviewing some of its ancestors, including the famous Hamiltonian cycle problem of which the TSP is the weighted version. We then introduce the most famous formulations of both the symmetric and the asymmetric TSP, and describe combinatorial approaches for both versions of the problem. We conclude with a brief discussion on the available TSP software.