2.5-opt algorithm, also known as 2h-opt, is an extension of 2-opt, that takes into account two simple alternative moves of 3-opt type. In its most internal loop it examines not only a 2-opt move, but also two Node Shifts:

before | ||

after | ||

variant A | variant B | variant C |

### 2.5-optimization

```
proc LS_25_Opt_Take_First(tour: var Tour_Array) =
## Optimizes the given tour using 2.5-opt
# Shortens tour by repeating 2.5-opt moves until no improvement
# can by done: in every iteration immediatelly makes permanent
# the first move found that gives any length gain.
var
locallyOptimal: bool = false
i, j: Tour_Index
X1, X2, Y1, Y2, V0: City_Number
while not locallyOptimal:
locallyOptimal = true
block two_loops:
for counter_1 in 0 .. N-3:
i = counter_1
X1 = tour[i]
X2 = tour[(i+1) mod N]
for counter_2 in (counter_1+2) .. N-1:
j = counter_2
Y1 = tour[j]
Y2 = tour[(j+1) mod N]
if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
Make_2_Opt_Move(tour, i, j)
locallyOptimal = false
break two_loops
else:
V0 = tour[(i+2) mod N]
if V0 != Y1:
if Gain_From_Node_Shift(X1, X2, V0, Y1, Y2) > 0:
Make_Node_Shift_Move(tour, (i+1) mod N, j)
locallyOptimal = false
break two_loops
else:
V0 = tour[(N+j-1) mod N]
if V0 != X2:
if Gain_From_Node_Shift(V0, Y1, Y2, X1, X2) > 0:
Make_Node_Shift_Move(tour, j, i)
locallyOptimal = false
break two_loops
```

Note that this code could be improved to be more efficient:

```
var
del_2_Length: Length
dX1Y1, dX2Y2, dX2Y1: Length
...
for counter_2 in (counter_1+2) .. N-1:
...
del_2_Length = distance(X1, X2) + distance(Y1, Y2)
dX1Y1 = distance(X1, Y1)
dX2Y2 = distance(X2, Y2)
if del_2_Length - (dX1Y1 + dX2Y2) > 0:
Make_2_Opt_Move(tour, i, j)
locallyOptimal = false
break two_loops
else:
dX2Y1 = distance(X2, Y1)
V0 = tour[(i+2) mod N]
if V0 != Y1:
if (del_2_Length + distance(X2, V0)) -
(dX2Y2 + dX2Y1 + distance(X1, V0)) > 0:
Make_Node_Shift_Move(tour, (i+1) mod N, j)
locallyOptimal = false
break two_loops
else:
V0 = tour[(N+j-1) mod N]
if V0 != X2:
if (del_2_Length + distance(Y1, V0)) -
(dX1Y1 + dX2Y1 + distance(Y2, V0)) > 0:
Make_Node_Shift_Move(tour, j, i)
locallyOptimal = false
break two_loops
```

This reduces running times by about 25%. But since for other algorithms we used statistics for unimproved versions, the data below are also taken from runs of the basic version.

### Some simple statistics

Problem # | Method | Time | Best | Avg | Worst |
---|---|---|---|---|---|

1 | NN | 100 | 100.00 | 108.79 | 119.13 |

NN + 2opt | 1360 | 82.41 | 86.28 | 91.53 | |

NN + 2.5opt | 1973 | 82.24 | 86.10 | 90.26 | |

2 | NN | 100 | 100.00 | 112.19 | 126.04 |

NN + 2opt | 1075 | 90.74 | 95.07 | 98.61 | |

NN + 2.5opt | 1562 | 90.67 | 94.37 | 98.81 | |

3 | NN | 100 | 100.00 | 106.74 | 115.58 |

NN + 2opt | 1253 | 89.08 | 92.96 | 98.44 | |

NN + 2.5opt | 2813 | 88.87 | 92.03 | 94.75 | |

4 | NN | 100 | 100.00 | 106.17 | 113.25 |

NN + 2opt | 1980 | 87.02 | 91.50 | 95.35 | |

NN + 2.5opt | 1773 | 87.00 | 90.59 | 93.88 | |

5 | NN | 100 | 100.00 | 106.40 | 116.05 |

NN + 2opt | 1046 | 87.49 | 92.30 | 97.11 | |

NN + 2.5opt | 1559 | 87.03 | 91.54 | 96.61 | |

6 | NN | 100 | 100.00 | 108.92 | 117.85 |

NN + 2opt | 1360 | 90.28 | 95.28 | 100.53 | |

NN + 2.5opt | 1560 | 91.01 | 94.90 | 101.26 | |

7 | NN | 100 | 100.00 | 105.35 | 112.60 |

NN + 2opt | 975 | 88.55 | 92.35 | 96.38 | |

NN + 2.5opt | 2343 | 88.77 | 91.71 | 97.12 | |

8 | NN | 100 | 100.00 | 114.47 | 122.94 |

NN + 2opt | 1046 | 91.33 | 94.80 | 99.07 | |

NN + 2.5opt | 1873 | 91.10 | 94.69 | 101.03 | |

9 | NN | 100 | 100.00 | 106.94 | 119.14 |

NN + 2opt | 1460 | 89.70 | 93.79 | 99.39 | |

NN + 2.5opt | 1873 | 88.81 | 92.80 | 97.89 | |

10 | NN | 100 | 100.00 | 108.41 | 117.03 |

NN + 2opt | 1460 | 88.86 | 93.74 | 97.66 | |

NN + 2.5opt | 1666 | 88.64 | 92.83 | 98.34 |

## No comments:

## Post a Comment