Question regarding pd_shift

[krypt-n]

Hi, this is not a real issue, just a thing I noticed in the code.

I'm currently looking into the running time of instances that use PDShift and compute_best_insertion_pd heavily.
Both contain an algorithm to find a cheap insertion of a shipment into a route. I merged the two algorithms but noticed that this changes the resulting routes.
After some debugging I noticed that the only relevant difference between the algorithm in pd_shift.cpp and the one in local_search.cpp is the range of the possible pickup locations. My question thus is:

Is it intended that PDShift does not consider the end of a route for the pickup? Or am I missing something?

This change is not a clear improvement in solution quality in the benchmarks I checked, some solutions improve, some get worse. This is why I am hesitant to apply this change.

diff --git a/src/problems/vrptw/operators/pd_shift.cpp b/src/problems/vrptw/operators/pd_shift.cpp
index 39f2a7b..0dcefd2 100644
--- a/src/problems/vrptw/operators/pd_shift.cpp
+++ b/src/problems/vrptw/operators/pd_shift.cpp
@@ -80,7 +80,7 @@ void PDShift::compute_gain() {
       target.is_valid_addition_for_tw(_input, s_route[_s_d_rank], t_d_rank);
   }

-  for (unsigned t_p_rank = 0; t_p_rank < t_route.size(); ++t_p_rank) {
+  for (unsigned t_p_rank = 0; t_p_rank <= t_route.size(); ++t_p_rank) {
     Gain t_p_gain = -utils::addition_cost(_input,
                                           m,
                                           s_route[_s_p_rank],

[jcoupey]

Is it intended that PDShift does not consider the end of a route for the pickup? Or am I missing something?

No, I don't recall any specific need for not considering the last position here and I don't see why we shouldn't do it in the same way as in compute_best_insertion_pd. This is a mismatch that results in not considering relocating a shipment after the last tasks in the target route.

This change is not a clear improvement in solution quality in the benchmarks I checked, some solutions improve, some get worse.

If the solutions change, it's because such a move, when allowed, is picked at some point and changes the sequences of solution we go through during local search. This does not mean the last solution down the line will necessarily be better, just that we change our exploration of the solution space. Yet, the logic is to have an exhaustive lookup of options before applying changes so we should not restrict in this way.

Aside from strict solution quality improvement, it means that the current code could potentially return an "obvious sub-optimal" solution where this obvious move could be easily spotted by end users and has not been applied.

Maybe we should fix this as such to highlight the change rather than blending the fix in a different refactoring?

[jcoupey]

@krypt-n you PR did target vrptw::PDShift, I assume this is because you're playing with the usual pickup-and-delivery benchmarks (Li&Lim). But it looks like we should apply the same change in cvrp::PDShift::compute_gain? That would apply to PD instances without time windows.