# 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.