patternMinor
What is the name of this logistic variant of TSP?
Viewed 0 times
thistspthevariantwhatnamelogistic
Problem
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:
I'm quite happy with the name and/or reference(s) to the problem. May
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:
- What is the name of the problem?
- 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. May
Solution
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$.
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$.
Context
StackExchange Computer Science Q#1440, answer score: 6
Revisions (0)
No revisions yet.