Repeating job at same address served by same vehicle

[do-me]

As the title states, I was looking for an option / constraint to serve jobs at the same address / coordinates always by the same vehicle. In other words: I don't want two or more different jobs to be served by the same vehicle.

We sometimes have requests from clients who have keys (in fact one key only) that they can hand out in the beginning of a tour but they cannot pass them around.

I tried searching the docs with key words and even semantically (export the docs as pdf, copy all text to SemanticFinder, search with a query) but I couldn't find anything related.

Is this already possible?

[reinterpretcat]

Hi,
ideally, such jobs should be scheduled to the same vehicle and the same stop as it leads to more optimal solution in most of the cases, but it is not guaranteed (e.g. search quality or constraint violation).

You can use a group constraint on the job, which will force assignment to the same vehicle, but still it might be different stops:

group (optional): a group name. Jobs with the same groups are scheduled in the same tour or left unassigned.

https://reinterpretcat.github.io/vrp/concepts/pragmatic/problem/jobs.html

[do-me]

Thanks a lot for the quick answer!

This group constraint seems to be exactly what I was looking for, e.g. one could use a hash from the coordinates/address/address-ID as group name right? Or even go further and use e.g. raster cell IDs or hexagon IDs, to come a little closer to "spatial coherence" that many clients require for facilitated planning. It would be very interesting to run some experiments with this or even add a "spatial coherence" factor through automatic gridding.

What exactly do you mean by

but still it might be different stops

Do you mean if the jobs on one address have e.g. different timewindows etc.? That's expected, or did you mean something else?

By the way I am still totally mind-blown how many hyper-complex scenarios you can tackle with VRP, definitely awesome work! We don't have a testing environment yet, but as soon as we created it, I'll make sure to update you on our benchmarks etc..

[reinterpretcat]

Do you mean if the jobs on one address have e.g. different timewindows etc.? That's expected, or did you mean something else?

Yes, the same stop location can be visited more than once, especially, if jobs here have different time windows. However, there is no guarantee that it won't happen in some other cases (e.g. could happen when pickup&delivery jobs are mixed and vehicle has low capacity available)

Thanks for feedback! There are still many rooms for improvement. One important: vertical scalability of underlying algorithms. I observed, that with default configuration it work optimally on 12-16 CPUs, on higher amount it seems to start to use resources less efficiently. I did some work recently to improve that, but haven't really tested due to no access to more powerful hardware and some spare time limits.

[do-me]

Great - that's totally expected then if there are conflicting constraints.

Interesting, we have some machines with 64 CPUs (maybe even more) where we will run some tests soon (TM) . I'll let you know :)

[do-me]

As a short follow-up-question:
Above we were talking about multiple jobs at the same coordinates on the same tour through the group parameter. As far as I understand it would however not be possible to optimize a problem where you have multiple drivers (each doing multiple tours) and need to guarantee that all jobs at the same coordinates are served by the same driver (not tour) if I do not know yet which driver will be assigned to which job.

Or could I use the clustering algorithm here in some way?

It's for this scenario: #118

[reinterpretcat]

need to guarantee that all jobs at the same coordinates are served by the same driver (not tour) if I do not know yet which driver will be assigned to which job.

If you want these jobs to be served at the same stop visit, can you simply merge them into one job with accumulated demand and service time?

Or could I use the clustering algorithm here in some way?

Yes, it could theoretically, but there is no guarantee that all jobs will be clustered together (depends on their constraints).

[do-me]

Let me rephrase, I think I explained it poorly:

• Every address has multiple jobs with different, non-overlapping timewindows (planning multiple visits per address for a year, where a vehicle has 220 routes for each working day)
• Constraint: all jobs for one address must be served by the same driver over the year (not on the same route/day) for customer satisfaction

Is this still possible with group?

group (optional): a group name. Jobs with the same groups are scheduled in the same tour or left unassigned

I think I was struggling with the vocabulary: what exactly is meant by tour?
Is it one trip of one vehicle or if I defined a 220-days shift would it tour be defined as all 220 trips (assuming round trips)?

[reinterpretcat]

I guess you will have a separate tour for each day, so group won't work there as it restricts jobs with the same group for the same tour.

Theoretically, if you have a homogeneous fleet (all vehicles are the same), you can use skills and assign unique skill to a single vehicle and multiple same address jobs at different days.