SwapStar speedup #1268
Description
The SwapStar operator is costly in term of computing time, taking a significant portion of the overall local search cost in various benchmarking results. I don't have a very clear view of the bottleneck here, but I once suspected it was allocation-based (see #657).
Another take at this is to reconsider the precomputing phase required for that operator. Typically for each route pair, we compute for all jobs in one route the top 3 insertion options in the other route. This is done only once per route pair, and the purpose is that having this information allows to reduce the complexity of the rest of the work. Now imagine we apply a modification to route R, then of course all top insertion options into that route have to be updated. But all top insertion options from remaining jobs in R to other (untouched) routes are still valid. Yet, they will be recomputed on the fly when reevaluating the best SwapStart options between R and any other route.
What we should try is: move this preprocessing from the current hot compute_best_swap_star_choice function to somewhere in SolutionState and trigger relevant updates from the usual local search modification contexts.