2-opt

K -Opt heuristics are a class of algorithms for approximate solving the problem of a Salesman ( PdH ). The k- opt heuristics belong to the Post- Optimization algorithms (English: After optimization), which are characterized in that they improve a solution already found on. The basic idea is to remove edges from a given tour and exchange against other edges, so that again gives a tour. Is the new tour is shorter than the old one, it is used as a new solution.

Method

The re-optimization when PdH is a round trip found by chance or heuristics to modify so that the sum of the edges reviews along the tour is reduced. The k- opt method is characterized in that it removes a certain amount of edges from the current solution then insert new edges that close the gaps.

The k- opt heuristics use the method of local search in neighborhoods. The neighborhood of a given solution f is defined as the set of all solutions obtained by certain specified changes in f. In the case of k- opt heuristic a k- exchange neighborhood is defined as the set of all valid solutions that arise when removing k edges from f and then inserting k new edges. In order to guarantee the validity of the solution, new edges close the round trip.

Structure

The following scheme characterizes the class of k- opt heuristics:

• Choose g as a new f

Algorithms

The algorithms of the class k -Opt are characterized by several features. Firstly, the choice of strategy is important, after which a new g is determined. Another factor is deciding on a method of determining the initial solution f Last, the choice of the parameter k has a large impact on the time complexity of the algorithm.

In the following, some properties may be mentioned, which have been established in the context of k- opt heuristics:

Strategies

• First improvement ( engl: first improvement ) chooses the first-best solution of g, which is better than f

• Selects the solution of g, which offers the greatest improvement

Algorithms for determining the starting solution

• Farthest insertion
• Nearest insertion
• Algorithm of Christophides

Values ​​for k

• K = 2 The simplest case. Two edges are removed and re-inserted crosswise.

In the presence of the triangle inequality, which is a practical requirement, one can show that the result of the 2- opt heuristic is a crossover free tour. If namely before a crossover, so you can, as indicated in the drawing on which to remove crossing edges and replace non-intersecting -by-two others. Because of the triangle inequality are obtained as a real improvement.

• K = 3 According to Lin (1965 ) of the case that the best results in relation to time.

Algorithms

The most well-known k- opt algorithm is the S. Lin and BW Kernighan (1973). He is very efficient in practice, but it may have in some cases exponential time complexity. The special feature of the Lin - Kernighan algorithm is that it operates with a variable k- value which is redefined in each iteration.