<p>This has been called "Discounted Reward." In my brutish opinion, steer toward the CS guys and away from the OR guys. I just like the lit better.</p>

<p>See: <a href="https://www.cs.cmu.edu/afs/cs.cmu.edu/user/avrim/www/Papers/orienteering-sicomp.pdf" rel="nofollow">"Approximation Algorithms for Orienteering and Discounted-Reward TSP." <em>FOCS</em> 2003</a> Which I just stole from my colleague's desk. </p>

<p>They model reward as $\lambda^{-t}$, where $t$ is time, and $\lambda$ is constant, but otherwise it is the standard <em>orienteering</em> formulation: Maximize reward, subject to a budget, or minimize budget subject to a reward constraint.</p>

CC BY-SA 3.0
2013-03-14T21:31:04.307Z
2013-03-14T21:31:04.307Z
Josh Vander Hook
<p>Hej guys,</p>

<p>I'm working on customizing a <a href="http://en.wikipedia.org/wiki/Vehicle_routing_problem" rel="nofollow">Vehicle Routing Problem</a> for a practical case, which is characterized as follows:</p>

<ul>
<li>The set of customers does not change over time, but their respective prizes are degressing in a  non-linear fashion (deterministic).</li>
<li>Traveling costs do not change.</li>
<li>Need to visit every customer exactly once.</li>
</ul>

<p>So I've been digging through tons of papers and such, but I can't find anything similar to the given case .. The Dynamic VRP goes way too far, with stochastics and redefining the routes in an ongoing fashion, which I do not need in this special case, because the degression of prizes is deterministic. I thought about the Traveling Repairman Problem, but I can't come up with a way to use it .. The VRP with Time Windows seems to be a completely different case as I have no opening or closing times.</p>

<p>Maybe someone got any hints for me ? I'm pretty sure this case has been dealt with, as it seems to be practically relevant.</p>

<p>Any help is appreciated !</p>

<p><strong>Edit:</strong> as mentioned in the comments I should provide a sufficient version of the VRP:</p>

