Skip to content
New issue

Have a question about this project? # for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “#”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? # to your account

Prune local search moves based on capacity constraints #709

Closed
jcoupey opened this issue May 11, 2022 · 0 comments · Fixed by #710
Closed

Prune local search moves based on capacity constraints #709

jcoupey opened this issue May 11, 2022 · 0 comments · Fixed by #710

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented May 11, 2022

We lack a mechanism for early detection of invalid local search moves based on capacity constraints. To be fair, I think this used to exist back in the days where we only had a amount key at job level and handling loads was just a matter of summing stuff up. I did not bother to hunt this in the git history, but if I recall correctly I removed this mechanism when introducing backhauls with the ability to have both delivery and pickup for jobs along the way.

The latter addition makes the load validity checks logic much more complex, but we could still rely on some bounds. For example in a relocate move, the delivery (resp. pickup) for inserted job added to the total job delivery (resp. pickup) for current route should not go over vehicle capacity.

Introducing this kind of check should be pretty straigthforward. Of course we would not be catching situations where both pickup and delivery sums are under the total capacity but the move is still invalid due to overload at some pickup happening before other deliveries. But in most situations my guess is we'd filter out a significant number of moves. And in delivery-only situations (in particular the usual academic benchmarks), this would behave exactly like the "sum-like" approach we used to have historically as described above.

# for free to join this conversation on GitHub. Already have an account? # to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant