Guiding solution crossover

[N-Wouda]

Voigt et al. (2021) propose a new crossover operator. In short, a single individual from the population is used together with the best solution found so far. For every client $i$, if we have $i \rightarrow j$ in the best solution but $i \rightarrow k, j \ne k$ in the selected individual, then we place $i$ in a so-called removal pool. It could be seen as removing all "broken pairs" as in similar to the currently used diversity measure. When all pairs have been checked, a subset of clients from the removal pool are selected based on ALNS-type destroy operator criteria e.g., randomly, worst cost, etc. Those clients are removed from the individual and are then repaired again using greedy insert. Same idea in Voigt et al. (2022).

Originally posted by @leonlan in https://github.com/N-Wouda/Euro-NeurIPS-2022/discussions/54#discussioncomment-3401551

---

Can we implement this ourselves?

[N-Wouda]

@blablaslack if you have worked on this, can you give a brief update here?

[leonlan]

FYI: Broken Pairs Exchange can be extended to implement the proposed crossover by Voigt.

[leonlan]

I'll have a look at this later again

[leonlan]

I tested this without success. Using SREX/BPX crossovers with the best solution leads to early convergence. It might be interesting to test variations where we do crossovers with best if (some condition), but given the importance of the dynamic problem, I think it's not worth to research this further.