31.11 Variable neighbourhood descent¶
Part 4 · Heuristic algorithms · Chapter 31 · Chapter 31: Local search · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Local search · App: TSP: nearest neighbour and 2-opt
- The examples of the previous sections show that a local optimum for one neighbourhood is often not a local optimum for another: the solution of \(LPT\) for move and swap, the 2-opt local optimum of length \(41\) for 2-opt and Or-opt. The natural idea is to use several neighbourhoods \(N_1,\dots,N_K\), and to stop only when none of them contains an improving neighbour.
The variable neighbourhood descent (denoted by \(VND\)) explores the neighbourhoods \(N_1,\dots,N_K\) in this order. It looks for an improving move in the current neighbourhood \(N_k\): if it finds one, it applies it and goes back to \(N_1\); otherwise it passes to \(N_{k+1}\). It stops when the current solution is a local optimum for all the \(K\) neighbourhoods.
Algorithm: Variable neighbourhood descent
-
\(VND\) stops after a finite number of moves, by the argument of Proposition 31.2. When it stops, \(\textit{Step}_K\) has failed and, since the last improving move, all of \(\textit{Step}_1,\dots,\textit{Step}_{K-1}\) have failed on the same solution: the solution returned is a local optimum for every \(N_k\), i.e., for the union \(N_1\cup\dots\cup N_K\).
-
The neighbourhoods are ordered from the smallest and cheapest to the largest: the expensive neighbourhoods are explored only when the cheap ones are exhausted. \(VND\) is the deterministic part of the variable neighbourhood search of Mladenovic and Hansen (Computers & Operations Research 24, 1997).
Example 31.9: \(VND\) on \(P\,||\,C_{\max}\) with move and swap
On the reference instance, from the solution of \(LPT\), with \(N_1=\) move and \(N_2=\) swap, and the makespan as objective:
| \(k\) | result of \(\textit{Step}_k\) | loads | next |
|---|---|---|---|
| \(1\) | no improving move | \((11,8,8)\) | \(k=2\) |
| \(2\) | swap jobs \(1\) and \(3\) | \((10,8,9)\) | \(k=1\) |
| \(1\) | no improving move | \((10,8,9)\) | \(k=2\) |
| \(2\) | swap jobs \(3\) and \(6\) | \((9,9,9)\) | \(k=1\) |
| \(1\) | no improving move | \((9,9,9)\) | \(k=2\) |
| \(2\) | no improving swap | \((9,9,9)\) | stop |
In the solution with loads \((10,8,9)\) the best move gives makespan \(11\) (job \(5\) or job \(7\) from machine \(1\) to machine \(2\)), so move is again exhausted, and swap finds the optimum.
Example 31.10: \(VND\) on the TSP with 2-opt and Or-opt
On the instance with \(10\) cities of Example 31.3, from the tour of \(NN\) (length \(49\)), with \(N_1=\) 2-opt, \(N_2=\) Or-opt and the first-improvement rule, \(VND\) makes the four 2-opt moves of the 2-opt local search (\(49\to47\to46\to43\to41\)), then the Or-opt move of Example 31.4, which inserts city \(9\) between cities \(3\) and \(4\) (\(41\to39\)), and stops: the optimal tour is a local optimum for both neighbourhoods. With the best-improvement rule, 2-opt alone already reaches the optimum.
- On the two medium instances of Section 31.9, with \(100\) random starting solutions (seed \(1\)) and best improvement, \(VND\) with \(N_1=\) move and \(N_2=\) swap gives:
| instance | objective | runs ending in an optimum | average value |
|---|---|---|---|
| \(P\,||\,C_{\max}\), \(m=4\), \(n=12\) | \(C_{\max}\) | \(15\) | \(20.62\) |
| \(P\,||\,C_{\max}\), \(m=4\), \(n=12\) | \(\sum_h L_h^2\) | \(68\) | \(19.32\) |
| BPP, \(c=10\), \(n=12\) | \(\sum_b L_b^2\) | \(89\) | \(5.11\) |
- Compared with the single neighbourhoods of Section 31.9, \(VND\) with the auxiliary objective reaches the optimum in \(68\) runs out of \(100\) for \(P\,||\,C_{\max}\) (move alone: \(4\)) and in \(89\) for the BPP (move alone: \(76\)). Combining neighbourhoods and using the auxiliary objective are independent improvements, and they add up.