Problem Description: Given n cities and the costs of travelling from one city to any other city, find a minimum cost route that starts and ends at a given city and the route visits every other city exactly once. It is a combinatorial optimization problem and no polynomial-time solution exists to this problem (NP-complete).
State Space: A permutation of the cities already visited
S = (k, (c1, c2, c3, ....., ck), w)
where k is the number of cities already visited,
ci is the ith visited city
w is the cost of root till now
Operators: select cj such that cj is not in the list of visited cities. add cost(ck, cj) to w and update S
Result: sequence of cities in the order of their visits
Some basic approaches to Solve the Problem
Naive Exhaustive-Search Approach (Brute-force): Search through all possible routes satisfying the constraints and return the one with minimum cost. O((n-1)!)
Branch and Bound Approach: Predict the minimum cost (bound) of an optimal route, say, using a greedy approach. At any instant while executing the previous Naive approach if the cost of the partial path exceeds the predicted minimum cost backtrack from there. Keep updating the minimum cost bound as some feasible solutions are obtained.
Other Approaches include Dynamic Programming(O(n^2 * 2^n)), Linear Programming, Branch-and-cut, etc.
Applications: Besides TSP itself (which includes School Bus routing, postal deliveries) there are various applications that can be modeled into TSP e.g. scheduling a drill machine to drill holes at particular locations on a circuit board.
Many other applications are listed in: http://iris.gmu.edu/~khoffman/papers/trav_salesman.html
Milestones in the solution of TSP instances: 49(1954), 57(1971), 64(1971), 67(1975), 80(1975), 120(1977), 318(1980), 532(1987), 666(1987), 1002(1987), 2392(1987), 3038(1992), 4461(1993), 7397(1994), 13509(1998), 15112(2001), 24978(2004), 33180(2004), 85900(2006)
- A page devoted to the applications, history and benchmarks of the TSP problem
Monalisa TSP Challenge (100,000 cities) - $100 prize to the first person to find a tour shorter than length 5,757,191.
- Book: The Traveling Salesman Problem: A Computational Study - http://bit.ly/bxoX3V
Available in UIUC Library, but issuedby someone for this semester
- Book: The travelling Salesman Problem and its variations by Gutin, Punnen. Available at Grainger/ Math (http://vufind.carli.illinois.edu/vf-uiu/Record/uiu_4513194)
- Concorde: http://www.tsp.gatech.edu/concorde.html
a library of TSP code, also publishes the benchmark run-times for various datasets run over a single processor with 533MHz speed and 2GB RA
Humor (found on web):