The RouteSplit operator logic is to pick an existing route with at least two jobs, then choose the best possible splitting rank r of that route in begin_route (jobs up to r excluded) and end_route (jobs after r) in such a way that:

• there exists an empty vehicle begin_v for which begin_route is valid;
• there exists an empty vehicle end_v for which end_route is valid;
• the sum of the costs for both routes above is minimal.

Then the operator is applied if said sum of costs is lower than the initial (single route) cost.

While looking back at this for #941, I noticed that costs are recomputed for each route portion and vehicle candidate using utils::route_eval_for_vehicle here and here.

This function goes through alll route jobs to evaluate the costs, adding start/end cost along the way. On the other hand we have SolutionState::fwd_costs at hand that allows to evaluate any route chunk for any vehicle with a single difference (so in constant time). This would not include start/end costs that would have to be added manually.

Basically we can swap this evaluation that is linear in the route chunk size with a constant-time evaluation. The good part is that whenever this operator is used (i.e. if there are at least two empty vehicles available), this evaluation is performed for all routes, for all splitting ranks, and at most twice for all empty vehicle, so one could expect a significant impact.