# What is this prize-collecting optimization problem with travel times?

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.

• 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)$? – Billiska Sep 13 '14 at 18:47
• Yes! if vertex $i$ is visited at two times,the total reward get increased only once! – Mohammad Khosravi Sep 13 '14 at 19:39
• @Billiska Do you have any idea in any case? – Mohammad Khosravi Sep 13 '14 at 20:40
• 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. – Billiska Sep 13 '14 at 21:50