Traveling Salesman Calculator
Find the shortest possible route that visits each city exactly once and returns to the origin city.
City Configuration
Add City
City List
| City | X | Y | Actions |
|---|
Algorithm Settings
Route Visualization
Solution Found
Total Distance:
Number of Cities:
Algorithm Used:
Optimal Route
Route Order:
Route Details:
| Step | From | To | Distance |
|---|
Performance Analysis
Computation Time:
Solution Quality:
Algorithm Insights:
About the Traveling Salesman Problem
What is the Traveling Salesman Problem?
The Traveling Salesman Problem (TSP) is a classic optimization problem: given a list of cities and the distances between them, what is the shortest possible route that visits each city exactly once and returns to the origin city? Despite its simple description, the TSP is notoriously difficult to solve optimally for large numbers of cities.
Algorithms Used
Nearest Neighbor
A greedy algorithm that always visits the nearest unvisited city next. Fast but may not find the optimal solution.
Brute Force
Checks all possible routes to find the optimal solution. Guaranteed to be optimal but extremely slow for more than 10 cities.
2-Opt Improvement
Improves an existing route by swapping pairs of edges to reduce the total distance. Good balance of speed and quality.
Real-World Applications
- Logistics and Delivery: Optimizing delivery routes for packages or services
- Circuit Board Manufacturing: Minimizing the movement of drilling equipment
- DNA Sequencing: Ordering DNA fragments efficiently
- Network Design: Optimizing the layout of telecommunications networks
- Vehicle Routing: Planning routes for multiple vehicles with various constraints
How to Use This Calculator
- Add cities by entering their names and coordinates, or use the "Add Random City" button
- Select an algorithm based on your problem size and accuracy needs
- Choose a starting city option
- Click "Solve Traveling Salesman Problem" to find the optimal route
- View the solution details and route visualization
- Export the solution for your records or further analysis
Computational Complexity
The TSP is an NP-hard problem, meaning that as the number of cities increases, the time required to solve it optimally grows exponentially. For n cities, there are (n-1)!/2 possible routes to check in the worst case:
| Cities | Possible Routes | Brute Force Time |
|---|---|---|
| 5 | 12 | < 1 second |
| 10 | 181,440 | ~ seconds |
| 15 | 43 billion | ~ years |