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 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
Patrick |

INAE, but - as far as my understanding goes - 2-opt usually is defined as

intra-routeneighborhood (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* asinter-routeneighborhood (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).").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?

It would be great if you could provide references to what you've already seen, specially for 2-Opt*.