Which algorithm suits this problem best?
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.