Flipped order inside vehicle array impacts result quality (problem instance included).

[PattyDePuh]

Greetings!

*TLDR:

• Given a problem instance with 46 jobs and 10 vehicles, time windows and skills.
• latest build of VROOM (alias. "1.12.0-dev" from 2nd of february) is not capable to assign all jobs to vehicles - compared to v1.8.
• but even leaves some vehicles unused.
• However, an acceptable solution is found by including an additional job, which might contradict VROOM's mantra.*
• Both "latest" and v1.8 build were not capable to reproduce the acceptable solution, if vehcle order gets flipped.

Description

Given the following problem instance from the zip-folder:
4_instances_on_v8_and_latest.zip

• "46_jobs.json", a problem instance with 46 jobs and 10 vehicles, time windows and skills.
  And its alterations:
• "47_jobs.json", an additional job is added.
  And the same instaces as above, but order of vehicles inside the array is flipped:
• 46_jobs_flipped.json
• 47_jobs_flipped.json
  For all given 4 instances, there are VROOM outputs from version 1.8 and "latest".
• 46_jobs_result_v8.json
• 46_jobs_result_latest.json
• etc.

In the scenario of those problem instances, a solution is considered "good",
if all jobs are getting assigned - observeable by the "unassigned" key inside the result JSON.
The overall cost optimization is not relevant.

The three phenomena occurring:

A) Worse solution with latest build.

On instance "46_jobs.json"
we find a good solution with VROOM v1.8 - using 9 from 10 available vehicles -
while the "latest" build is only capable to assign all jobs but one.

B) Adding one more jobs results in a good solution

On instance "47_jobs.json"
both vroom versions are capable to find a good solution - both using only 9 from 10 available vehicles.
It shall be mentioned, that the added job (id:0) could be served by the unused vehicle.
Considering the "bad" solution from "46_jobs.json", this is quite troubling as logically it's hard to explain to anyone that a more complicated instance achieves a good result but a less complicated instance doesn't.

C) Changing the vehicle order

If changing the vehicle order - as in "46_jobs_flipped.json" and "47_jobs_flipped.json" respectively -
none VROOM version is capable to reproduce the "good" solution.

Thoughts

While problem C is problematic for consistency and reproduction purposes/debugging,
it is to some degree explainable: Input different - output different.
Problem A and B however are troubling.

Questions

Would you consider these behaviours as acceptable or can this already be considered as bug?
I get that I could use an existing solution as input for a following optimization, but that is hard to decide in advance when gradually adding more jobs as you don't know in advance when you should use an existing solution or rather leave VROOM more freedom.

[krypt-n]

Hi, thank you for you bug report. I can reproduce the problems exactly as you describe them.

I looked a bit into Problem A and identified commit 575d389 as the first vroom version where it occurs.
I.e. vroom at 88d118d finds a solution with 0 unassigned jobs for 46_jobs.json, but vroom at 575d389 finds a solution with 1 unassigned job.
Perhaps @jcoupey has some insight into why 575d389 leads vroom into a quite bad local optimum

[krypt-n]

Fwiw, I managed to reproduce problem A with a somewhat smaller instance:
46_jobs.txt

[jcoupey]

First, thanks @PattyDePuh for sharing a detailed descriptions and instances, it makes it much easier to look at!

I think it all comes down to the solving path being changed across various inputs and vroom versions: the heuristic solutions and/or moves applied during the local search lead to a different local minimum. I don't think 575d389 is specifically to blame here since the output at 88d118d already is quite different from the v1.8 solution. It's just largely more noticeable when the number of unassigned jobs goes from 0 to 1, instead of having a tiny variation in overall cost and still all jobs assigned.

We're always ending up in a local minimum, which is fine as long as users can't easily come up with a better solution. Here the new master is not generally worse than v1.8 (it's probably actually much better on average), it's simply that the new search path triggers this problem that did not show up before. There are probably ways to trigger that exact same problem with v1.8 using other similar instances.

Now on why this happens, it's in a way quite similar to what we experienced with priorities in #319. I think this is related to the fact that in instance 46_jobs.json, the unassigned job can only be handled by a single vehicle. During the search this vehicles' route gets packed with other jobs for cost-based reasons so the remaining job never gets a chance to be added. Indeed there is no incentive in the search to force including a job based on strong skills constraints. And none of the local search moves we have are able to undo that deadlock. The problem disappears when removing the 13 skill to the unassigned job, or when adding the 13 skill to other vehicles.

Regarding the B and C points: any change applied to the input is bound to change the search path and it so happens that the ones you tried lead to one more assigned job. That's just a better local minimum, though I definitely don't want to have to explain situation B to a client. ;-)

[jcoupey]

Easiest way to fix this I can think of off the top of my head would be to somehow order vehicles based on the number of jobs they can actually perform (including skills filtering). This would have the additional advantage of removing the vehicles shuffling side-effect from situation C above.

1. For the homogeneous case, this could happen here though it would probably require to store the number of compatible jobs at vehicle level from Input::set_*_compatibility;
2. For the heterogeneous case (in which falls the 46_jobs.json example), it looks like the current way we sort based on the number of compatible jobs is biased since the values we rely on (computed from get_jobs_vehicles_costs) do not account for compatibility.

[jcoupey]

Quick update on the numbered ideas from previous comment.

1. Is already a thing since the max_tasks based sorting does include compatibility as of Derive implicit constraints from input #648.
2. I ticketed this idea in Account for vehicle/job compatibility in Input::set_jobs_vehicles_evals #982

I think both are good to have overall regardless of the exact effect on the particular instances discussed here.