2-opt: basic algorithm

Naive 2-optimization code

We can apply 2-opt move as an improvement step in general scheme of local optimization.

A naive version:

...
  for i in 0 .. N-1:   # outer loop is for X1-X2 link
    X1 = tour[i]
    X2 = tour[(i+1) mod N]
    for j in 0 .. N-1:   # inner loop is for Y1-Y2 link
      Y1 = tour[j]
      Y2 = tour[(j+1) mod N]
      if (Y1 == X1) or (Y1 == X2) or (Y2 == X1): # not 2-opt
         continue

      if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
        # this move will shorten the tour, apply it at once
        Make_2_Opt_Move(tour, i, j)
...

We can save half of iterations by taking an advantage from symmetry of STSP. There is no need to check pair (10,5), since it is the same as pair (5,10) already checked before. Therefore we can safely skip all cases where j is greater than i. Or just start j loop from i+2 value, because X1 and Y1 should not be consecutive cities.

Using the first improving 2-opt move

proc LS_2_Opt(tour: var Tour_Array) =
  ## Iteratively optimizes given tour using 2-opt moves.
  # Shortens the tour by repeating 2-opt moves until no improvement
  # can by done; in every iteration immediatelly makes permanent
  # change from the first move found that gives any length gain.
  var
    locallyOptimal: bool = false
    i, j: Tour_Index
    counter_2_Limit: Tour_Index 
    X1, X2, Y1, Y2: 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]

        if i == 0:
          counter_2_Limit = N-2
        else:
          counter_2_Limit = N-1 

        for counter_2 in (i+2) .. counter_2_Limit:
          j = counter_2
          Y1 = tour[j]
          Y2 = tour[(j+1) mod N]

          if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
            # this move will shorten the tour, apply it at once
            Make_2_Opt_Move(tour, i, j)
            locallyOptimal = false
            break two_loops  

Note that this code still could be changed for some more efficiency: for example Gain_From_2_Opt() called many times in inner loop uses distance(X1, X2) to obtain a value which is an invariable in this loop. You may also notice that Make_2_Opt_Move() is a oneliner identical to calling Reverse_Segment() with one parameter incremented...

Using the best improving 2-opt move

Instead of applying the first move shortening the tour in given iteration we can use the move that gives the best improvement in this iteration:

proc LS_2_Opt_Take_Best(tour: var Tour_Array) =
  # Shortens the tour by repeating 2-opt moves until no improvement
  # can by done; in every iteration looks for and applies the move
  # that gives maximal length gain.
  type
    Move2 = object
      i, j: Tour_Index
      gain: Length_Gain
  var
    locallyOptimal: bool = false
    i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    counter_2_Limit: Tour_Index
    gainExpected: Length_Gain
    bestMove: Move2

  while not locallyOptimal:
    locallyOptimal = true
    bestMove.gain = 0

    for counter_1 in 0 .. N-3:
      i = counter_1
      X1 = tour[i]
      X2 = tour[(i+1) mod N]

      if i == 0:
        counter_2_Limit = N-2
      else:
        counter_2_Limit = N-1

      for counter_2 in (i+2) .. counter_2_Limit:
        j = counter_2
        Y1 = tour[j]
        Y2 = tour[(j+1) mod N]

        gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
        if gainExpected > bestMove.gain:
          bestMove = Move2(i: i,
                           j: j,
                           gain: gainExpected)
          locallyOptimal = false
    # end_for counter_1 loop 

    if not locallyOptimal:
      Make_2_Opt_Move(tour, bestMove.i, bestMove.j)
  # end_while not locallyOptimal 

Note that this method itself does not guarantee that the resulting tour will be shorter than in the first improvement method (see below).

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by the two 2-opt algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	107.58	115.79
	NN + 2opt	1253	88.39	92.53	97.95
	NN + 2opt Take Best	939	88.21	91.56	96.98
2	NN	100	100.00	108.67	120.52
	NN + 2opt	1168	92.32	95.77	102.48
	NN + 2opt Take Best	974	92.13	94.30	99.53
3	NN	100	100.00	108.36	125.23
	NN + 2opt	1146	92.12	94.70	99.51
	NN + 2opt Take Best	1253	92.38	93.91	96.94
4	NN	100	100.00	109.82	121.53
	NN + 2opt	1460	86.35	89.61	94.47
	NN + 2opt Take Best	1253	85.06	86.95	89.79
5	NN	100	100.00	112.23	121.84
	NN + 2opt	1146	93.00	97.32	104.07
	NN + 2opt Take Best	940	93.27	95.85	98.32
6	NN	100	100.00	111.97	121.54
	NN + 2opt	1360	88.70	94.23	98.62
	NN + 2opt Take Best	1040	88.99	91.87	95.01
7	NN	100	100.00	109.72	121.54
	NN + 2opt	1566	87.14	91.50	96.69
	NN + 2opt Take Best	1246	87.87	90.87	93.32
8	NN	100	100.00	110.66	119.32
	NN + 2opt	1175	88.45	93.37	98.67
	NN + 2opt Take Best	1168	88.30	91.43	94.53
9	NN	100	100.00	106.16	119.52
	NN + 2opt	1268	84.10	88.26	93.68
	NN + 2opt Take Best	1174	84.22	87.44	90.98
10	NN	100	100.00	107.81	117.47
	NN + 2opt	781	91.31	94.25	99.95
	NN + 2opt Take Best	875	90.30	93.02	96.06