<p>This is an "Orienteering problem" and is NP-hard [1]. If the starting vertex is given the problem is <em>rooted</em>; your variant is <em>unrooted</em>. Some authors call it the "selective travelling salesman" [2].</p>

<p>[1] B. L. Golden, L. Levy, and R. Vohra. "The orienteering problem". In: Naval Research Logistics 34.3 (1987), pp. 307-­318.</p>

<p>[2] M. Gendreau, G. Laporte, and F. Semet. "A tabu search heuristic for the undirected selective travelling salesman problem". In: European Journal of Operational Research (1998), pp. 539­-545.</p>

CC BY-SA 2.5
2011-04-05T11:48:28.653Z
2011-04-05T11:48:28.653Z
Marcus Ritt
<p>You can sell for  $n$ <em>days</em>.
Suppose your average speed is $S$ <em>km/day</em>.<br>
Then you can only travel $nS$ <em>km</em> (that too if you can sell things in 0 seconds).</p>

<p>Let $EP(c)$ be estimated profit for city $c$.</p>

<p>problem:</p>

<p>Find subgraph $H = \{Roads,Cities\}$ with<br>
1. Maximum $\sum_{c\in Cities} EP(c) = EP(H)$<br>
2. $\sum_{r\in Roads} weight(r) &lt; nS$</p>

<p>Also, if salesman can't jump we would want that subgraph to be connected. </p>

<p>This probably isn't NP-hard because we can use dynamic programming to find out all subgraphs with weights less than $nS$.Then we can filter out disconnected subgraphs. And find out $max\{ EP(H) \}$. </p>

CC BY-SA 2.5
2011-03-31T19:42:45.433Z
It is trivial to reduce the Hamiltonian Path problem to the given problem (say that the distance between cities u and v is 1 travelingday if (u,v) is an edge in the graph and is a distance of 2 travelingdays otherwise, and check if the optimal path in n-1 days starting at some city visits all n locations), so the problem is definitely NP Complete unless I'm misunderstanding its formulation.

