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

Priority-improving move selection only accounts for priority #1212

Closed
jcoupey opened this issue Jan 29, 2025 · 1 comment
Closed

Priority-improving move selection only accounts for priority #1212

jcoupey opened this issue Jan 29, 2025 · 1 comment

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Jan 29, 2025

When picking the best option in local search, we first lookup moves that improve priority score:

for (unsigned s_v = 0; s_v < _nb_vehicles; ++s_v) {
if (best_priorities[s_v] > best_priority) {
best_priority = best_priorities[s_v];
best_gain = best_gains[s_v][s_v];
best_source = s_v;
best_target = s_v;
}
}

The problem here is that there is no account for gain (or solution deterioration), so if multiple moves yield the same priority score gain, the first one will be picked, possibly shadowing another that is better in term of cost.

Also we used to only have UnassignedExchange being able to change the priority score, leaving the number of assigned tasks identical. Now PriorityReplace is able to both improve priority score while deteriorating the number of assigned tasks. We should also be able to pick the least task removal for equal priority score improvements.

@jcoupey jcoupey added this to the v1.15.0 milestone Jan 29, 2025
@jcoupey jcoupey mentioned this issue Jan 29, 2025
6 tasks
@jcoupey
Copy link
Collaborator Author

jcoupey commented Jan 29, 2025

Fixed along with the changes in #1210

@jcoupey jcoupey closed this as completed Jan 29, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant