Thanks for suggesting a fix! We indeed need to use the existing check for pending deliveries as part of the validity check in cvrp::PriorityReplace::is_valid. That will prevent crashes by avoiding picking an invalid move, but we actually need a broader improvement.

The point of the PriorityReplace operator is to try to replace as many tasks at the beginning (resp. end) of a route as possible by a single job, as soon as it improves the priority score. So adding the check will only discard invalid moves, but not account for other possible moves that are both valid and still improving in term of priority.

Illustration: say you have a route starting with P1->D1->P2->D2->P3->... and the first 5 tasks combined have a priority smaller than the one for a single job we could insert as replacement. Then simply adding a check for pending deliveries after P3 will rightly tell that cutting the route right after P3 is invalid. What we need instead is to try replacing a smaller part, e.g. the P1->D1->P2->D2 part with the single job, which is also a priority score improvement.

Thanks for clarifying, I assume that means the same PR should also add pending delivery checks to fwd_over and bwd_over evaluation in run_ls_step in addition to the current is_valid checks ?

Simply adding another check upstream will again only filter out unwanted moves, not help reaching out to other valid ones.

The current fwd_last_rank value as passed to the PriorityReplace ctor is the one we'd like to use if valid wrt pending deliveries, but if not we should reach out for the highest possible value below fwd_last_rank that is OK for the pending check (if any). So essentially I think once we found the current fwd_last_rank candidate we need to add a loop back with new checks. Same symmetric situation with bwd_first_rank.

This is starting to be a lot of boilerplate prior to calling the PriorityReplace ctor so I wonder if it wouldn't be better to move the responsibility of determining the ranks to the operator itself.

After Discussing with @jcoupey, a more comprehensive fix is in the works