3-opt: basic algorithm

Using the first improving 3-opt move

After taking into account the findings from the general idea of 3-opt we have the following code:

proc LS_3_Opt(tour: var Tour_Array) =
  ## Iteratively optimizes given tour using 3-opt moves.
  # Shortens the tour by repeating 3-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, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    optCase: Reconnection_3_optCase
    gainExpected: Length_Gain

  while not locallyOptimal:
    locallyOptimal = true

    block four_loops:
      for counter_1 in 0 .. N-1:
        i = counter_1 # first cut after i
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
        for counter_2 in 1 .. N-3:
          j = (i + counter_2) mod N # second cut after j
          Y1 = tour[j]
          Y2 = tour[(j+1) mod N]
          for counter_3 in counter_2+1 .. N-1:
            k = (i + counter_3) mod N  # third cut after k
            Z1 = tour[k]
            Z2 = tour[(k+1) mod N]

            for optCase in [opt3_case_3, opt3_case_6, opt3_case_7]:
              gainExpected = Gain_From_3_Opt(X1, X2,
                                             Y1, Y2,
                                             Z1, Z2,
                                             optCase)
              if gainExpected > 0:
                Make_3_Opt_Move(tour, i, j, k, optCase)
                locallyOptimal = false
                break four_loops

Using the best improving 3-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_3_Opt_Take_Best(tour: var Tour_Array) =
  # Shortens the tour by repeating 3-opt moves until no improvement
  # can by done: in every iteration looks for and applies the move
  # that gives maximal length gain.
  type
    Move3 = object
      i, j, k: Tour_Index
      optCase: Reconnection_3_optCase
      gain: Length_Gain
  var
    locallyOptimal: bool = false
    i, j, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    gainExpected: Length_Gain
    optCase: Reconnection_3_optCase
    bestMove: Move3

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

    for counter_1 in 0 .. N-1:
      i = counter_1 # first cut after i
      X1 = tour[i]
      X2 = tour[(i+1) mod N]
      for counter_2 in 1 .. N-3:
        j = (i + counter_2) mod N # second cut after j
        Y1 = tour[j]
        Y2 = tour[(j+1) mod N]
        for counter_3 in counter_2+1 .. N-1:
          k = (i + counter_3) mod N  # third cut after k
          Z1 = tour[k]
          Z2 = tour[(k+1) mod N]

          for optCase in [opt3_case_3, opt3_case_6, opt3_case_7]:
            gainExpected = Gain_From_3_Opt(X1, X2,
                                           Y1, Y2,
                                           Z1, Z2,
                                           optCase)
            if gainExpected > bestMove.gain:
              bestMove = Move3(i: i,
                               j: j,
                               k: k,
                               optCase: optCase,
                               gain: gainExpected)
              locallyOptimal = false
    # end_for counter_1 loop

    if not locallyOptimal:
      Make_3_Opt_Move(tour,
                      bestMove.i,
                      bestMove.j,
                      bestMove.k,
                      bestMove.optCase)

Some simple statistics

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

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	109.03	116.16
	NN + 2opt	1368	90.49	94.29	98.80
	NN + 3opt	68650	90.30	91.78	95.96
2	NN	100	100.00	108.27	116.78
	NN + 2opt	1460	82.15	85.91	91.02
	NN + 3opt	70833	80.76	82.91	86.44
3	NN	100	100.00	107.71	115.96
	NN + 2opt	1360	89.22	92.73	99.68
	NN + 3opt	68853	88.22	89.83	94.19
4	NN	100	100.00	109.01	119.52
	NN + 2opt	1253	90.84	94.85	101.98
	NN + 3opt	69060	89.43	91.54	93.50
5	NN	100	100.00	107.84	115.52
	NN + 2opt	1460	87.11	90.58	94.76
	NN + 3opt	72086	85.34	87.02	89.58
6	NN	100	100.00	112.18	124.09
	NN + 2opt	1666	85.39	88.50	93.23
	NN + 3opt	70526	83.88	85.44	88.48
7	NN	100	100.00	107.35	116.78
	NN + 2opt	1360	88.57	91.14	96.73
	NN + 3opt	75000	86.98	88.33	90.25
8	NN	100	100.00	111.81	123.85
	NN + 2opt	1368	87.50	91.48	96.90
	NN + 3opt	64843	86.12	88.53	91.28
9	NN	100	100.00	116.59	128.45
	NN + 2opt	1460	90.86	94.23	99.83
	NN + 3opt	69686	89.35	91.42	95.11
10	NN	100	100.00	109.34	121.81
	NN + 2opt	1075	93.00	95.29	99.78
	NN + 3opt	64162	91.30	92.51	94.34