Pre-checks with nonzero timewarps

[wouterkool]

Pre-checks should be improved to work for nonzero timewarp routes as well. Assuming that all time warp gets resolved, there should be an improvement, otherwise we do not need to fully check the move as it can never be improving. This case is currently ignored.

[wouterkool]

Note that there are multiple levels at which we could do a precheck based on bounds. For example if we only want to defer fullly computing twBetween, we may even take into account the penalty for twBefore.twData and twAfter.timeWarp:

auto const tws = TWS::merge(p(U)->twBefore,
                            route->twBetween(posV, posV + M - 1),
                            route->twBetween(posU + N, posV - 1),
                            route->twBetween(posU, posU + N - 1),
                            n(endV)->twAfter);

deltaCost += penaltyManager.twPenalty(tws.totalTimeWarp());

Before this we can add a precheck

auto twPenaltyLB = penaltyManager.twPenalty(p(U)->twBefore.timeWarp + n(endV)->twAfter.timeWarp);
if (deltaCost + twPenaltyLB >= 0)
    return deltaCost + twPenaltyLB

Even more general, we may give an (optional) parameter maximumTimeWarp=-deltaCost to TWS::merge that can stop merging as soon as the timeWarp equals or exceeds this maximum. For this to be efficient, it would be nice if we could also do this inside twBetween (which in itself sequentially calls TWS::merge), which requires the twBetween to be evaluated 'lazily'. In my experience, this is more difficult to implement but may be beneficial to support other constraints which require 'left-to-right' evaluation of TWS.

[wouterkool]

I think there are also some situations where we can skip evaluating the TWS::merge since we can reason that the timewarp will be 0 (e.g. when removing a customer from a segment that has timewarp 0).

[N-Wouda]

Are there any prechecks we can add easily that would help a bit? We have done quite a bit since this issue was opened, so I am unsure if it's now moot (or not).

[wouterkool]

• I think the largest opportunity (also applying pre-checks with existing timewarp) has been implemented using the new cost evaluator functions.
• My previous comment is no longer valid as that assumed the duration segment is only computed for timewarp, whereas now we also have duration in the objective.

Therefore I think there are no options for 'large' and 'easy' improvements. What I think are still options:

• When inserting a client, we apply a 'best insertion' strategy. Here, instead of checking cost >= 0 as bounding strategy for each option we could check cost >= min(bestCost, 0) which may result in a bit more bounding potentially if bestCost < 0.
• We may compute a bound in each step when merging clients for a proposal so we can find early if a route's costs exceeds a certain threshold and stop fully computing the duration segment. However, this is a bit more complicated and unclear what to do for moves involving two routes.
• We could think of computing other bounds, e.g. for a segment between, we could compute a lower bound on the duration in O(1) as the sum of stop and travel durations (using prefix sum caches), which can be used to compute a bound on duration and (possibly) timewarp. We may then be able to skip the O(n) merge often. However, I think this is not generally worth it, except for long segments or if we would have time dependent travel times.

Not related to prechecks, but in general we could consider more (global?) caching ; I am curious how often we are re-evaluating the same subsequences or even complete proposed routes.

[N-Wouda]

• My previous comment is no longer valid as that assumed the duration segment is only computed for timewarp, whereas now we also have duration in the objective.

Not in general, no, but I think it's relevant often enough that we may want to do some investigation anyway. Our default is to only penalise distance in the objective (unit duration cost is zero by default), and that's also common in academia. We could make that faster by checking, for a proposal that only removes clients:

• Whether there was time warp on the original route;
• Whether there are duration-related costs;

And if not, the proposal can return a default DurationSegment when asked, since there are no costs related to duration.

I think this can be determined inside the proposal, without changing the CostEvaluator. It might need a template parameter to determine if the proposal is 'pure' remove (since that's something we know inside the operators and need to tell the proposal about). If it's not we can skip this entirely since then we need to compute the DurationSegment anyway.

This should particularly speed up the Exchange<N, 0> operators a bit, for what seems to be limited extra complexity.

[N-Wouda]

Let's revisit the easy parts of this for release 0.11.0.