[Solved]: What is the name of this logistic variant of TSP?

ignougroup
Problem Detail: 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. An instance of the problem. 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.

Asked By : Juho

Answered By : Juho

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1440