4
$\begingroup$

There exist very rich literature on discrete optimization problems such as variants of knapsack problem, traveling salesman problem, orienteering problem, tourist trip design problem and etc. Recently, I have encountered a question during my research which I like to know what this problem is? Is it a variant of a famous problem like the above list and is there any literature on it?

Problem: Suppose there is a tourist moving over a graph and in visiting each vertex collects a reward respective to that vertex. Let ${\mathcal G}=({\mathcal V},{\mathcal E})$ be the graph and $T(t)=(\tau_{ij}(t))$ be a time dependent matrix where $\tau_{ij}(t)$ represents traveling time from vertex $i$ to $j$ if the travel being started at time $t$, for any $i,j\in {\mathcal V}$ and $t\in {\mathbb R}$ (Note that if $ij\notin {\mathcal E}$, then $\tau_{ij}(t)=\infty$). Also, let ${\rm r}(t)=(r_i(t))$ be the time dependent vector for vertex visits, i.e. if the vertex $i$ be visited at time $t$ then a reward equal to $r_i(t)$ is collected ($r_i$ is a strictly decreasing function, for any $i\in {\mathcal V}$). The goal is maximizing the total collected reward.

In a simpler form one may let $T$ be constant.

$\endgroup$
  • $\begingroup$ Does the reward disappear from a vertex after it has been collected? For example, if vertex $i$ is visited at both time $t_1,t_2$, do the total reward get increased by only $r_i(t_1)$ and not $r_i(t_1)+r_i(t_2)$? $\endgroup$ – Billiska Sep 13 '14 at 18:47
  • $\begingroup$ Yes! if vertex $i$ is visited at two times,the total reward get increased only once! $\endgroup$ – Mohammad Khosravi Sep 13 '14 at 19:39
  • $\begingroup$ @Billiska Do you have any idea in any case? $\endgroup$ – Mohammad Khosravi Sep 13 '14 at 20:40
  • $\begingroup$ In the case where reward can be collected again at the same vertex, we can quite simply solve it by dynamic programming. The dynamic programming is done by updating $R(i,t)$ --- the best total reward among explored paths that ends at vertex $i$ at time $t$ --- in the order of increasing $t$. So this version of the problem is pseudo-polynomial time similar to knapsack problem. However, I do not know a famous problem that would match exactly this problem. $\endgroup$ – Billiska Sep 13 '14 at 21:50

Your Answer

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

Browse other questions tagged or ask your own question.