# 2-Opt/2-Opt* Neighborhood

 1 Dear OR-Community, I have searched for quite some time now, but could not find precise literature on this topic. In a recent Paper which deals with multi-start iterated local search for the PVRPTW, I came across the following words: Context: The local search algorithm browses four neighborhoods, of which two are the following: "2-Opt: The 2-opt move removes two arcs (i, j) and (u, v) traversed in the same route or in two distinct routes and reconnects the route(s) concerned using arcs (i, u) and (j, v). On one route, this move can be also deﬁned by a reversal of subsequence from j to u included. When applied to two routes, two subsequences are reversed. 2-Opt*: In this move, two arcs (i, j) and (u, v) in the same route or in two routes are replaced by (i, v) and (u, j). Contrary to 2-opt, no subsequence is reversed after this operation." My question now is: Assume that i and j, as well as u and v, are both two subsequent customers in the same route. Imagine the following tour: Depot - 1 - i - j - 4 - u - v - 7 - Depot 2-Opt* ==> Depot - 1 - i - v - 7 - Depot and j - 4 - u - j Performing a 2-Opt* move produces an isolated subtour - how does that make sense?? Thank you! :) Patrick asked 02 May '14, 06:08 Patrick 21●4 accept rate: 0% INAE, but - as far as my understanding goes - 2-opt usually is defined as intra-route neighborhood (i. e., "The 2-opt move removes two arcs (i, j) and (u, v) traversed in the same route or in two distinct routes and...") and 2-opt* as inter-route neighborhood (i. e, "In this move, two arcs (i, j) and (u, v) in the same route or in two routes are replaced by (i, v) and (u, j)."). (02 May '14, 07:09) fbahr ♦ Thank you. Somewhere on the Internet I have seen an example with 2-Opt on a single route and 2-Opt* on two routes, but without explicitly stating those being intra-route and inter-route neighborhoods. Probably anyone has hints on literature following that aproach? (02 May '14, 07:33) Patrick It would be great if you could provide references to what you've already seen, specially for 2-Opt*. (02 May '14, 12:41) Ehsan ♦
Be the first one to answer this question!
 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:

×22
×13
×8
×8
×2

Asked: 02 May '14, 06:08

Seen: 2,251 times

Last updated: 02 May '14, 12:41

### Related questions

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