Prune local search moves based on TW constraints

[jcoupey]

This is somehow similar to #509 but whereas the latter focuses on costs this could be seen as the "time" counterpart.

Consider a job j with TW [a(j), b(j)] and the task t at rank i in route r with TW [a(t), b(t)]. The situation of disjoints TW can be summed up as:

• if b(j) < a(t) + service(t) + duration(t, j) then j cannot be inserted in r after rank i;
• if b(t) < a(j) + service(j) + duration(j, t) then j cannot be inserted in r before rank i + 1.

This provides an embarrassingly simple way to discard a lot of local search move lookups. Contrary to #509 this would not require any tuning, just avoiding some unnecessary work (creating operator object, computing potential gain then ending up deciding it's invalid anyway). We'd only need to maintain min/max insertion ranks for all jobs into any route, which would not be expensive since only computed upon route modifications.

Of course this would not bring much in situations with loose TW constraints, but I'd expect a significant impact on instances with a lot of disjoints TW, e.g. all the usual VRPTW/PDPTW benchmarks.

[jcoupey]

We can probably replace a(t) and b(t) by e(t) and l(t) respectively earliest and latest dates for t. This avoids to account for multiple TW for t and is also much more constraining as tasks can have no TW constraint in the first place but still have tight earliest/latest dates.

In order to account for multiple TW for j ([a_0(j), b_0(j)] ... [a_n(j), b_n(j)], we should use the latest deadline in the first condition and the earliest available date in the second:

• if b_n(j) < e(t) + service(t) + duration(t, j) then j cannot be inserted in r after rank i;
• if l(t) < a_0(j) + service(j) + duration(j, t) then j cannot be inserted in r before rank i + 1.

[jcoupey]

The bounds obtained using earliest and latest dates are stored in SolutionState::insertion_ranks_begin and SolutionState::insertion_ranks_end. It turns out they are indeed much more constraining than when using plain TW but also not always relevant because those bounds get quickly get invalidated depending on how the routes are modified by LS operators.

So I also defined SolutionState::weak_insertion_ranks_begin and SolutionState::weak_insertion_ranks_end ranges that are looser bounds based solely on TW (not earliest/latest date propagation), but whose validity is guaranteed in more situations.

Hence the LS operator filtering logic based on those different bounds is a bit tricky in the codebase.