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