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

Patrick
214
accept rate: 0%

edited 02 May '14, 06:16

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

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:

×22
×13
×8
×8
×2

Asked: 02 May '14, 06:08

Seen: 2,137 times

Last updated: 02 May '14, 12:41

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