Too much splitting of same-location deliveries in a route

[jcoupey]

Consider the (somewhat specific) scenario of a PDPTW where all deliveries are located at the same place. Based on the capacity restrictions, we expect a typical route to look like sequential tours across pickups with a bunch of deliveries in between. For example p - p - p - d - d - d - p -p - d -d.

The current solving approach does not do a good job on this kind of instances and I have at hand a few instances where we generate too many delivery sequences, i.e. a valid solution exists with less D sequences in routes and is cheaper but we don't reach it. Also in that case the solutions look a bit silly with delivery tasks only happening at the end of the route whereas they could be done in a previous delivery sequence.

[jcoupey]

Upon further examination, this appears to be related to a bias from the heuristic process. Consider a typical situation where a new tour across pickups needs to be started for capacity reasons. Say we go from:

p - p - p - d - d - d

Then all the following insertion options have the same cost due to deliveries being at the same location (inserted tasks are capitalized):

p - p - p - d - P - D - d -d
p - p - p - d - d - P - D - d
p - p - p - d - d - d - P - D

But because the criterion for updating the best insertion option is a strict improvement, the first option is picked over the last one, which is nonetheless obviously better for next steps. This creates a situation with pending pickups not delivered and we end with a lot of going back to the delivery site.

I've tried switching to a <= in the criterion to update the best insertion here:

https://github.com/VROOM-Project/vroom/blob/58f74115bd9dbc5f4d9f682f4466ba8051b096cd/src/algorithms/heuristics/heuristics.cpp#L346

In that case, we create a new pickup tour at the end in the above situation. The heuristic results are much better, enough so that the local search will fix the remaining hicups and we end up with the "right" number of delivery site visits.

Now this change is useful to understand the problem but is not a serious fix. If applied, a symmetric problem for instances with same-location pickups appears and the solution quality on those regresses.

[mhosman]

Hey @jcoupey thanks for your response in #621. Yes, it seems to be this same issue. I will prepare an input-output file to share my scenario. There's any workaround to fix this?

[jcoupey]

There's any workaround to fix this?

See code change suggestion in previous comment.