This issue is related to #971, which proposes to improve priority scores relying on initial heuristic solution changes. A dual approach would be to still let the local search do the priority heavy lifting after overcoming the limitations of the current move options we have.

Currently adding higher-priority jobs happen in try_job_additions whenever we (re)populate modified routes, or via the UnassignedExchange operator that allows to replace a job with another higher-priority job, even if at a more expensive cost. This is somehow limited and replacing just one job is clearly not enough in many situations.

What we could do instead is try replacing a whole portion of route with an unassigned job so that priority increases. The more jobs we remove, the more chance we have that the switch will be valid constraint-wise. To cut down the complexity of choosing which jobs to remove, we could limit to series of consecutive jobs at the beginning or end of a route. We could then easily decide where to "cut" the route based on any priority value by storing cumulative priority values in routes.