There is a subtlety I didn't see at first in the adjustments required to update is_valid_addition_for_tw. The point of this function is to check validity while trying to replace an existing range of jobs with a new inserted range. We need to add a way to maintain the current route load during this process to check against the new break constraint.

The new load before insertion should be 1 - 2 + 3 with:

1. previous route load at that point;
2. total of job deliveries for replaced range (stuff loaded at startup that is not in the car any more after removing the old jobs);
3. total of job deliveries for insertion range (stuff that will have to be loaded at startup after inserting the new jobs).

Value 1 is already stored by the RawRoute object, while 2 can be computed in constant time using the delivery_in_range member function. Now in the is_valid_addition_for_tw context, the naive way to get 3 would be to go through the insertion range and sum the delivery values. But this would incur an expensive lookup (linear in the size of the insertion range) inside a hot spot.

The best way to avoid this I can think of is to provide this value as an additional argument to is_valid_addition_for_tw, since the call sites have better ways (read constant time) to get it. For example in local search operators, that value is already used for capacity checks in the cvrp version of the operator so it could be stored as a member for re-use in the vrptw context, or directly recomputed.

This will add a bit of boilerplate to the is_valid_addition_for_tw calls but I'm afraid there's no way around it.

We'll also have to apply to TWRoute::replace the same changes as the ones already applied to TWRoute::is_valid_addition_to_tw, since both will have to pass the current load to order_choice in a consistent way. I updated the task list accordingly.

There is yet another thing I under-estimated here: the changes already applied to is_valid_addition_to_tw and replace mean that we should not break the max_load constraint for a break taking place during the replaced/inserted range (we'll either place the break at a convenient place or decide that the move is invalid). This is necessary but not sufficient in general: replacing a range with another that has more job deliveries would impact the whole vehicle load from route start up to the beginning of the replaced range. Symmetrically, if the inserted range has more jobs pickups that the replaced range, load is increased for the whole end of the route. In short we need more checks for not breaking max_load for breaks before and after the insertion range.
In order to avoid looping though all breaks for those checks, we could maintain forward/backward min margins for breaks based on actual route load and max_load values.

This limitation only applies for instances with jobs, so normally the current state of this PR should be already working for shipment-only instances (ping @fbaierl if you want to give it a spin).

EDIT: I updated the task list to reflect this.

Hello @jcoupey, not sure if I understand this correctly, but will the current solution only work if there are absolutely no job elements inside the VROOM query at all?

We actually use jobs (always with empty pickup and delivery values) to force the vehicles to maintain certain previously calculated routes (as described here).

I have added an example to the original issue with those empty jobs.

I'm currently running some testing and I've spotted a few problematic situations along the way, such as P&D scenarios where we fail to insert shipments before or between the breaks, probably related to the heuristic decisions in order_choice. Not quite clear to me yet but I think this is due to a pre-existing bias, in which case this would already be affecting the current solving approach even before this PR. I'll investigate further and open a separate issue if necessary.

I think the adjustments to is_valid_addition_for_tw and order_choice are now OK to handle max_load break values. Our new problem is that there are some places in the existing codebase where the checks should only be about timing since the max_load part does not make sense.

One example is when we test a single pickup addition or delivery addition in insertion_search.h. Of course inserting only a pickup or only a delivery does not make sense and never happens, but testing additions in isolations for TW is a great way to short-circuit a lot of loop iterations in case of time incompatibility. But now with the max_load checks added, any "single pickup" insertion will be seen as impossible before any break with a max_load: [0] since the load is never delivered, even though P -> D -> Break would not be a problem. The same applies the other way around for deliveries, resulting in obviously wrong solutions with a lot of unassigned jobs in situations with multiple breaks (despite vehicle idle time).

So what I tried in the previous commits is to add a flag as parameter to is_valid_addition and order_choice to switch on or off the max_load checks. I don't find the solution especially elegant and it makes both functions a bit more complex overall. But at least now we can pick the right behavior based on what is really required in a given context.

A benefit of this approach is that we could try storing at vehicle level whether the max_load checks are required at all, and override that flag dynamically. The idea is that we could then reduce the overhead of the changes in this PR for other "normal" instances without max_load constraints. This overhead is mostly related to passing amount information to the two functions and maintaining current route load while processing route portions for the validity checks.