I quickly tried to see the difference between master and this PR on the Solomon instances but computing times changes seem meaningless. I'll probably try some more tests on bigger instances.

Happy to have some feedback if anyone has a clue on the "theoretical" impact of such a change.

I'd suspect that this regresses performance for instances that do a lot of is_valid_addition_for_tw checks (instances with a lot of unassigned jobs?) based on my experience with the performance of vroom. The reason is that the new code involves a memory allocation and the old code does not, but this effect might be negligible if there are no instances where is_valid_addition_for_tw is hot.

If it turns out to be a performance regression, you could try replacing the std::vector with a std::array of fixed size 1 to avoid a potential memory allocation.

I'd say is_valid_addition_for_tw is hot for pretty much any instance with jobs and time windows because it's called every single time we want to check the validity of a potential insertion that works for the rest of the constraints (capacity are checked first). Good point about situations with a lot of unassigned jobs which may stress that even more.

I'm not really concerned about turning add into a replace call as this happens only when we actually update a solution, a rare occasion compared to the number of validity checks performed overall.

Instances with only shipments are not affected as they always use replace calls anyway.

This kind of change is always a pain to benchmark as variations in computing times are sometimes higher across several runs than across different versions. What I did to try and smooth things was:

• Use big random instances (1000 jobs) in two settings (with or without unassigned jobs)
• Solve using different exploration levels
• Run on the same instance 5 times and discard the fastest and the slowest runs
• Compare total solving time

The initial changes show a +2.5% increase of the overall solving time, then switching to arrays brings that down to +1.6%. I think we can definitely live with that tiny increase for the sake of simplifying the code and its downstream maintenance.

Another thing I meant to try was to move the implementation of the changed function to the header file. @krypt-n do you reckon that could improve things a bit? Could not test this actually since without further change to the build I hit a linking problem with undefined references to the range versions from other compilation units.

I do think it could, but I find it hard to measure. The benchmark VRPTW instances don't call is_valid_addition_for_tw that often in comparison to other functions. So I suppose it's not that important to optimize here

Worth trying anyway because we're now simply redirecting to another function so the implementation is at most a couple lines. And the same also applies to is_valid_removal and remove.

I just tried that in the last commit and I'm a bit confused about why there are missing references at linking stage (see previous CI fail).

There are some instantiations of the template functions missing in the cpp file. These should be enough:

diff --git a/src/structures/vroom/tw_route.cpp b/src/structures/vroom/tw_route.cpp
index 55717c5..8c22038 100644
--- a/src/structures/vroom/tw_route.cpp
+++ b/src/structures/vroom/tw_route.cpp
@@ -1044,6 +1044,35 @@ template bool TWRoute::is_valid_addition_for_tw(
   const Index first_rank,
   const Index last_rank) const;

+template bool
+TWRoute::is_valid_addition_for_tw(const Input& input,
+                                  const std::array<Index, 1>::iterator first_job,
+                                  const std::array<Index, 1>::iterator last_job,
+                                  const Index first_rank,
+                                  const Index last_rank) const;
+
+template bool TWRoute::is_valid_addition_for_tw(
+  const Input& input,
+  const std::array<Index, 1>::const_iterator first_job,
+  const std::array<Index, 1>::const_iterator last_job,
+  const Index first_rank,
+  const Index last_rank) const;
+
+template bool TWRoute::is_valid_addition_for_tw(
+  const Input& input,
+  const std::vector<Index>::const_iterator first_job,
+  const std::vector<Index>::const_iterator last_job,
+  const Index first_rank,
+  const Index last_rank) const;
+
+
+template void
+TWRoute::replace(const Input& input,
+                 const std::array<Index, 1>::const_iterator first_job,
+                 const std::array<Index, 1>::const_iterator last_job,
+                 const Index first_rank,
+                 const Index last_rank);
+

some instantiations of the template functions missing

Argh yes, I always seem to get fooled that way as those were not necessary as long as the implementation stayed in the .cpp file.

The good news is that it seems we're on something very interesting: the computing time increase now turns in a significant reduction (-17.4% on my small empirical tests). It looks like moving the various implementations to the header file largely overcomes the overhead of creating a temporary array and doing an extra replace call.

I'll benchmark the current state of the PR with the usual VRPTW benchmarks (though PDPTW are likely "affected" too) and report.

the computing time increase now turns in a significant reduction

That was too good to be true, especially given that not a lot of code is made available to other compilation units. This observation seems to be only related to the system load while running on a couple instances on my local laptop and I can't actually reproduce that difference any more...

I did run tests on my usual benchmarking machine and it comes down to:

1. All solutions are identical (as expected).
2. Computing times on the usual VRPTW and PDPTW with master and this PR are on par across all exploration levels.
3. Tests on a (slightly more representative) set of random instances with a high number of unassigned jobs do show a small increase in computing times. Changes vary depending on number/rate of unassigned jobs and exploration levels, yet this is not significant enough to renounce simplifying the code and further maintenance.

The benchmark VRPTW instances don't call is_valid_addition_for_tw that often in comparison to other functions

I'm still curious about this as it sounds counter-intuitive. My guess would be that this happens because we only perform TW checks as a last resort after checking all other constraints.

Maybe this also means there are some other low hanging fruits in term of code optimization.