Short answer: No, TSP is not “solved” in the mathematical sense, and that’s actually okay for most businesses.
Long answer: We can find optimal solutions for small instances (up to about 50 cities with current technology), but no polynomial-time algorithm exists for optimal solutions to large instances.
The problem remains NP-complete, meaning it’s mathematically proven to be among the most difficult computational problems.
What this means for businesses: You don’t need mathematically perfect solutions.
Modern approximation algorithms can find routes within 2-5% of optimal for large problems, which is more than good enough for practical applications and can be calculated in seconds rather than years.
The mathematical reality: TSP belongs to the NP-complete complexity class, meaning solution time grows exponentially with problem size.
For large instances (100+ cities), finding optimal solutions would require computational time exceeding the age of the universe – even with the world’s fastest computers.
The practical reality: “Unsolvable” doesn’t mean “unusable.” Businesses successfully use TSP approximation algorithms daily to optimize routes with hundreds or thousands of stops.
The key is accepting “excellent” solutions instead of demanding “perfect” ones.
Business perspective: A delivery route that’s 3% longer than mathematically perfect but calculated in 0.1 seconds is infinitely more valuable than a perfect route that takes 100 years to compute.
For optimal solutions: No, not for large instances. This is mathematically proven – unless someone solves the P vs NP problem and claims their million-dollar prize.
For practical solutions: Absolutely yes. Modern approximation algorithms like the Christofides algorithm can find solutions within 50% of optimal in polynomial time, which is more than sufficient for most practical applications.
**TSP (Traveling Salesman Problem):**
One vehicle (or salesman)
Visits all locations exactly once
Returns to the starting point
Minimizes total travel distance/time
**VRP (Vehicle Routing Problem):**
Multiple vehicles with capacity constraints
Potentially multiple depots or starting points
Varying customer demands and requirements
More complex optimization involving routing and resource allocation
Business reality: Most real-world delivery and service operations are actually VRP, not pure TSP.
VRP is computationally more complex but more representative of actual business challenges.
When each applies: Use TSP thinking for single-vehicle route planning; use VRP approaches for fleet management and multi-vehicle operations.
The honest answer: It depends on your specific needs, problem size, and time constraints.
For small problems (≤20 cities): Dynamic programming delivers optimal solutions quickly.
For medium problems (≤50 cities): Branch and bound can find optimal solutions with reasonable computation time.
For large problems (>50 cities): the Christofides algorithm provides excellent approximations with quality guarantees.
For very large problems (>200 cities): Advanced heuristics like genetic algorithms or simulated annealing, often combined with local search improvements.
Business recommendation: Most companies achieve excellent results with nearest neighbor initialization followed by 2-opt improvements – fast, reliable, and typically within 5% of optimal.