Skip to content
New issue

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

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

Already on GitHub? Sign in to your account

Account for vehicle/job compatibility in Input::set_jobs_vehicles_evals #982

Closed
jcoupey opened this issue Sep 7, 2023 · 0 comments · Fixed by #983
Closed

Account for vehicle/job compatibility in Input::set_jobs_vehicles_evals #982

jcoupey opened this issue Sep 7, 2023 · 0 comments · Fixed by #983

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Sep 7, 2023

In set_jobs_vehicles_evals, we compute all costs for adding a given job in an empty route for all vehicles. Down the line this is used in the heuristics to compute insertion regrets.

The problem is that we define values even if a vehicle/job pair is not compatible which does not make sense. The result in the dynamic heuristic is that whenever a vehicle is the last one that can perform an unassigned job, we may still discard that choice because of a low regret value. This amounts to saying "I don't need to make the effort to insert this job at this point since another (still) empty vehicle can do it later for cheap". Except this "cheap" evaluation has no value if none of the remaining empty vehicles are compatible with that job and the job will remain unassigned.

This may be especially problematic in situations with lots of constraints (no surprise this idea came up in #671 (comment)).

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

Successfully merging a pull request may close this issue.

1 participant