One of the standard transformations of a tour used in local optimization is reversing a segment. In the new tour all the cities of the segment occur in reverse order.

pos. 0 123 456 7 ... before A-B-C-D-E-F-G-H-... after A-B-F-E-D-C-G-H-...

We use the following algorithm: swap the first and the last city of the segment, then the second and one before last, and so on, to the middle of the segment. This way number of swaps is equal half of the segment size.

**Beware**

We should not forget that a tour is cyclic, and therefore after `tour[N-1]`

city (in ascending order of indices) goes `tour[0]`

, to close the tour. Therefore segment from `tour[N-2]`

to `tour[2]`

is 5 cities long — it constists of: `tour[N-2]`

, `tour[N-1]`

, `tour[0]`

, `tour[1]`

and `tour[2]`

, in this order. Note that reversing the complementary segment, consisting of the cities on positions from 2 to (N-2), is not the exactly same and in some cases may lead to erroneous results. (But see later reversing a segment given by city numbers, not by positions, more complex and using additional structure, but where this problem does not occur).

```
proc Reverse_Segment(tour: var Tour_Array;
startIndex, endIndex: Tour_Index) =
## Reverses order of elements in segment [startIndex, endIndex]
## of tour.
## NOTE: Final and initial part of tour make one segment.
## NOTE: While the order of arguments can be safely changed when
## reversing segment in 2-optimization, it makes difference for
## 3-opt move - be careful and do not reverse (x,z) instead of (z,x).
var
left, right: Tour_Index
let inversionSize = ((N + endIndex - startIndex + 1) mod N) div 2
left = startIndex
right = endIndex
for counter in 1 .. inversionSize:
swap(tour[left], tour[right])
left = (left + 1) mod N
right = (N + right - 1) mod N
```

## No comments:

## Post a Comment