Benchmarking context

Benchmarking this change is quite hard. I do have a few real-life examples that are challenging wrt priority scores and where we produce possibly sub-optimal solutions. On those, this PR tends to generally improve the priority score, the difference being more noticeable for small exploration factors. The instance from #623 is also drastically improved.

Other than that I've been trying to systematically produce custom benchmark instances to confirm the improvement and I found that it's actually quite hard to generate instances where v1.13.0 produces obvious sub-optimal priority scores (that's good news in a way!). What I ended up doing is to generate instances where the priority score is totally at odd with the usual cost criterion, because that's where our approach is more likely to fail reaching good priority scores.

Custom instances

The process is as follow:

1. generate random instances with vehicle TW and no job priorities, making sure we don't have enough vehicles to handle everything;
2. solve each instance to spot unassigned jobs (those are the "more expensive ones");
3. go back to the initial instance and set a "priority": 100 value to a random fraction (1%, 2%, 4%, 10%, 20%, 40%, 60%) of those unassigned jobs to generate new instances with priorities.

This way we make sure the "though jobs" get a high priority which makes it especially challenging to reach high priority scores on those instances. In other word, a solving approach only aiming at cost could produce arbitrarily bad solutions wrt priority scores (that is actually what happens when only looking at our heuristic solutions).

Results

Overview

With this PR, the priority scores are significantly improved over v1.13.0 on a number of such instances when running with -x 0. It also came as a surprise that the number of unassigned jobs is usually vastly reduced, even in some situations where the priority score is even.

More precisely, on those 154 instances the rate of solutions reaching the upper bound for priority score goes from 52.0% for v1.13.0 to 79.2% for 33486e1.

Rate of solutions with strict improvement with PR by criteria:

It's notable that whenever assigned jobs and cost are not improved, it is in most situations because the priority score has increased, resulting in a "more constrained" solution. This makes sense with our criterion ordering.

Example

Here is an example with only 1 job out of 200 with priority 100 (coordinates [2.21221, 48.30892]).

Solution with v1.13.0 (priority 100, 107 unassigned jobs and cost of 149235)

Solution with PR (priority 100, 87 unassigned jobs and cost of 141601)

In the PR solution, one route goes further enough to reach that job but the other routes make much more sense, so we're able to assign 20 jobs more within the vehicles TW with an even lower cost.

My interpretation is that the new operator from this PR made it possible to change a good heuristic solution to include the priority job. So we reach a very good solution both cost-wise and in term of assigned jobs, with the optimal priority score. On the other hand with v1.13.0, only one of the heuristic solutions favouring reaching out to far-away jobs was (accidentally) better on priority and thus ended up outputted after the local search. But in that case, the local search did not manage to improve the cost that much, and make room to assign more jobs.

Impact of exploration level

The impact of the operator is somewhat lower when using -x 5, because having a high exploration level is another complementary mean to favor including jobs with priority.

With -x 5, the rate of solutions reaching the upper bound for priority is already 76.6% for v1.13.0 and goes up to 81.8% for 33486e1.

Rate of solutions with strict improvement with PR by criteria:

So even if the net difference on priority is less significant, we still see an interesting improvement on other criteria. Also notably solutions that are worse in cost are usually better on assigned jobs, and solutions that are worse on assigned jobs (and/or cost) are usually better on priority, which again makes sense with our optimization criterion ordering.