Notes on the TSP and related problems
July 28, 2010 Leave a comment
Here are the problem definitions and some notes on the metric versions of the Traveling Salesman Problem and related problems.
A metric space is defined as an ordered pair , where is a set and is a distance function satisfying the following properties:
1. TSP: Given a n-vertex metric space and points in , find a minimum length tour that covers all points.
Notes on the TSP:
- No point that is not one of the specified points will be visited by the optimal TSP tour. This follows directly from the triangle inequality (visiting a point, v that is not one of the specified points, can be short cut by bypassing v to obtain a tour that is shorter than one that visits v).
- The optimal tour is a cycle, i.e. no point is visited more than once. This, again, follows from the triangle inequality.
- TSP is NP-hard.
2. k-delivery TSP: Given an n-vertex metric space , a Source set , a Destination set , and a number , such that , and , where represents the number of items available (i.e. capacity) at source point , and represents the requirement at destination point, , find a minimum length tour of a vehicle that transports all items from source points to the destination points such that the vehicle carries at most items at all times during the tour.
Notes on the k-delivery TSP:
- Implicit in the problem statement are the assumptions that all source points in S are identical, and that all destination points in T are identical, and that all items are identical. In other words, any item can be transported from any source to any destination.
- The problem can require the tour to start at a particular point. Intuitively, it seems that, unlike in the case of metric TSP, having a fixed starting point can result in a longer tour than what may be obtained given the freedom to choose any starting point.
- There are two versions of this problem. The preemptive version allows the vehicle to drop off an item at an intermediate point that is not a destination point. The non-preemptive version does not allow this freedom.
- For the non-preemptive version of the problem, the optimal tour would involve only the points in . This follows from the triangle inequality.
- k-delivery TSP generalizes TSP and hence is NP-hard.
Consider a TSP instance requiring a least cost tour covering specified points. Choose an arbitrary point, say r, among the specified points, designate it as a source point with capacity , and designate the remaining points as destinations with unit requirement. An optimal k-delivery TSP tour for this instance corresponds to an optimal TSP tour.
- An application of k-delivery TSP: Suppose that Coke has a certain number of storehouses in a particular town, from where it needs to transport cartons of bottles to stores across the town. A carton can go from any storehouse to any store, and there is only one vehicle for carrying the cartons, and it can carry at most a certain number of cartons at any time.