32.7 Variable neighbourhood search¶
Part 4 · Heuristic algorithms · Chapter 32 · Chapter 32: Metaheuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Metaheuristics · App: TSP: simulated annealing and tabu search
Variable neighbourhood search (denoted by \(VNS\)) uses a sequence of neighbourhoods \(N_1,N_2,\dots,N_{k_{\max}}\) of increasing size. From the current local optimum it draws a random solution in \(N_k\) (shaking), applies a local search to it, and moves to the new local optimum if it is better, restarting from \(k=1\); otherwise it tries the next, larger neighbourhood \(N_{k+1}\).
- The pseudo-code of \(VNS\) for \(P\,||\,C_{\max}\), where \(N_k\) contains the assignments obtained with \(k\) moves and the local search is MOVEDESCENT, reads as follows:
Algorithm: Variable neighbourhood search for \(P\,||\,C_{\max}\)
-
\(VNS\) was proposed by Mladenovic and Hansen (1997). It rests on three observations: a local optimum for one neighbourhood need not be a local optimum for another; a global optimum is a local optimum for every neighbourhood; and the local optima of different neighbourhoods are often close to each other.
-
Shaking diversifies, and the size \(k\) controls how much: small \(k\) explores the solutions close to the current local optimum, larger \(k\) goes farther only when the closer ones have failed. The local search intensifies. Returning to \(k=1\) after every improvement concentrates the search near the new, better solution.
-
The variable neighbourhood descent (\(VND\)) of the chapter «Local search» also uses several neighbourhoods, but deterministically: it explores them completely, one after the other, and stops at a solution that is a local optimum for all of them. \(VNS\) explores the large neighbourhoods only by random samples, which is what makes very large neighbourhoods usable; the local search inside \(VNS\) can itself be a \(VND\).
-
Here \(N_k\) contains the assignments obtained by moving \(k\) jobs (or fewer, if the same job is drawn twice). Since a swap of two jobs is the combination of two moves, \(N_2\) contains the swap neighbourhood: shaking with \(k=2\) can reproduce the swaps that the move neighbourhood cannot see.
32.7.1 Example¶
Example 32.7: \(VNS\) on the \(P\,||\,C_{\max}\) reference instance
We start from the LPT solution, with loads \((11,8,8)\), and use \(k_{\max}=3\) and \(seed=1\) (random numbers \(0.0000\), \(0.1315\), \(0.7556\), \(0.4587\), \(0.5328\), \(0.2190\), \(0.0470\), \(0.6789\)). MOVEDESCENT does not change the LPT solution, which is a local optimum for the move neighbourhood (Example 32.5). Each random move uses two numbers: \(j=1+\lfloor 7u\rfloor\) and \(g=1+\lfloor 2u\rfloor\).
-
Iteration 1, \(k=1\): job \(j=1+\lfloor 7\cdot 0.0000\rfloor=1\) moves from \(M_1\) to the first other machine (\(g=1+\lfloor 2\cdot 0.1315\rfloor=1\)), \(M_2\): loads \((6,13,8)\). MOVEDESCENT moves job \(6\) from \(M_2\) to \(M_1\): loads \((9,10,8)\), \(C_{\max}=10\), better than \(11\). The new solution \(J_1=\{5,6,7\}\), \(J_2=\{1,2\}\), \(J_3=\{3,4\}\) is accepted, and \(k=1\).
-
Iteration 2, \(k=1\): job \(j=1+\lfloor 7\cdot 0.7556\rfloor=6\) moves from \(M_1\) to \(M_2\) (\(g=1+\lfloor 2\cdot 0.4587\rfloor=1\)): loads \((6,13,8)\). MOVEDESCENT moves job \(6\) back to \(M_1\) and returns the current solution, which is not better: \(k=2\).
-
Iteration 3, \(k=2\): job \(j=1+\lfloor 7\cdot 0.5328\rfloor=4\) moves from \(M_3\) to the first other machine \(M_1\) (\(g=1+\lfloor 2\cdot 0.2190\rfloor=1\)); then job \(j=1+\lfloor 7\cdot 0.0470\rfloor=1\) moves from \(M_2\) to the second other machine \(M_3\) (\(g=1+\lfloor 2\cdot 0.6789\rfloor=2\)): loads \((13,5,9)\). MOVEDESCENT moves job \(4\) from \(M_1\) to \(M_2\): loads \((9,9,9)\). The solution is accepted, and since \(C_{\max}=9=\LB\) the search stops: \(VNS(I)=9=z(I)\).
In terms of the current solution of iteration \(3\), the two random moves and the descent have exchanged jobs \(1\) and \(4\): a swap, which the move neighbourhood of MOVEDESCENT cannot perform.
- On PCM15, from the LPT solution (\(73\)) and with at most \(300\) iterations, \(VNS\) gives the following makespans for \(seed=1,\dots,10\), and the number of iterations performed:
| \(seed\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) |
|---|---|---|---|---|---|---|---|---|---|---|
| \(k_{\max}=1\): \(C_{\max}\) | \(69\) | \(70\) | \(70\) | \(70\) | \(69\) | \(69\) | \(69\) | \(69\) | \(70\) | \(69\) |
| iterations | \(27\) | \(300\) | \(300\) | \(300\) | \(48\) | \(59\) | \(20\) | \(43\) | \(300\) | \(13\) |
| \(k_{\max}=2\): \(C_{\max}\) | \(70\) | \(69\) | \(69\) | \(69\) | \(69\) | \(70\) | \(69\) | \(70\) | \(70\) | \(69\) |
| iterations | \(300\) | \(41\) | \(126\) | \(285\) | \(33\) | \(300\) | \(31\) | \(300\) | \(300\) | \(26\) |
| \(k_{\max}=3\): \(C_{\max}\) | \(70\) | \(69\) | \(69\) | \(69\) | \(69\) | \(69\) | \(69\) | \(70\) | \(70\) | \(69\) |
| iterations | \(300\) | \(32\) | \(38\) | \(29\) | \(26\) | \(11\) | \(25\) | \(300\) | \(300\) | \(25\) |
- With \(k_{\max}=3\), \(VNS\) reaches the optimum \(69\) in \(7\) runs out of \(10\), usually in a few tens of iterations; the best tabu search of Section 32.5.2 needed a carefully tuned tenure. When \(VNS\) fails, the search is stuck at \(70\): the shaking explores at most three moves away, and the optimum is farther. Larger \(k_{\max}\), or restarts, can be added at the price of more iterations.
Next: 32.8 GRASP