This post is best viewed using the light theme.
What is the Traveling Salesman Problem?
Ever wondered why the delivery driver drives past your house? Or why your GPS sometimes takes you on what seems like a weird route? That’s exactly what the Traveling Salesman Problem (TSP) tries to solve!
In simple terms: “Given a list of cities and the distances between them, what’s the shortest possible route that visits each city exactly once and returns to the starting point?”
It sounds easy, but it’s actually one of the most famous problems in computer science. With just 13 cities, there are over 6 billion possible routes to check!
Why Use Genetic Algorithms?
Genetic algorithms are perfect for TSP because:
- They don’t need to check every possible route (which would take forever)
- They can find good solutions quickly (even if not perfect)
- They’re flexible - you can easily change parameters to experiment
This post shows how genetic algorithms can solve TSP using real US city coordinates. We’ll compare our results with Google’s OR-Tools to see how well we do!
The Cities We’re Working With
Here are the 13 US cities we’ll be optimizing routes for:
| City | Coordinates | Code | Description |
|---|---|---|---|
| New York | 40, -74 | A | Starting point |
| Los Angeles | 34, -118 | B | West Coast hub |
| Chicago | 41, -87 | C | Midwest center |
| Minneapolis | 44, -93 | D | Northern city |
| Denver | 39, -104 | E | Mountain region |
| Dallas | 32, -96 | F | Southern hub |
| Seattle | 47, -122 | G | Pacific Northwest |
| Boston | 42, -71 | H | Northeast |
| San Francisco | 37, -122 | I | Bay Area |
| St. Louis | 38, -90 | J | Gateway to West |
| Houston | 29, -95 | K | Texas coast |
| Phoenix | 33, -111 | L | Desert Southwest |
| Salt Lake City | 40, -111 | M | Mountain West |
Total: 13 cities - enough to make it interesting but not overwhelming!
How the Algorithm Works
The Route Representation
Instead of storing full city names, we use letters A-M. So a route like “A→H→C→D→E→M→G→I→B→L→K→F→J→A” means: New York → Boston → Chicago → Minneapolis → Denver → Salt Lake City → Seattle → San Francisco → Los Angeles → Phoenix → Houston → Dallas → St. Louis → New York
Distance Calculation
We use Euclidean distance (straight-line distance) between coordinates, not road distance. This makes calculations faster and gives us a good approximation.
The Genetic Algorithm Process
- Start with random routes (population of 20 routes)
- Calculate fitness (shorter routes = better fitness)
- Select parents using different methods
- Create children by combining parts of parent routes
- Mutate some routes randomly
- Repeat for 500 generations
Interactive TSP Solver
Try the interactive demo below! You can experiment with different genetic algorithm settings:
Choose Your Settings
Cross Over Method:
Selection Method:
Click “Run” to see how different settings affect the solution!
Quick Tips:
- Random selection usually gives poor results - it defeats the purpose of genetic algorithms!
- Tournament selection tends to work best for TSP
- Each run gives different results due to the random nature of genetic algorithms
- We use a mutation rate of 0.2 and population size of 20
Results and Analysis
How Different Methods Perform
Roulette Wheel selection tends to create more dramatic fitness spikes - you’ll see the blue line jump around more!
The Optimal Solution
Google’s OR-Tools found the best possible route: New York → Boston → Chicago → Minneapolis → Denver → Salt Lake City → Seattle → San Francisco → Los Angeles → Phoenix → Houston → Dallas → St. Louis → New York
Total distance: 7,293 miles
Our genetic algorithm won’t always find this exact solution, but it gets pretty close and does it much faster than checking all possible routes!
What I Learned Building This
Key Insights
- Mapping coordinates - latitude and longitude need to be swapped for proper chart display
- Chart APIs - SVG charts are more responsive but have limitations with axis control
- Genetic algorithms - mutation rates above 0.5 turn GA into random search
- Web workers - essential for keeping UI responsive during heavy calculations
- Performance - population size of 20 and 500 generations work well for this problem size
Real-World Applications
TSP isn’t just academic! It’s used everywhere:
- Delivery companies optimizing routes for drivers
- Circuit board manufacturing minimizing drill paths
- DNA sequencing finding optimal gene arrangements
- Robot path planning in warehouses and factories
Genetic algorithms are perfect for these real-world problems because they can find good solutions quickly, even when the perfect solution would take too long to calculate.