Notes on the TSP and related problems

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 (M,d), where M is a set and d: M \times M \rightarrow \mathbb{R} is a distance function satisfying the following properties:

  • d(x,y) \geq 0 \forall x, y \in M.
  • d(x,y) = 0 iff x = y.
  • d(x,y) = d(y,x).
  • d(x,y) + d(y,z) \geq d(x,z).

1. TSP: Given a n-vertex metric space (V,d) and m points in V, find a minimum length tour that covers all m points.

Notes on the TSP:

  • No point that is not one of the specified m 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 m 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 (V,d), a Source set S \subset V, a Destination set T \subset V, and a number k, such that S \cap T = \phi, \sum_{s \in S} x_s = m and \sum_{t \in T} y_t = m, where x_s represents the number of items available (i.e. capacity) at source point s, and y_t represents the requirement at destination point, t, find a minimum length tour of a vehicle that transports all m items from source points to the destination points such that the vehicle carries at most k 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 S \cup T. 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 m specified points. Choose an arbitrary point, say r,  among the specified points, designate it as a source point with capacity m-1, and designate the remaining m-1 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.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: