Page "Travelling salesman problem" Paragraph 24

; V-opt heuristic: The variable-opt method is related to, and a generalization of the k-opt method.

Whereas the k-opt methods remove a fixed number ( k ) of edges from the original tour, the variable-opt methods do not fix the size of the edge set to remove.

Instead they grow the set as the search process continues.

The best known method in this family is the Lin – Kernighan method ( mentioned above as a misnomer for 2-opt ).

Shen Lin and Brian Kernighan first published their method in 1972, and it was the most reliable heuristic for solving travelling salesman problems for nearly two decades.

More advanced variable-opt methods were developed at Bell Labs in the late 1980s by David Johnson and his research team.

These methods ( sometimes called Lin – Kernighan – Johnson ) build on the Lin – Kernighan method, adding ideas from tabu search and evolutionary computing.

The basic Lin – Kernighan technique gives results that are guaranteed to be at least 3-opt.

The Lin – Kernighan – Johnson methods compute a Lin – Kernighan tour, and then perturb the tour by what has been described as a mutation that removes at least four edges and reconnecting the tour in a different way, then v-opting the new tour.

The mutation is often enough to move the tour from the local minimum identified by Lin – Kernighan.

V-opt methods are widely considered the most powerful heuristics for the problem, and are able to address special cases, such as the Hamilton Cycle Problem and other non-metric TSPs that other heuristics fail on.

For many years Lin – Kernighan – Johnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best known solutions for all other TSPs on which the method had been tried.