11
$\begingroup$

I have been trying to implement a variant of LNS on a graph for TSP. One of the ways that I can define a neighborhood for TSP is to find $k$-shortest path between two nodes. But the choice of these nodes are random. I have two questions:

  1. Are there better ways to define neighborhood?
  2. Is there a way to find a promising neighborhood?
Improve this question
$\endgroup$
2
11
$\begingroup$

This paper by Pisinger and Ropke is particularly useful when working on (A)LNS, and provides great guidance and an overview of operators/neighborhoods. I would suggest this paper by Vidal et al. for more genetic search inspired aspects.

Improve this answer
$\endgroup$
8
$\begingroup$

These common neighborhoods for TSP/VRP might be useful:

  • 2-opt, 3-opt, ..., k-opt
  • change 1 visit: remove 1 visit from a chain and insert it somewhere else in a chain
  • swap 2 visits
  • change a subchain of visits: remove a number of sequential visits from a chain and insert it somewhere else in a chain, sometimes reversed
  • swap 2 subchains
  • ruin&recreate
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.