1
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Rather than knapsack, it probably makes more sense to think in terms of travelling salesman. $\endgroup$ – David Richerby Apr 16 '17 at 0:06
  • $\begingroup$ I was thinking about that as well, but as fare as I know, TSP wilk only give me the order in which I should visit the nodes but does not select a subset, or am I wrong? $\endgroup$ – user3019653 Apr 17 '17 at 9:20
  • $\begingroup$ The subset aspect certainly means that it's not a pure TSP problem. But to me, "TSP, except that, if I can't visit all the cities, I just want to go to the most important ones" feels much closer to standard TSP than "knapsack, except that the weight of items that haven't yet been chosen varies depending on what the most recently added item was (oh, and by the way, it varies as a Euclidean distance)" seems to regular knapsack. $\endgroup$ – David Richerby Apr 17 '17 at 10:44
  • $\begingroup$ True that. Should I edit my question accordingly or open a new one? $\endgroup$ – user3019653 Apr 17 '17 at 10:53
  • $\begingroup$ It's up to you. If you do post a second question, it would be good to link between them for context. I think what I would do is edit this question to make it method-agnostic. Something along the lines of "Here's my problem. I've thought about it as a variant of knapsack where the weights are variable, and it also looks like a variant of TSP. How do I solve this?" $\endgroup$ – David Richerby Apr 17 '17 at 11:04
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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