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

Rework solution space jump #874

Open
jcoupey opened this issue Jan 18, 2023 · 2 comments
Open

Rework solution space jump #874

jcoupey opened this issue Jan 18, 2023 · 2 comments
Labels
Milestone

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Jan 18, 2023

Once we've reached a local minima, we try jumping around in the solution space by removing n jobs from each route, then re-inserting them heuristically, then rerunning a local search phase. Here n depends on the exploration level and current depth stage.

While the overall principle of ruining and re-creating a solution once in a while has proven its worth, the current implementation has major drawbacks.

  1. n is between 1 and 5. This was deemed enough at the time of implementation while testing on Solomon 100-jobs instances, but does not make sense on much bigger instances. The number of removed tasks should probably be proportional to the instance size.
  2. The current process removes exactly the same number of tasks in all routes. It would probably be much more efficient to remove "overall best candidates" (to be defined). This way some routes may stay virtually untouched while others could be mostly destroyed.
  3. The current way the best candidates per route are found is somehow expensive, especially when applied several times in a row.

Those statements bring more questions than answers, but I really feel we could make a better use of the search depth if we improve the current logic.

@jcoupey jcoupey added the core label Jan 18, 2023
@jcoupey
Copy link
Collaborator Author

jcoupey commented Jan 18, 2023

This idea is complementary to #508.

@jcoupey
Copy link
Collaborator Author

jcoupey commented Dec 19, 2024

I spent a lot of time testing several ruining schemes, to no avail so far. The ruining process relevance is very related to the recreation approach we use and currently the changes made for #1155 are taking over any attempt at changing the ruining part. In fact I've come to the conclusion that the new recreation process is much too greedy and changing it lost us the subtle search balance we previously had between exploration diversity and focus around good solutions.

More precisely: greedily (re)-inserting jobs while recreating does currently reach to much "wilder" solutions that are very different from the initial (pre-ruin) solutions. While this is good in term of search diversity, the impacts are huge: following local search steps are much longer because solutions are usually poorer after recreation and we loose some focus to find solutions "close" to the ones we ruin. As a result overall computing times are significantly higher (despite faster recreation) with globally decreasing solution quality.

I plan to revert the changes done for #1155 before getting back to see if we can improve ruining.

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

Successfully merging a pull request may close this issue.

1 participant