TSP Solver & Visualizer 2.0

×

TSP Solver & Visualizer - Help

What is the Traveling Salesman Problem (TSP)?

The Traveling Salesman Problem is a classic optimization challenge: Given a list of cities and the distances between them, find the shortest possible route that visits each city exactly once and returns to the starting city.

Despite its simple description, TSP is NP-hard, meaning there's no known algorithm that can solve all instances efficiently as the number of cities grows. This makes it a perfect testbed for comparing optimization algorithms.

How to Use This Application

1. Create a Problem: Click on the canvas to add cities manually, or use predefined problems (geometric patterns or classical instances from TSPLIB), or generate random cities.
2. Choose an Algorithm: Select from Nearest Neighbor (fast greedy), Self-Organizing Map (neural network), 2-Opt (local improvement), or Simulated Annealing (probabilistic).
3. Adjust Parameters: Tune algorithm-specific parameters to see how they affect performance.
4. Run and Watch: Click "Solve" and watch the algorithm work. Use the Animation Delay slider to slow down and see details.
5. Compare: Enable Comparison Mode to run all algorithms on the same problem and see which performs best.

Algorithms Explained

• Nearest Neighbor: Greedy construction - always moves to the nearest unvisited city. Fast but often produces suboptimal tours.
• Self-Organizing Map (SOM): Neural network with a ring of neurons that adapts to city positions. Unique visualization shows neurons (red dots) forming a ring that deforms to fit the cities.
• 2-Opt: Local search that iteratively improves a tour by swapping pairs of edges. Starts with Nearest Neighbor solution and refines it.
• Simulated Annealing: Probabilistic method that accepts worse solutions early (high temperature) to escape local optima, gradually "cooling" to find better solutions.

Classical Problem Instances

The application includes famous TSP instances from TSPLIB, a widely-used benchmark library:

• Burma14: 14 cities in Burma (Myanmar)
• Ulysses16/22: Geographic locations from Homer's Odyssey
• Eil51: 51-city instance by Eilon
• Berlin52: 52 locations in Berlin, Germany
• St70: 70-city instance by Steinberg

Tips

• Start with small problems (10-20 cities) to see algorithm behavior clearly
• Use lower Animation Delay values to speed up visualization
• Try the same problem with different algorithms to see how they compare
• Geometric patterns like Circle are "easy" - try Clustered or Classical instances for more challenging problems