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

Add SWAP* operator #507

Closed
jcoupey opened this issue May 13, 2021 · 1 comment · Fixed by #580
Closed

Add SWAP* operator #507

jcoupey opened this issue May 13, 2021 · 1 comment · Fixed by #580

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented May 13, 2021

Our local search relies on various SWAP-like neighborhoods that will perform in-place exchanges of tasks (or pair of tasks), either between two different routes, or in the same route. For example the Exchange operator typically will spot situations like the following (edges are gray before applying and red after):

exchange_after

But requiring that both jobs take each other's place in the other route is very limiting and we're missing situations where the real gain would happen when moving tasks across routes while changing their respective ranks. Probably this can happen sometimes during the current search with two subsequent relocate moves but again in a very limited manner: the intermediate state has to be both valid (capacity, TW) and interesting in term of gain.

The drawback of this kind of move is that the a priori complexity is O(n^4) where n is the typical route length. Fortunately, this recent paper from Thibaut Vidal shares a clever way to reduce the required exploration, yet making sure to spot the best new insertion ranks. This brings down the operator lookup complexity to O(n^2).

So it appears we could have our cake and eat it too by superseding the existing Exchange operator with SWAP*: we'd then be able to reach out to more relevant neighboring solutions while not increasing the overall complexity.

@jcoupey
Copy link
Collaborator Author

jcoupey commented May 13, 2021

Note: the question of validity is not accounted for in the above paper, since HGS-CVRP maintains a population of infeasible solutions, and also validity is trivial for a plain CVRP.

We'd have to adjust this to embed the various required checks for the situations we cover (CVRP + backhauls, TW).

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