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:
- Are there better ways to define neighborhood?
- Is there a way to find a promising neighborhood?