# PCVRP with prizes reduced over time

Hej guys,

I'm working on customizing a 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 ..]

• Please give a self-contained statement of the problem. What are customers, prizes, traveling costs, etc.? Mar 17, 2013 at 3:10
• 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). Mar 17, 2013 at 18:50
• 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. Mar 17, 2013 at 19:05
• 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? Mar 17, 2013 at 19:17
• 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. Mar 17, 2013 at 21:21

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.