Reverse skills

[dschnare]

Hello,

I'm wondering how I might efficiently model a reverse skill such that if a vehicle has refused to accept a shipment for work then the vehicle would have a "reverse skill" that would exclude the vehicle from being considered for said shipment.

The only way I can think of doing it with the current Vroom API is I would assign a skill to each shipment say shipment.pickup.id * 1000, and then assign all vehicles a skill for each shipment 1000, 1001, 1002,... Then when a vehicle has declined work, I would remove the associated skill from their skills array, but this explodes the vehicle's skills array the more shipments we have in the VRP problem.

[hklarner]

How about enumerating all sets of shipments that actually occur for vehicles in your problem and giving a skill to each set?

E.g. in a specific instance of your problem there might be vehicles that can do all shipments (assign skill 0), there might be vehicles that can do all shipments except shipment 3 and 17 (assign skill 1), and there might be vehicles that can do all except shipments 5, 6, 108 and 110 (assign skill 2). If that is it, you only need 3 skills for your problem and not 110 (or however many shipments you have).

Depending on how many sets of shipments actually occur, you might be lucky and have far less skills to assign than there are individual shipments in your problem.

[dschnare]

@hklarner Very interesting idea. So basically map sets of shipments that should not be assigned to vehicles to a number/id. The issue we have is that each vehicle could potentially refuse work for any shipment so in practice for us at least the sets of shipments that need to be "unpaired" is unique to each vehicle.

Our vehicles represent gig workers basically. and each worker can accept or refuse a shipment/task. That's what I'm trying to model with skills.

[hklarner]

Have you actually tried to assign a skill for each shipment and running vroom? Is it actually unacceptably slow? Because I could imagine it scales quite well.

Also, why do you introduce this peculiar value 1000?

[jcoupey]

Is it actually unacceptably slow?

There is no scaling problem with the solution described in the original post. Under the hood we basically store vehicle/job compatibility in a "matrix". Going through the actual skills arrays to decide compatibility is done only once to populate that data, then further access to compatibility information happens in constant time.

So setting a huge number of skills will have no impact on computing times. Sure it will be slightly longer to parse and will add some boilerplate to store vehicle/job matches, but that's totally negligible compared to the actual solving time.

[jcoupey]

The only problem of having huge skills arrays to model "all-but-one" or "all-but-a-few" situations is that it can bloat the payload files and trigger problems related to file sizes when sending them in POST requests.

I guess introducing some kind of "reverse" skill description could help with that. This being said it would not unlock new modeling options, just add some modeling syntactic sugar.