9
$\begingroup$

I am trying to benchmark our vehicle routing solver against Gehring & Homberger instances. However, I got bit puzzled by the route duration constraint (maximum driving / maximum working time). In some data set format, this constraint is enforce as end time window of the depot (Option1): e.g. see here. However, in some other references, e.g. Vidal et. al 2013, this constraint is different: i.e. enter image description here, which actually means arrivalTimeBackAtDepot - departureTimeFromDepot <= maxRouteDuration (Option2). Hence, an Option2 solution could be infeasible for Option1.

Could anyone shed some light on this? How are the results compared and updated on Sintef webpage?

Thank you in advance.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ Hi @VeGh and welcome to OR@SE. I think your question would benefit from some links to the related websites that you mention. It would be nice if you could edit your question and add some relevant links for the convenience of the reader. $\endgroup$
    – JakobS
    Commented Jul 3, 2019 at 10:18
  • $\begingroup$ I noticed that some academic datasets (I don't recall which ones) had visits that had a dueTime later than the planning window time, so I (automatically shorten it and show a warning](github.com/kiegroup/optaplanner/blob/master/…). Is that related in any way? $\endgroup$
    – Geoffrey De Smet
    Commented Jul 3, 2019 at 13:39

1 Answer 1

Reset to default
4
$\begingroup$

You seem to be mixing up two related but different attributes: time windows and route duration. Duration is the time elapsed since the beginning of a route, and depends on the starting time as you mention. The time windows, on the other hand, are absolute and do not depend on the starting times of the routes.

In a classical VRPTW setting, only time windows are present. Route duration constraints are additional attributes commonly found in periodic or multitrip problems.

Improve this answer
$\endgroup$
7
  • $\begingroup$ can't you model route duration with a time window? $\endgroup$
    – Marco Lübbecke
    Commented Jul 3, 2019 at 11:38
  • 2
    $\begingroup$ They coincide if the routes start all at time zero. However, it is often possible to shift the starting times of routes forward in time and if that happens this equivalence is no longer valid. Am I missing something? $\endgroup$
    – Claudio Contardo
    Commented Jul 3, 2019 at 11:43
  • 1
    $\begingroup$ thanks, that settles it $\endgroup$
    – Marco Lübbecke
    Commented Jul 3, 2019 at 12:09
  • 1
    $\begingroup$ I've always interpreted it the same way as Claudio does: those numbers depend on the start of the planning window, not the start of the route. Obviously, the other way (= from start of route) is far more realistic, with a typical technician having 8 hours to complete his/her route. Have I misinterpreted that all this time? $\endgroup$
    – Geoffrey De Smet
    Commented Jul 3, 2019 at 13:41
  • 1
    $\begingroup$ Dear all, thank you for your feedback. When looking at the problem description found at Sintef there is nothing about route duration, just end time window of the depot. To me, this sounds as Capacitated VRP-TW(VRP), if I am not mistaken. However, when I tried to re-produce some best-known solutions (found on aforementioned webpage), some solutions violate the end time window at the depot. And this seems to be related to solving different problem variant, than CVRP, namely VRP-TW with route durations. $\endgroup$
    – VeGh
    Commented Jul 4, 2019 at 11:20

Your Answer

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

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