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.
| Original language | English |
|---|---|
| Title of host publication | Wiley Encyclopedia of Operations Research and Management Science |
| Publisher | wiley |
| Pages | 1-9 |
| Number of pages | 9 |
| ISBN (Electronic) | 9780470400531 |
| ISBN (Print) | 9780470400630 |
| DOIs | |
| Publication status | Published - 1 Jan 2010 |
| Externally published | Yes |
Keywords
- Hamiltonian cycle
- branch and bound
- combinatorial algorithms
- graph-theoretic relaxations
- heuristic algorithms
- software
- traveling salesman problem