Number of available vehicles?

[zvadaadam]

Hello 👋,

I am wondering if the model for VRP could be extended to take an input of a number of vehicles and the model outputs a desired number of routes? Any tips on how to approach it?

Btw, amazing work on the paper!

Many thanks 🙏

[wouterkool]

Hi!

I think you could try different things. Simplest would be to encode remaining number of vehicles as extra input to the context node (optionally normalized to 0-1 if this is always, e.g., between 1 an 10). Then simply stop as soon as all routes are constructed (this may leave some nodes unvisited).

To ensure/encourage feasibility (all nodes visited and capacities satisfied) you could at least check in each step if the remaining (unvisited) nodes can be served by the remaining number of vehicles (checking total demand vs total capacity), and mask out the depot if this is not the case. This may still lead to infeasibilities in some cases though but maybe you can penalize them during training.

As an alternative to adding the number of depots as context input feature, you could add multiple depots, then simply update the mask as soon as one is visited. I guess this may work slightly better, but is more difficult to implement.

In any case, constrained optimization is difficult and it may require some creativity to make it work. It may be useful to try and generate multiple samples or use beam search at test time.

You may find it interesting to try a variant of DPDP as well (code coming soon), which may be more suitable to accommodate such constraints as it considers a large number of solutions during construction.

[zvadaadam]

@wouterkool Thanks for the tips 🙏 Gonna try to play with it 🙂

It might be interesting to have an agent for each vehicle (multi-agent rl) 🤔 I'm trying to add support for CVRPTW with soft constraints and it seems to work but I keep getting an extra vehicle(s) with only 2 locations for various instance sizes. Maybe I could penalize the cases where the locations are not evenly distributed across vehicles.

Looking forward to try the DPDP approach, pretty creative 👍