Your solution just finds an MST, if I'm not mistaken, which doesn't really give a valid solution.
Yonatan N
CC BY-SA 2.5
2011-03-31T20:03:18.327Z
To me it look more like [Knapsack Problem](http://en.wikipedia.org/wiki/Knapsack_problem). Which is $NP-complete$ to solve exactly.
Pratik Deoghare
CC BY-SA 2.5
2011-04-02T21:27:06.577Z
your initial analysis is correct but we definitely can't do that in polytime, as Yonatan correctly explains. There are exponentially many subgraphs that one'd have to check that could have distance less than $nS$. Also, this isn't quite what I asked for (as I can pretty handily do analysis like this)... I just wanted the name of this problem (or a similar one that caps the distance travelled on a TSP).
Eli
CC BY-SA 2.5
2011-03-31T19:20:28.677Z
2011-03-31T19:41:56.327Z
2011-03-31T19:41:56.327Z
Pratik Deoghare
<p>I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take.</p>

<p>It's likely NP-hard, I was just wondering if there's a name for this or similar variants on TSP.</p>

<p><strong>EDIT</strong></p>

<p>Here's a clarification of the problem:</p>

<ul>
<li>Let $S$ be a clique with weighted edges that one could put onto a plane (Euclidian distances, etc.) and $k$ be a positive real number.</li>
<li>A solution $G$ is a subgraph of $S$ that is a simple path such that $\Sigma_{e \in E(G)} e &lt; k$ and $|V(G)|$ is maximized.</li>
</ul>

<p>Or, in terms of geometry:</p>

<ul>
<li>Let $S$ be a set of points on the plane</li>
<li>A solution is a path through some of the points of length less than $k$ that maximizes the number of points hit.</li>
</ul>

CC BY-SA 2.5
2011-03-31T19:05:00.070Z
Please elaborate.
Pratik Deoghare
CC BY-SA 2.5
2011-03-31T19:43:26.260Z
[Prize-collecting TSP](http://dx.doi.org/10.1002/net.3230190602)?
Jukka Suomela
CC BY-SA 2.5
2011-03-31T21:25:05.720Z
Hi Eli. It would be nice if you explain why you are interested in the question since this does not look like a research level question.
Kaveh
CC BY-SA 2.5
2011-04-01T00:37:39.233Z
For Euclidian distances your problem is called "Traveling Salesman Selection Problem".
Marcus Ritt
CC BY-SA 2.5
2011-04-02T04:08:20.027Z
Kaveh, I dunno what qualifies as "research-level", but I was looking at a dataset for the locations of craters on the moon from the LOLA (http://www.planetary.brown.edu/html_pages/LOLAcraters.html) and was wondering where I might want to land a rover to visit as many craters as quickly as possible before running out of fuel or whatever. This obviously generalizes nicely into a number of problems. The one I asked about seemed the most natural, but I couldn't information about it.
Eli
CC BY-SA 2.5
2011-04-02T04:12:47.983Z
@Marcus, that doesn't look like it. TSSP as explained by Hammacher and Moll seems to involve finding a normal TSP tour plus some other stuff.
Eli
CC BY-SA 2.5
2011-04-02T12:15:26.767Z
@Eli I was referring to http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.9727 . I think there are no other requirements, what other stuff are you referring to?
Marcus Ritt
CC BY-SA 2.5
2011-04-02T21:23:27.640Z
@Marcus, first of all, that problem involves solving all of TSP, which is almost certainly harder than my problem when my $n$ is fixed. Secondly, it specifies a number of cities, not a maximum total distance travelled.
Eli
CC BY-SA 2.5
2011-04-03T00:20:25.210Z
@Eli, I see; "n days to sell" and "sell once per city" made me believe your limit is the number of cities. Maybe you could clarify this in the question. Your kind of problem seems to be what is known as an "Orienteering problem", see for example http://dx.doi.org/10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D
Marcus Ritt
CC BY-SA 2.5
2011-04-03T15:44:05.233Z
@Marcus: the orienteering problem actually looks right as described here: http://valis.cs.uiuc.edu/~sariel/papers/05/orient/ -- thanks.
Eli
CC BY-SA 2.5
2011-04-03T19:18:20.593Z
Right, so the main difference between orienteering and prize collecting TSp is that there's no penalty for missing sites. Marcus, why don't you make it an answer so Eli can accept it.
Suresh Venkat
CC BY-SA 2.5
2011-04-03T19:29:48.467Z
Yup, this is the orienteering problem.  http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.62.9247&rep=rep1&type=pdf
Jeffε
CC BY-SA 2.5
2011-04-05T00:25:31.693Z
@Eli, thanks. Your comment is sufficient. I wanted to check if the problem is motivated by an application. (I would suggest adding including the motivation in the post. I am adding application of theory tag.)
Kaveh
<ds.algorithms><graph-algorithms><cg.comp-geom><application-of-theory><tsp>
Is there a local variant of TSP?
Eli
# Is there a local variant of TSP?

(Asked by: username_0 on 2011-03-31)

I'm a traveling salesman and I have n days to sell, I can start anywhere, I can sell once per city. I want to know where to start and what route to take.

It's likely NP-hard, I was just wondering if there's a name for this or similar variants on TSP.

**EDIT**

Here's a clarification of the problem:

* Let $S$ be a clique with weighted edges that one could put onto a plane (Euclidian distances, etc.) and $k$ be a positive real number.
* A solution $G$ is a subgraph of $S$ that is a simple path such that $\Sigma\_{e \in E(G)} e < k$ and $|V(G)|$ is maximized.

Or, in terms of geometry:

* Let $S$ be a set of points on the plane
* A solution is a path through some of the points of length less than $k$ that maximizes the number of points hit.

**Tags:** ds.algorithms, graph-algorithms, cg.comp-geom, application-of-theory, tsp

> **Comments:**
> **username_1**: Please elaborate.  
> **username_2**: [Prize-collecting TSP](http://dx.doi.org/10.1002/net.3230190602)?  
> **username_3**: Hi username_0. It would be nice if you explain why you are interested in the question since this does not look like a research level question.  
> **username_4**: For Euclidian distances your problem is called "Traveling Salesman Selection Problem".  
> **username_0**: username_3, I dunno what qualifies as "research-level", but I was looking at a dataset for the locations of craters on the moon from the LOLA (http://www.planetary.brown.edu/html_pages/LOLAcraters.html) and was wondering where I might want to land a rover to visit as many craters as quickly as possible before running out of fuel or whatever. This obviously generalizes nicely into a number of problems. The one I asked about seemed the most natural, but I couldn't information about it.  
> **username_0**: @Marcus, that doesn't look like it. TSSP as explained by Hammacher and Moll seems to involve finding a normal TSP tour plus some other stuff.  
> **username_4**: @username_0 I was referring to http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.9727 . I think there are no other requirements, what other stuff are you referring to?  
> **username_0**: @Marcus, first of all, that problem involves solving all of TSP, which is almost certainly harder than my problem when my $n$ is fixed. Secondly, it specifies a number of cities, not a maximum total distance travelled.  
> **username_4**: @username_0, I see; "n days to sell" and "sell once per city" made me believe your limit is the number of cities. Maybe you could clarify this in the question. Your kind of problem seems to be what is known as an "Orienteering problem", see for example http://dx.doi.org/10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D  
> **username_0**: @Marcus: the orienteering problem actually looks right as described here: http://valis.cs.uiuc.edu/~sariel/papers/05/orient/ -- thanks.  
> **username_5**: Right, so the main difference between orienteering and prize collecting TSp is that there's no penalty for missing sites. Marcus, why don't you make it an answer so username_0 can accept it.  
> **username_6**: Yup, this is the orienteering problem.  http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.62.9247&rep=rep1&type=pdf  
> **username_3**: @username_0, thanks. Your comment is sufficient. I wanted to check if the problem is motivated by an application. (I would suggest adding including the motivation in the post. I am adding application of theory tag.)  

---

## 2 answers

### Answer by username_4 on 2011-04-05. Score: 4 | Accepted answer

This is an "Orienteering problem" and is NP-hard [1]. If the starting vertex is given the problem is *rooted*; your variant is *unrooted*. Some authors call it the "selective travelling salesman" [2].

[1] B. L. Golden, L. Levy, and R. Vohra. "The orienteering problem". In: Naval Research Logistics 34.3 (1987), pp. 307-­318.

[2] M. Gendreau, G. Laporte, and F. Semet. "A tabu search heuristic for the undirected selective travelling salesman problem". In: European Journal of Operational Research (1998), pp. 539­-545.


---

### Answer by username_1 on 2011-03-31. Score: 0

You can sell for $n$ *days*.
Suppose your average speed is $S$ *km/day*.  
Then you can only travel $nS$ *km* (that too if you can sell things in 0 seconds).

Let $EP(c)$ be estimated profit for city $c$.

problem:

Find subgraph $H = \{Roads,Cities\}$ with  
1. Maximum $\sum\_{c\in Cities} EP(c) = EP(H)$  
2. $\sum\_{r\in Roads} weight(r) < nS$

Also, if salesman can't jump we would want that subgraph to be connected.

This probably isn't NP-hard because we can use dynamic programming to find out all subgraphs with weights less than $nS$.Then we can filter out disconnected subgraphs. And find out $max\{ EP(H) \}$.

> **Comments:**
> **username_7**: It is trivial to reduce the Hamiltonian Path problem to the given problem (say that the distance between cities u and v is 1 travelingday if (u,v) is an edge in the graph and is a distance of 2 travelingdays otherwise, and check if the optimal path in n-1 days starting at some city visits all n locations), so the problem is definitely NP Complete unless I'm misunderstanding its formulation.  Your solution just finds an MST, if I'm not mistaken, which doesn't really give a valid solution.  
> **username_1**: To me it look more like [Knapsack Problem](http://en.wikipedia.org/wiki/Knapsack_problem). Which is $NP-complete$ to solve exactly.  
> **username_0**: your initial analysis is correct but we definitely can't do that in polytime, as Yonatan correctly explains. There are exponentially many subgraphs that one'd have to check that could have distance less than $nS$. Also, this isn't quite what I asked for (as I can pretty handily do analysis like this)... I just wanted the name of this problem (or a similar one that caps the distance travelled on a TSP).  

---

