The Traveling Salesman Problem
Overview
Why study TSPs?
Other Application
Timeline
Timeline continued
15,112 Cities in Germany
24,978 cities in Sweden
71009 in China
1,904,711 Cities in the World
Approaches to Solving TSPs
Heuristic Approaches
Exact Solutions
The Ant Algorithm
Conclusion
Works Cited

Heuristic Approaches

By using approaches based on heuristics, practical applications of TSP can be solved since the optimal solution is not always needed. By using heuristics, sub-optimal solutions can be found, and often times just having a solution is “good enough”. Random Optimizations Optimised Markov chain algorithms which utilise local searching heuristically sub-algorithms can find a route extremely close to the optimal route for 700-800 cities. Local Search Start off with a valid tour, then use local moves to improve the tour. Terminates at a “local minimum.” Nearest Neighbor Start at a node, and selected the nearest unvisited node; repeat until done. Worst case creates a complexity of ½ log n. Greedy Algorithm Start with empty partial tour. Add smallest edge that results in a valid partial tour. Repeat until complete tour reached. Worst case creates a complexity of ½ log n.