Traveling Salesman Problem

Skip to end of metadata
Go to start of metadata

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

Benchamark:

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)

Links:

Humor (found on web):

 

Enter labels to add to this page:
Please wait 
Looking for a label? Just start typing.