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

Greedier solution recreation process #1155

Closed
jcoupey opened this issue Sep 13, 2024 · 0 comments · Fixed by #1156
Closed

Greedier solution recreation process #1155

jcoupey opened this issue Sep 13, 2024 · 0 comments · Fixed by #1156

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Sep 13, 2024

The try_job_addition worst-case complexity is $O(U^2\times R)$ where $U$ is the number of unassigned jobs we try to re-insert, and $R$ is the number of candidate routes for re-insertion. This is not a big deal in typical re-insertion tries after applying a local search operator because then $R\le 2$ and $U$ is usually small.

On the other hand, when we ruin a bigger part of the solution and want a full recreation, then $R$ is the number of existing vehicles in the current solution and $U$ can be much higher. So the time spent doing the recreation can start to be significant, especially in the light of #874 where we'll probably tend to remove more jobs than we currently do.

We could have a pre-established insertion order for unassigned jobs, based say on priority, capacity, TW narrowness, closeness to some vehicle or similar. In which case the above complexity would drop to $O(U\times R)$.

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