1
$\begingroup$

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

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ Please give a self-contained statement of the problem. What are customers, prizes, traveling costs, etc.? $\endgroup$
    – Jeffε
    Mar 17, 2013 at 3:10
  • $\begingroup$ 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). $\endgroup$
    – tesseract
    Mar 17, 2013 at 18:50
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jeffε
    Mar 17, 2013 at 19:05
  • 1
    $\begingroup$ 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? $\endgroup$
    – Jeffε
    Mar 17, 2013 at 19:17
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Mar 17, 2013 at 21:21

1 Answer 1

Reset to default
0
$\begingroup$

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 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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.