What is the name of this logistic variant of TSP?

Question

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the problem.

I have $P$ warehouses on the Cartesian plane. There's a path from a warehouse to every other warehouse and the distance metric used is the Euclidean distance. In addition, there are $n$ different items. Each item $1 \leq i \leq n$ can be present in any number of warehouses. We have a collector and we are given a starting point $s$ for it, say the origin $(0,0)$. The collector is given an order, so a list of items. Here, we can assume that the list only contains distinct items and only one of each. We must determine the shortest tour starting at $s$ visiting some number of warehouses so that the we pick up every item on the order.

Here's a visualization of a randomly generated instance with $P = 35$. Warehouses are represented with circles. Red ones contain item $1$, blue ones item $2$ and green ones item $3$. Given some starting point $s$ and the order ($1,2,3$), we must pick one red, one blue and one green warehouse so the order can be completed. By accident, there are no multi-colored warehouses in this example so they all contain exactly one item. This particular instance is a case of set-TSP.

I can show that the problem is indeed $\mathcal{NP}$-hard. Consider an instance where each item $i$ is located in a different warehouse $P_i$. The order is such that it contains every item. Now we must visit every warehouse $P_i$ and find the shortest tour doing so. This is equivalent of solving an instance of $\text{TSP}$.

Being so obviously useful at least in the context of logistic, routing and planning, I'm sure this has been studied before. I have two questions:

1. What is the name of the problem?
2. How well can one hope to approximate the problem (assuming $\mathcal{P} \neq \mathcal{NP}$)?

I'm quite happy with the name and/or reference(s) to the problem. Maybe the answer to the second point follows easily or I can find out that myself.

Answer 1

The problem is in $\mathrm{P}$ if the number of items is constant.

Let $K$ be the number of items (independent of $n$). For every ordering of items, use backtracking to try all allowed routes: you first go through some warehouse for the first item (trying all warehouses), then one for the second item and so on.

There are $O(K!)$ orderings of the items. Let $W_i$ be the number of warehouses for item $i$. The number of routes is $\prod_{i=1}^K W_i \leq \prod_{i=1}^K n = n^K$. Therefore, the running time of the above algorithm is $O(K! n^K)$, which is polynomial for fixed $K$.

If the number of items can be linear in $n$, the problem is at least as hard to approximate as $TSP$: you can take an instance of $TSP$, make an item for every vertex as you noted, and then add extra vertices very far away from all other vertices to inflate $n$ (and therefore allow for enough items that every vertex of the $TSP$ instance has a different item), without destroying the hardness of approxability of $TSP$. Note that if your points are in the Euclidian plane, then this doesn't really help you as there is a $PTAS$ for planar $TSP$.

Answer 2

Among others, this problem can be seen as an instance of the Traveling Purchaser Problem. $\text{TPP}$ is a generalization of $\text{TSP}$ and was first proposed by T. Ramesh, Traveling purchaser problem, 1981. The problem is as follows:

We are given a set $M = \{ 1, ..., m \}$ of markets and a set of $N = \{ 1, ..., n \}$ of products. Also we are given $c_{ij}$, the cost of traveling from city $i$ to city $j$, and non-negative $d_{ij}$, the cost of a product $i$ at market $j$. The purchaser starts from his home city (for example city $1$), and travels to a subset of the $m$ cities and purchases each of the $n$ products in of the cities he visits, and return back to his home city. The objective is to find a tour for the purchaser that such that the sum of the travel and purchase costs are minimized.

So, put in the terms of the original question, warehouses are markets. Each available item at a market has equal price. If item $i$ is not available at a market $j$, its price $d_{ij}$ is set to a high value.

In addition to containing $\text{TSP}$, $\text{TPP}$ contains prize collecting $\text{TSP}$, uncapacited facility location problem, group Steiner tree problem and the set cover problem as its immediate special cases. For the hardness, following from current hardness results for set cover, it follows that there is no PTAS for $\text{TPP}$ even with metric travel costs whose performance ratio is better than $(1-o(1))\ln n$ unless $\mathcal{P} = \mathcal{NP}$. For additional discussion and formulation as an IP, see for example R. Ravi and F. S. Salman, Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design, 1999. The Wikipedia entry for TPP also gives links to some heuristic approaches.

Answer 3

What you described sounds more like a planning problem in AI. It sounds like what might be modeled with a planning language, such as STRIPS, ADL, PDDL, etc. Once modeled, the plan can then be solved by one of many planning algorithms/heuristics, which are typically state space search algorithms. The Wiki links should get you started. A planning chapter in any AI textbook can also help. An example of PDDL planner is the GraphPlanner software.

Granted some rather degenerate instances of this problem may be equivalent to TSP, this problem is not in general the same as TSP, nor is it Set TSP. In both TSP and Set TSP, the set of cities (warehouses) to be visited is predefined. Here, we don't really care about what warehouses are visited, but rather we only care about fulfilling an order as cheaply and efficiently as possible. You could have orders that cannot be fulfilled. A planner will come back with an empty plan or a partial one in such a case -- a non-satisfiability report. The plan satifiability problem is known in general to be PSPACE-complete. In TSP or Set TSP, an optimal tour always exists -- it might not be unique though.