Cut down validity checks time

[jcoupey]

A bit of profiling on current master (e.g. on solomon instances) shows that most of the local search time ­- that is most of the overall time - is spent in various operators validity checks, while computing potential gain for operators does not take that long. This makes sense as validity checks are usually performed prior to potential gain checks, so they are the front-facing way of discarding the many potential move we explore.

Here is a FlameGraph obtained with master at 42e901b on Solomon instance R203 : 42e901b_R203.svg. Interestingly we can see that vroom::vrptw::CrossExchange::is_valid and vroom::vrptw::MixedExchange::is_valid are taking a bigger part than other operators.

Now there are reasons why we should probably check for potential gain before validity most of the time:

1. In the light of Mixed pickups and deliveries #262 it appears that in some cases the complexity of the validity checks will increase, while computing potential gains will remain unchanged. So discarding operators based on gain should avoid costly checks altogether.
2. Because we lookup the best move between routes or inside a route, it means that most of the time we already have a good candidate handy (the best one so far). So as the search goes on discarding moves based on potential gains should occur increasingly often.

Now there is a reason why validity checks are currently performed before gain computing. In some cases validity for a move is dependant on orientation choices (think moving an edge to another route with the original orientation or reversed). In that case the actual gain depends on the result of the validity check. Nevertheless, we could start by computing and storing all potential gains based on orientation options, then use the max gain as a bound to decide whether it's worth checking for validity.

[jcoupey]

we could start by computing and storing all potential gains based on orientation options, then use the max gain as a bound to decide whether it's worth checking for validity

This works beyond my expectations! #262 (comment)