Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

Question

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?

This paper is particularly useful when working on (A)LNS, and provides great guidance and an overview of operators/neighborhoods. https://www.sciencedirect.com/science/article/pii/S0305054805003023 — Albert Schrotenboer, May 31 '19 at 07:11
@AlbertSchrotenboer that seems like it deserves to be an answer, not a comment. — LarrySnyder610, May 31 '19 at 12:01

score 11 · Accepted Answer · answered May 31 '19 at 12:05

11

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.

answered May 31 '19 at 12:05

Albert Schrotenboer

1,859
12
27

score 8 · Answer 2 · answered Jun 03 '19 at 19:30

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

Neigbourhoods in Large Neighbourhood Search (LNS) algorithms

2 Answers2