The Traveling Salesman Problem seeks the shortest tour visiting each city exactly once and returning to the starting city. Given n cities with distances dᵢⱼ, find permutation π minimizing Σᵢ₌₁ⁿ d(π(i),π(i+1)). TSP is NP-hard with n!/2n possible tours. Exact methods include: branch and bound, dynamic programming (Held-Karp O(n²2ⁿ)), and integer programming formulations (subtour elimination constraints). Heuristics include: nearest neighbor, 2-opt, 3-opt, Lin-Kernighan, Christofides algorithm (1.5-approximation for metric TSP). Variants include: asymmetric TSP, multiple TSP, and vehicle routing problem. TSP applications extend beyond routing to: circuit board drilling, genome sequencing, and scheduling.