search

wouterkool / attention-learn-to-route

Attention based model for learning to solve different routing problems
MIT License
1.04k stars 337 forks source link

VRP without demand/capacity #49

Open tonydavis629 opened 2 years ago

tonydavis629 commented 2 years ago

Hello, I'm trying to implement this work to solve a VRP routing problem in my research, but I don't have the demand/capacity requirement. Is there a simple way I could remove this input to have just a standard VRP solver?

wouterkool commented 2 years ago

Hi! You could remove it from the code or you could simply set the demand to 0 for all customers (for which I suggest to retrain the model). However, if you don't have a capacity requirement, the shortest solution is to use a single vehicle to serve all customers, which is, in fact, the TSP problem, so it's better to use that version instead. If you have some other requirements (e.g. a maximum route length) these are currently not supported in this repository.

tonydavis629 commented 2 years ago

Wow thank you for the quick response. Yes I considered setting demand to 0, thank you for validating that idea. Yes the maximum route length is the problem, so I'll have to figure that one out. Thanks!

wouterkool commented 2 years ago

It should not be difficult to add it, have a look at the orienteering problem which also has a maximum length constraint (but only a single route). You should change the mask representing the feasible actions, such that an action is only feasible if it still allows to return to the depot within the maximum route length and (optionally) add a feature to the context node giving the current or remaining available route length. Good luck!

tonydavis629 commented 2 years ago

I'm having a little trouble implementing your suggestion to mask the infeasible actions that are greater than the maximum route length. I am not exactly sure how to pull the remaining lengths from each route in the stateCVRP object. I tried setting the demand/capacity to a multiple of the VRP size, but it only seems to work maybe half of the time to have the routes evenly distributed, sometimes the model outputs 1 node for 1 route for dozens of routes.

Would it maybe be simpler if I could just specify the number of vehicles explicitly? Can you point me in that direction?