<p><strong>Input:</strong><br>
N: given set of customers,<br>
D: given set of demands of said customers,<br>
C: given set of traveling costs, where c_ij is the weight of the arc (i,j),<br>
M: maximum number of vehicles that may be used,<br>
V: fixed costs of using a vehicle,<br>
Q: capacity of a vehicle,<br>
P: set of prizes for every customer,<br>
f(t): a function describing the degression of the prizes,<br>
(I'm not sure yet whether I want to visit every customer or not)  </p>

<p><strong>Output:</strong><br>
Optimal routes with the following objective:  </p>

<ul>
<li>minimize total costs of travel,  </li>
<li>minimize number of vehicles used,  </li>
<li>maximize sum of prizes.  </li>
</ul>

<p>Whether finding the optimal solution is possible or not is not really of interest in the first place.</p>

<p>[As I looked for questions related to the VRP, TSP and similar models, these were posted in theoretical CS, but now I see that this section is definitely not the right one for me ..]</p>

CC BY-SA 3.0
2013-03-17T03:10:33.250Z
Please give a _self-contained_ statement of the problem.  What are customers, prizes, traveling costs, etc.?
Jeffε
CC BY-SA 3.0
2013-03-17T18:50:27.837Z
I'm not sure what you mean - this is just a version of the usual VRP, but with mentioned restrictions. Customers / prizes / traveling costs - those are the usual sets of characteristics in VRP (or the PCVRP in the case of prizes).
tesseract
CC BY-SA 3.0
2013-03-17T18:59:52.167Z
Usually you could use the traveling costs as the time it takes to get from node i to node j, but in this special case I have to come up with a relationship between the position of a customer in the schedule and his prize. The PCVRP defines the prizes as static, that's why I can't use it. I thought about something like: `x_ij * (a_i + s_i) = a_j` as a restriction, where `x_ij` is a boolean (1 if customer j is serviced right after customer i, else 0), `a_i` is the arrival time at the customer i and `s_i` the service time of customer i.
tesseract
CC BY-SA 3.0
2013-03-17T19:05:05.297Z
There is more than one "usual vehicle routing problem".  If it's really that standard, it should be easy for you to give a self-contained problem statement.
Jeffε
CC BY-SA 3.0
2013-03-17T19:08:00.240Z
As I already said - I don't know what you would like to know - a description of the VRP or a mathematical model or the special case that I'm working at ? You already linked the wiki article for the VRP, I'm not sure what information I could provide otherwise ..
tesseract
CC BY-SA 3.0
2013-03-17T19:17:03.953Z
The Wikipedia article mentions four different problems.  I'm looking for a single self-contained problem statement.  What precisely is your input?  What precisely is your output?
Jeffε
CC BY-SA 3.0
2013-03-17T19:29:15.557Z
Input: N: given set of customers. D: given set of demands of said customers. C: given set of traveling costs, where c_ij is the weight of the arc (i,j). M: maximum number of vehicles that may be used. V: fixed costs of using a vehicle. Q:  capacity of a vehicle. P: set of prizes for every customer. f(t): a function describing the degression of the prizes.(I'm not sure yet whether I want to visit every customer or not.) Output: optimal routes with  the following objective: minimize total costs of travel, minimize number of vehicles used, maximize sum of prizes. Is that self-contained ?
tesseract
CC BY-SA 3.0
2013-03-17T21:21:54.197Z
You should move these into the post. Also it seems that you have multiple objective functions and it might not be possible to achieve the optimal for all of them at the same time, so the question is still not clear. ps: The scope of the site is *theoretical* computer science and you should try to formulate your question clearly and unambiguously. You may want to look at the "how to write a better question" section of the [faq].
Kaveh
CC BY-SA 3.0
2013-03-18T16:06:15.467Z
Sorry, but what's a "customer"?  What's a "demand"?  What's a "vehicle"?  What's a "prize"?  Please give a **self-contained** description of the problem.  (For example: "The input is a directed graph $G=(V,E)$, a non-negative cost function $c\colon E\to\mathbb{R}$, a subset $N$ of the vertices (called _customers_),....")
Jeffε
CC BY-SA 3.0
2013-03-18T17:20:59.917Z
Well ... is it really necessary for me to copy-paste a general description of the VRP ? I may be wrong, but in my understanding there is a "general" version of the VRP, which is defined in a quite precise way. Please refer to something like [Classical and modern heuristics for the vehicle routing
problem](http://140.113.119.114/students/thesis/096/2/Literature/%E8%AB%96%E6%96%87%E5%8F%83%E8%80%83/GENIUS/2000_Classical%20and%20Modern%20heuristic%20for%20the%20VRP.pdf), for a self-contained description. You're right - there are many variants, but the "core VRP" remains the same.
tesseract
<co.combinatorics><combinatorics>
PCVRP with prizes reduced over time
tesseract
# PCVRP with prizes reduced over time

(Asked by: username_0 on 2013-03-14)

Hej guys,

I'm working on customizing a [Vehicle Routing Problem](http://en.wikipedia.org/wiki/Vehicle_routing_problem) for a practical case, which is characterized as follows:

* The set of customers does not change over time, but their respective prizes are degressing in a non-linear fashion (deterministic).
* Traveling costs do not change.
* Need to visit every customer exactly once.

So I've been digging through tons of papers and such, but I can't find anything similar to the given case .. The Dynamic VRP goes way too far, with stochastics and redefining the routes in an ongoing fashion, which I do not need in this special case, because the degression of prizes is deterministic. I thought about the Traveling Repairman Problem, but I can't come up with a way to use it .. The VRP with Time Windows seems to be a completely different case as I have no opening or closing times.

Maybe someone got any hints for me ? I'm pretty sure this case has been dealt with, as it seems to be practically relevant.

Any help is appreciated !

**Edit:** as mentioned in the comments I should provide a sufficient version of the VRP:

**Input:**  
N: given set of customers,  
D: given set of demands of said customers,  
C: given set of traveling costs, where c\_ij is the weight of the arc (i,j),  
M: maximum number of vehicles that may be used,  
V: fixed costs of using a vehicle,  
Q: capacity of a vehicle,  
P: set of prizes for every customer,  
f(t): a function describing the degression of the prizes,  
(I'm not sure yet whether I want to visit every customer or not)

**Output:**  
Optimal routes with the following objective:

* minimize total costs of travel,
* minimize number of vehicles used,
* maximize sum of prizes.

Whether finding the optimal solution is possible or not is not really of interest in the first place.

[As I looked for questions related to the VRP, TSP and similar models, these were posted in theoretical CS, but now I see that this section is definitely not the right one for me ..]

**Tags:** co.combinatorics, combinatorics
> **Comments:**
> **username_1**: Please give a _self-contained_ statement of the problem.  What are customers, prizes, traveling costs, etc.?  
> **username_0**: I'm not sure what you mean - this is just a version of the usual VRP, but with mentioned restrictions. Customers / prizes / traveling costs - those are the usual sets of characteristics in VRP (or the PCVRP in the case of prizes).  
> **username_0**: Usually you could use the traveling costs as the time it takes to get from node i to node j, but in this special case I have to come up with a relationship between the position of a customer in the schedule and his prize. The PCVRP defines the prizes as static, that's why I can't use it. I thought about something like: `x_ij * (a_i + s_i) = a_j` as a restriction, where `x_ij` is a boolean (1 if customer j is serviced right after customer i, else 0), `a_i` is the arrival time at the customer i and `s_i` the service time of customer i.  
> **username_1**: There is more than one "usual vehicle routing problem".  If it's really that standard, it should be easy for you to give a self-contained problem statement.  
> **username_0**: As I already said - I don't know what you would like to know - a description of the VRP or a mathematical model or the special case that I'm working at ? You already linked the wiki article for the VRP, I'm not sure what information I could provide otherwise ..  
> **username_1**: The Wikipedia article mentions four different problems.  I'm looking for a single self-contained problem statement.  What precisely is your input?  What precisely is your output?  
> **username_0**: Input: N: given set of customers. D: given set of demands of said customers. C: given set of traveling costs, where c_ij is the weight of the arc (i,j). M: maximum number of vehicles that may be used. V: fixed costs of using a vehicle. Q:  capacity of a vehicle. P: set of prizes for every customer. f(t): a function describing the degression of the prizes.(I'm not sure yet whether I want to visit every customer or not.) Output: optimal routes with  the following objective: minimize total costs of travel, minimize number of vehicles used, maximize sum of prizes. Is that self-contained ?  
> **username_2**: You should move these into the post. Also it seems that you have multiple objective functions and it might not be possible to achieve the optimal for all of them at the same time, so the question is still not clear. ps: The scope of the site is *theoretical* computer science and you should try to formulate your question clearly and unambiguously. You may want to look at the "how to write a better question" section of the [faq].  
> **username_1**: Sorry, but what's a "customer"?  What's a "demand"?  What's a "vehicle"?  What's a "prize"?  Please give a **self-contained** description of the problem.  (For example: "The input is a directed graph $G=(V,E)$, a non-negative cost function $c\colon E\to\mathbb{R}$, a subset $N$ of the vertices (called _customers_),....")  
> **username_0**: Well ... is it really necessary for me to copy-paste a general description of the VRP ? I may be wrong, but in my understanding there is a "general" version of the VRP, which is defined in a quite precise way. Please refer to something like [Classical and modern heuristics for the vehicle routing problem](http://140.113.119.114/students/thesis/096/2/Literature/%E8%AB%96%E6%96%87%E5%8F%83%E8%80%83/GENIUS/2000_Classical%20and%20Modern%20heuristic%20for%20the%20VRP.pdf), for a self-contained description. You're right - there are many variants, but the "core VRP" remains the same.  

---

## 1 answers

### Answer by username_3 on 2013-03-14. Score: 0 | Accepted answer

This has been called "Discounted Reward." In my brutish opinion, steer toward the CS guys and away from the OR guys. I just like the lit better.

See: ["Approximation Algorithms for Orienteering and Discounted-Reward TSP." *FOCS* 2003](https://www.cs.cmu.edu/afs/cs.cmu.edu/user/avrim/www/Papers/orienteering-sicomp.pdf) Which I just stole from my colleague's desk.

They model reward as $\lambda^{-t}$, where $t$ is time, and $\lambda$ is constant, but otherwise it is the standard *orienteering* formulation: Maximize reward, subject to a budget, or minimize budget subject to a reward constraint.


---

