Unassigned job when using skills on small dataset

[steveharenberg]

I have a small example where I am getting an unassigned job when using skills, despite there being a simple solution.

input json

{
    "vehicles": [
        {
            "profile": "car",
            "id": 1,
            "start_index": 0,
            "end_index": 0,
            "capacity": [
                10
            ],
            "skills": [
                1,
                2,
                3,
                4,
                5,
                6,
                7,
                8
            ],
            "time_window": [
                0,
                1000
            ]
        },
        {
            "profile": "car",
            "id": 2,
            "start_index": 0,
            "end_index": 0,
            "skills": [
                4,
				5
            ],
            "capacity": [
                11
            ],
            "time_window": [
                0,
                1000
            ]
        },
        {
            "profile": "car",
            "id": 3,
            "start_index": 0,
            "end_index": 0,
            "skills": [
                1,
                2,
                3,
                4,
                5,
                6,
                7,
                8
            ],
            "capacity": [
                12
            ],
            "time_window": [
                0,
                1000
            ]
        }
    ],
    "jobs": [
        {
            "id": 1,
            "skills": [
                1
            ],
            "location_index": 1,
            "delivery": [
                2
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        },
        {
            "id": 2,
            "skills": [
                2
            ],
            "location_index": 2,
            "delivery": [
                5
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        },
        {
            "id": 3,
            "skills": [
                3
            ],
            "location_index": 3,
            "delivery": [
                1
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        },
        {
            "id": 4,
            "skills": [
                4
            ],
            "location_index": 4,
            "delivery": [
                6
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        },
        {
            "id": 5,
            "skills": [
                5
            ],
            "location_index": 5,
            "delivery": [
                4
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        },
        {
            "id": 6,
            "skills": [
                6
            ],
            "location_index": 6,
            "delivery": [
                9
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        },
        {
            "id": 7,
            "skills": [
                7
            ],
            "location_index": 7,
            "delivery": [
                1
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        },
        {
            "id": 8,
            "skills": [
                8
            ],
            "location_index": 8,
            "delivery": [
                2
            ],
            "time_windows": [
                [
                    0,
                    1000
                ]
            ]
        }
    ],
    "matrices": {
        "car": {
            "durations": [
                [
                    0,
                    70,
                    60,
                    0,
                    80,
                    30,
                    20,
                    40,
                    100
                ],
                [
                    70,
                    1080,
                    30,
                    40,
                    1080,
                    1080,
                    100,
                    1080,
                    1080
                ],
                [
                    60,
                    30,
                    1080,
                    20,
                    1080,
                    1080,
                    1080,
                    1080,
                    1080
                ],
                [
                    0,
                    40,
                    20,
                    1080,
                    1080,
                    70,
                    1080,
                    30,
                    1080
                ],
                [
                    80,
                    1080,
                    1080,
                    1080,
                    1080,
                    60,
                    1080,
                    120,
                    1080
                ],
                [
                    30,
                    1080,
                    1080,
                    70,
                    60,
                    1080,
                    1080,
                    90,
                    1080
                ],
                [
                    20,
                    100,
                    1080,
                    1080,
                    1080,
                    1080,
                    1080,
                    70,
                    10
                ],
                [
                    40,
                    1080,
                    1080,
                    30,
                    120,
                    90,
                    70,
                    1080,
                    1080
                ],
                [
                    100,
                    1080,
                    1080,
                    1080,
                    1080,
                    1080,
                    10,
                    1080,
                    1080
                ]
            ],
            "costs": [
                [
                    1080,
                    70,
                    60,
                    1080,
                    80,
                    30,
                    20,
                    40,
                    100
                ],
                [
                    70,
                    1080,
                    30,
                    40,
                    1080,
                    1080,
                    100,
                    1080,
                    1080
                ],
                [
                    60,
                    30,
                    1080,
                    20,
                    1080,
                    1080,
                    1080,
                    1080,
                    1080
                ],
                [
                    1080,
                    40,
                    20,
                    1080,
                    1080,
                    70,
                    1080,
                    30,
                    1080
                ],
                [
                    80,
                    1080,
                    1080,
                    1080,
                    1080,
                    60,
                    1080,
                    120,
                    1080
                ],
                [
                    30,
                    1080,
                    1080,
                    70,
                    60,
                    1080,
                    1080,
                    90,
                    1080
                ],
                [
                    20,
                    100,
                    1080,
                    1080,
                    1080,
                    1080,
                    1080,
                    70,
                    10
                ],
                [
                    40,
                    1080,
                    1080,
                    30,
                    120,
                    90,
                    70,
                    1080,
                    1080
                ],
                [
                    100,
                    1080,
                    1080,
                    1080,
                    1080,
                    1080,
                    10,
                    1080,
                    1080
                ]
            ]
        }
    }
}

vehicle 1 has capacity 10
vehicle 2 has capacity 11
vehicle 3 has capacity 12

If you run without skills (vehicles can service all jobs), you can solve the problem with 3 routes:
vehicle 1: 5, 4 (uses 9 of 10 capacity)
vehicle 2: 6, 8 (uses 11 of 11 capacity)
vehicle 3: 1, 2, 3, 7 (uses 9 of 12 capacity)

If we make it such that vehicle 2 can only service jobs 4 and 5, then a valid solution is simply:
vehicle 1: 1, 2, 3, 7 (uses 9 of 10 capacity)
vehicle 2: 5, 4 (uses 9 of 11 capacity)
vehicle 3: 6, 8 (uses 11 of 12 capacity)

However, the solution I get from vroom (on the input json given above) is:
vehicle 1: 6 (uses 9 of 10 capacity)
vehicle 2: 4, 5 (uses 9 of 11 capacity)
vehicle 3: 7, 3, 2, 1 (uses 9 of 12 capacity)
with job 8 being unassigned.

Interestingly, if I remove the cost matrix and only use the duration matrix it finds the solution with no unassigned

I am using vroom 1.12 and simply running:

vroom -i input.json

Is this just a case of bad luck with the heuristics?

[jcoupey]

Thanks for the comprehensive report. First I can confirm all statements, and especially that the solution you detail assigning all jobs is valid.

Interestingly, if I remove the cost matrix and only use the duration matrix it finds the solution with no unassigned

That's just because different costs lead to a different search paths, in this case not triggering the initial problem any more.

Is this just a case of bad luck with the heuristics?

Kind of. What happens here is that vehicles 1 and 3 are identical regarding skills (can do any job) but the 6 -> 8 route only fits in vehicle 3 because of capacity. Now we sort vehicles by decreasing capacity when building initial routes because it's usually better to start filling up "bigger" vehicles. So vehicle 3 is filled first and if it gets 7, 3, 2, 1, then vehicle 1 is stuck with only 6 as 8 won't fit and the local search won't change that. You may wonder why 6 and/or 8 are not assigned to vehicle 3 in the first place: when vehicle 3 gets an initial route like 7, 6, 8, then vehicle 1 is next in line because it can handle more tasks than 2 (see full check in above link), so vehicle 1 gets 5, 4 and route for vehicle 2 is empty so the solution is even worse with only 5 jobs assigned.

This is really related to the order in which vehicles are initially filled and if you reverse the capacity comparison in the sort mentioned above, then you get a solution without unassigned jobs. In this respect, it's a bit similar to #671, though in this case #671 (comment) would probably not solve the problem.

[steveharenberg]

Ok, thanks for looking into it!

[do-me]

I'd just like to confirm this general behavior in all VROOM versions from 1.8 - 1.13. It happens very frequently that vehicles with skills are filled up with non-skilled jobs and as a result there are jobs with skills left unassigned.

However, and strangely, it is almost always precisely 1 job left over which seems a little odd. If it was a varying number it would be in line with Julien's answer above but in this way, might the reason be somewhere else? 

If you need some more examples, I can collect them in the next weeks but they are all pretty similar to @steveharenberg 's example.

[jcoupey]

@do-me thanks for reporting. It's always good to have some examples, at least to get a consistent testing base for a potential fix. Also maybe worth looking at if you think you're not hitting the same kind of heuristic bias as above.

[do-me]

https://github.com/do-me/Test/blob/main/vroom-problem-336-jobs.json (couldn't attach the file in this comment)

Here is one of the instances where the described problem happens. Even though it's not a "small" instance anymore it's still apparent to the human observer, that the distribution of jobs is suboptimal in this case, and that an easy solution for all jobs could be found. Some notes/feedback:

• There is "enough of everything" in terms of vehicles, time, capacity etc. but due to the suboptimal distribution of non-skilled jobs to skilled vehicles some jobs remain unserved.
• A solution for this problem does exist - if you need it for debugging or similar we could provide it too.
• We tested different versions of VROOM for the attached problem instance and there is a notable difference between the solutions:
  • v1.8 & v1.11 yield the exact same result - 1 job unassigned but
  • v1.13 leaves even 3 jobs unassigned

It's worth noting that we tested v1.13 with large and small instances and from my experience for larger instances >2000 jobs, >50 vehicles it's usually way faster (4 times) and yields better results than earlier VROOM versions. For smaller instances however, sometimes v1.8/v1.11 in fact - like in this case - yield better results.

[jcoupey]

@do-me thanks for sharing! I can reproduce the 3 unassigned jobs with v1.13.

it's still apparent to the human observer [...] that an easy solution for all jobs could be found

Well since you stripped all locations, it rules out any geometric intuition. So it is not so trivial to see which routes to adjust in order to reshuffle and insert the unassigned jobs in a valid way.

A solution for this problem does exist - if you need it for debugging or similar we could provide it too.

That would be much appreciated! You can attach a solution file (just use another file format than json, for some reason GH does not allow it), or simply provide the list of ordered job ids associated with each vehicle id.

On a side note: your matrix looks heavily customized (lots of zero and identical rows), is there a reason for this? Asking since it may have an impact on the solving side.

[jcoupey]

Since #982, compatibility is taken into account in a way that will impact:

1. vehicle ordering within the heuristic process;
2. some of the job-inclusion decisions (based on heuristic regret values and job proximity count).

This seems enough to solve the problem reported here, running from current master:

$ vroom -i input.json | jq .summary.unassigned
0
$ vroom -i vroom-problem-336-jobs.json | jq .summary.unassigned
1

I'm not saying this kind of suboptimal result can't happen any more, just that it should be less likely. In any case, I'm closing this ticket as the behavior is now as expected for all reported instances.

[do-me]

Thanks a lot, we'll go ahead and come back here after testing!