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

Improve try_job_additions #392

Closed
jcoupey opened this issue Sep 11, 2020 · 2 comments · Fixed by #427
Closed

Improve try_job_additions #392

jcoupey opened this issue Sep 11, 2020 · 2 comments · Fixed by #427

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Sep 11, 2020

The LocalSearch::try_job_additions function is used to try adding unassigned jobs during the local search phase. It happens after any route change that may give room to new insertions, or after loosening the solution, which we do once in a while when reaching a local minima.

Setting aside a couple tricks (handling shipments, shortcuts based on priorities), the current implementation sketch is as follows:

  1. Go through all unassigned jobs, then through all routes, then all potential insertion ranks to find out the best overall (valid) option in term of cost increase.
  2. Apply the best option.
  3. Loop back to 1. while there are available insertion options.

We do need to compute the information of the best cost for all job/route pair with associated insertion rank, but we are basically running the whole process at step 1. for each new choice, while most of the previous information are still valid and could be stored. So when inserting job j in route for vehicle v, we should keep all data for other jobs/vehicles, but only recompute choices across remaining unassigned jobs and vehicle v.

Of course this would only make a small difference for instances with no unassigned jobs. However, the time spent in try_job_additions can amount to nearly 20% of the overall running time in a situation with many unassigned jobs, like in this flame graph.

@krypt-n
Copy link
Contributor

krypt-n commented Jan 5, 2021

I'd like to give this a try

@jcoupey
Copy link
Collaborator Author

jcoupey commented Jan 5, 2021

@krypt-n that would be great! I flagged this for the next release but did not have time to get started. We'll see how things go and whether to keep this for v1.9 or if it should be postponed.

Anyway feel free to ask if you need any additional pointers.

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.

2 participants