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's gravatar image

Ehsan ♦
4.8k31122
accept rate: 16%

retagged 26 Nov '11, 15:15

fbahr's gravatar image

fbahr ♦
4.6k716


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 efficient 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 }
link

answered 17 Sep '11, 12:46

Florents%20Tselai's gravatar image

Florents Tselai
600516
accept rate: 7%

edited 17 Sep '11, 16:28

@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 ♦

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".

link

answered 28 Nov '11, 12:06

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

edited 28 Nov '11, 12:07

Your answer
toggle preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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,578 times

Last updated: 09 Feb '12, 02:16

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