# Naming of k-opt local search heuristic in areas other than routing

 1 k-opt is a very well-known local search heuristic in the area of routing problems in which you exchange k arcs in a selected route. In areas other than routing, k-opt simply means changing values of (up to) k components of the solution. The second one is a very popular local search heuristic for designing (meta)heuristics in other areas. I've seen academics familiar with the routing area who believes that "k-opt" is a reserved term for routing heuristics (maybe because application of "k-opt" term in routing area is older than other areas). So my question is as follows: What do you name a k-opt heuristic if it is used in areas other than routing? Do you still use k-opt or do you use other alternatives (maybe k-exchange)? ps. Any elaboration on the differences of terms "k-opt" and "k-exchange" in routing or other areas is highly appreciated. asked 16 Sep '11, 16:30 Ehsan ♦ 4.8k●3●12●24 accept rate: 16% fbahr ♦ 4.6k●7●17

 4 As written in Metaheuristics: From Design to Implementation pg. 92 (I was reading this a couple of hours ago :P) For scheduling problems, the 2-opt operator will generate a very large variation (weak locality), whereas for routing problems such as the TSP, it is a very efﬁcient operator because the variation is much smaller (strong locality). Neighborhoods for permutation scheduling problems. For permutations representing sequencing and scheduling problems, the k -opt family of operators is not well suited. The following operators may be used: Position-based neighborhood: Figure 2.7 illustrates an example of a position-based operator, the insertion operator. In the insertion operator, an element at one position is removed and put at another position. The two positions are randomly selected. FIGURE 2.7 Insertion operator :  { 1 2 3 4 5 6 7 8 } { 1 6 2 3 4 5 7 8 }  Order-based neighborhood: Many order-based operators can be used such as the exchange operator where arbitrarily selected two elements are swapped as shown in Fig. 2.8, and the inversion operator where two elements are randomly selected and the sequence of elements between these two elements are inverted as shown in Fig. 2.9.- FIGURE 2.8 Exchange operator:  { 1 2 3 4 5 6 7 8 } { 1 2 7 4 5 6 3 8 }  FIGURE 2.9 Inversion operator:  { 1 2 3 4 5 6 7 8 } { 1 2 7 6 5 4 3 8 }  answered 17 Sep '11, 12:46 Florents Tselai 600●5●16 accept rate: 7% @Florenc: I just read the book. It seems that it uses the term "k-opt" as a general term. It also mentions that the "k-opt" and "k-exchange" can be used interchangeably. (17 Sep '11, 14:36) Ehsan ♦ @Ehsan Actually, i've mainly seen these two terms being used together as "k-opt exchange" (17 Sep '11, 14:50) Florents Tselai @Florenc: Thanks. You're correct. I think k-exchange is used less than other names. What confuses me the most is that are many naming conventions for this issue used in literature of various areas. (17 Sep '11, 15:00) Ehsan ♦ 1 In Mathematical Programming Glossary, k-opt is introduced as "a heuristic for the TSP, though it can apply more generally to a problem that seeks a subgraph with all nodes." http://glossary.computing.society.informs.org/second.php?page=N.html#n-Opt (09 Feb '12, 02:16) Ehsan ♦
 2 ISTR I've seen these referred to as Lin-Kernighan-style heuristics, but I can't recall the context. I referred to my application of the idea to 3D assignment in my dissertation as "variable-depth interchange". answered 28 Nov '11, 12:06 Matthew Salt... ♦ 4.7k●3●10 accept rate: 17%
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

×18
×13
×9
×8
×1

Asked: 16 Sep '11, 16:30

Seen: 4,785 times

Last updated: 09 Feb '12, 02:16

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.