Which algorithm suits this problem best? I have an optimization problem and I'm looking to find an algorithm whitch best fits this. The problem is the following:

There are several points of interest (POI), each has a value (for the user), the distance to each other POI is also known.
Now I want to generate the best tour (ordered list of POIs) with the most value for the user given a maximum distance he has to travel. 

At first I was thinking about the knapsack problem where the distance would be the weight. The problem is, the order of the POIs is important and the weights vary according to the POIs already selected (more specifically, they depend on the last POI selected). Another idea is using TSP, where I first need to somehow select the subset of nodes which should be visited.

Does anyone have an idea, which known problem is similar to the one described and/or if there is an algorithm solving this. I'm not looking for an ideal solution, a good approximization is fine as well. Also perfomance is not an issue (for now).
I thought of a method to state this problem completely in terms of metric vertex weights, which could be considered a (very non-standard) kind of TSP.

In particular, look at the following subproblem:


  Given a graph $G=(V,E)$, with an initial vertex $v_0\in V$, a distance function $d : E\rightarrow \mathbb{R}^+$ such that the graph is metric, a function $p : V \rightarrow \mathbb{R^+}$ that assigns points to vertices, a maximum distance $D$, a minimum value $P$ and an integer $k$. 
  Determine if there exists a (simple) tour on $G$ starting at $v_0$ of exactly $k$ vertices such that the total distance is less than $D$ and the sum of the points $p(v)$ is at least $P$.


So, we want to find a tour of vertices $v_1,\ldots,v_k$ with total distance at most $D$, so $\sum_{i=1}^{k-1} d(v_i,v_{i+1})\leq D$. Additionally, we want to have enough POI points, so $\sum_{i=1}^{k} p(v_i)\geq P$. We will rewrite to the second condition to be similar to the first.

We can replace the second condition by $\sum_{i=1}^{k} -p(v_i)\leq -P$, but now we have negative weights. Since we have fixed $k$, we can solve this by adding the value $p^* =\max_{v\in V}p(v)$ to every individual point: set $p'(v_i):=p^*-p(v_i)$ and $P':=k\cdot p^* - P$, so we get $\sum_{i=1}^{k} p'(v_i)\leq P'$. Now, $p'(v_i) = p^*-p(v_i)$ is non-negative, and we may assume $P'=k\cdot p^*-P$ non-negative, since we know for sure that we cannot get enough points in any tour of $k$ vertices otherwise.

Now, the difference is that points are assigned to vertices in stead of edges. We solve this by defining $p'(v,w):= \frac{1}{2}(p'(v) + p'(w))$ and now we require $\sum_{i=1}^{k-1} p'(v_i,v_{i+1})\leq P'$. This is still equivalent to the previous condition, as we must leave and enter every vertex on a (simple) tour exactly once. Note that $p'(v,w) \leq p'(v,w)+ p'(u) = \frac{1}{2} (p'(v) + p'(w)) +p'(u) = \frac{1}{2}(p'(v)+p'(u)) + \frac{1}{2}(p'(u) +p'(w)) = p'(v,u) + p'(u,w)$ for any $u,v,w\in V$, since $p'(u)$ is positive. So, the distance $p'$ is metric on $G$, as it satisfies the triangle inequality.

Now, there are no more differences between the pairs $(p',P')$ and $(d,D)$. This means that we can phrase our subproblem as follows: determine if there exists a simple tour of exactly $k$ vertices of length at most $P'$ under metric $p'$ AND of length at most $D$ under metric $d$. I call this the $k$-vertex simultaneous TSP. 

Note that this problem, if we assume $(p',P')$ arbitrary, could actually be a lot harder than the current problem. $(p',P')$ is extremely 'regular' for a TSP, since the order in which we visit the vertices doesn't matter for this metric. (which should be the case, since it didn't matter in the original formulation either)



Initially, I thought this approach would lead to a regular TSP problem, but it seemed more unlikely as I wrote it down. Nevertheless, I think the ideas here can be useful in approaching the problem, at least. I don't see a way to 'combine' the different distances for an exact solution, but it might be possible if we are satisfied with an approximation.