7
$\begingroup$

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.
Improve this question
$\endgroup$
13
  • 3
    $\begingroup$ Prize-collecting TSP? $\endgroup$
    – Jukka Suomela
    Mar 31, 2011 at 19:43
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Mar 31, 2011 at 21:25
  • 1
    $\begingroup$ 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 (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. $\endgroup$
    – Eli
    Apr 2, 2011 at 4:08
  • 2
    $\begingroup$ @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 dx.doi.org/10.1002/… $\endgroup$
    – Marcus Ritt
    Apr 3, 2011 at 0:20
  • 1
    $\begingroup$ @Marcus: the orienteering problem actually looks right as described here: valis.cs.uiuc.edu/~sariel/papers/05/orient -- thanks. $\endgroup$
    – Eli
    Apr 3, 2011 at 15:44

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0
0
$\begingroup$

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) \}$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Mar 31, 2011 at 19:42
  • $\begingroup$ To me it look more like Knapsack Problem. Which is $NP-complete$ to solve exactly. $\endgroup$
    – Pratik Deoghare
    Mar 31, 2011 at 20:03
  • $\begingroup$ 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). $\endgroup$
    – Eli
    Apr 2, 2011 at 21:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.