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

Route exchange operator #288

Closed
jcoupey opened this issue Jan 14, 2020 · 0 comments · Fixed by #300
Closed

Route exchange operator #288

jcoupey opened this issue Jan 14, 2020 · 0 comments · Fixed by #300
Assignees
Milestone

Comments

@jcoupey
Copy link
Collaborator

jcoupey commented Jan 14, 2020

While working with shipments on #274, I came across a situation where a whole route in the solution could be performed in the same order and at a cheaper cost by another vehicle. Yet the atomic moves available during local search are unable to reach this transformation.

This can only happen in a situation with heterogeneous fleet (think many different start and end points) and in the above case is related with a very specific way to model the problem. Nevertheless it's a fact that this may happen as a result of an heuristic bias (e.g. vehicle ordering for initial route construction) and we have no simple way to mend the solution if the local search fails to fix it.

We should have a simple "route exchange" operator to apply to pairs of vehicles during local search. Couple notes off the top of my head:

  • potential gain / validity computations are pretty straightforward
  • no fancy choice on ranks in routes like other operators, so low complexity and probably small overhead
  • only apply this operator for instances with heterogeneous fleet
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