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.

$\endgroup$
  • 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 Jul 3 '19 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 Jul 3 '19 at 13:39
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$
  • $\begingroup$ can't you model route duration with a time window? $\endgroup$ – Marco Lübbecke Jul 3 '19 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 Jul 3 '19 at 11:43
  • 1
    $\begingroup$ thanks, that settles it $\endgroup$ – Marco Lübbecke Jul 3 '19 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 Jul 3 '19 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 Jul 4 '19 at 11:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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