Or-opt

Or-opt idea

Or-opt is an algorithm proposed by Ilhan Or in 1976: a segment consisting of 3, 2 or 1 consecutive cities is shifted to other position in tour. This means that Or-opt is a restricted version of 3-opt and therefore it should be somewhat faster, but produce worse tours than full 3-optimization.

Or-opt move

Each move used by Or-opt is just Segment Shift:

proc Make_Segment_Shift_Move(tour: var Tour_Array;
                             i, j, k: Tour_Index) =
  ## Performs given Segment Shift move
  Shift_Segment(tour, i, j, k)

Gain from Or-opt move

proc Gain_From_Segment_Shift(X1, X2, Y1, Y2, Z1, Z2: City_Number):
                             Length_Gain =
  ## Gain of tour length which can be obtained by performing Segment
  ## Shift
  # Cities from X2 to Y1 would be moved from its current position,
  # between X1 and Y2, to position between cities Z1 and Z2.
  # Assumes: X1!=Z1
  #          X2==successor(X1); Y2==successor(Y1); Z2==successor(Z1)
  let del_Length = distance(X1, X2) + distance(Y1, Y2) + distance(Z1, Z2)
  let add_Length = distance(X1, Y2) + distance(Z1, X2) + distance(Y1, Z2)
  result = del_Length - add_Length

Or-opt using the first improving move

proc LS_Or_opt_Take_First(tour: var Tour_Array) =
  ## Optimizes the given tour using Or-opt
  # Shortens the tour by repeating Segment Shift moves for segment
  # length equal 3, 2, 1 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, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number

  while not locallyOptimal:
    locallyOptimal = true

    for segmentLen in countdown(3, 1):
    
      block two_loops:
        for pos in 0 .. N-1:
          i = pos
          X1 = tour[i]
          X2 = tour[(i + 1) mod N]
          
          j = (i + segmentLen) mod N
          Y1 = tour[j]
          Y2 = tour[(j + 1) mod N]

          for shift in segmentLen+1 .. N-1:
            k  = (i + shift) mod N
            Z1 = tour[k]
            Z2 = tour[(k + 1) mod N]

            if Gain_From_Segment_Shift(X1, X2, Y1, Y2, Z1, Z2) > 0:
              Make_Segment_Shift_Move(tour, i, j, k)
              locallyOptimal = false
              break two_loops

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 Or-opt algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	111.23	122.80
	NN + 2opt	1460	93.96	96.65	100.64
	NN + Or-opt	6460	94.64	97.26	102.54
	NN + 2opt + Or-opt	3126	92.29	94.59	97.28
2	NN	100	100.00	110.64	119.25
	NN + 2opt	1268	86.93	90.19	95.17
	NN + Or-opt	8106	89.00	93.09	101.05
	NN + 2opt + Or-opt	3218	85.30	88.33	91.93
3	NN	100	100.00	109.22	115.52
	NN + 2opt	1075	85.48	89.20	93.58
	NN + Or-opt	6543	86.91	92.35	98.14
	NN + 2opt + Or-opt	3125	85.01	87.19	90.52
4	NN	100	100.00	111.96	119.75
	NN + 2opt	1360	87.37	91.02	96.94
	NN + Or-opt	7079	87.92	95.32	104.80
	NN + 2opt + Or-opt	2919	85.83	89.19	94.70
5	NN	100	100.00	109.49	117.46
	NN + 2opt	1075	93.43	96.66	103.79
	NN + Or-opt	4687	93.12	97.78	103.31
	NN + 2opt + Or-opt	2831	92.28	94.29	100.36
6	NN	100	100.00	105.35	112.56
	NN + 2opt	1253	87.02	90.97	98.85
	NN + Or-opt	6146	87.43	92.79	100.48
	NN + 2opt + Or-opt	2913	86.84	89.18	94.75
7	NN	100	100.00	107.32	117.78
	NN + 2opt	1253	90.06	94.14	97.89
	NN + Or-opt	6353	92.18	95.90	100.65
	NN + 2opt + Or-opt	3439	88.44	91.28	95.44
8	NN	100	100.00	115.11	124.44
	NN + 2opt	1666	88.10	91.08	97.24
	NN + Or-opt	6879	90.65	96.09	102.98
	NN + 2opt + Or-opt	3746	86.16	88.84	92.96
9	NN	100	100.00	108.46	113.81
	NN + 2opt	1146	92.35	97.09	101.10
	NN + Or-opt	5420	94.40	99.33	105.41
	NN + 2opt + Or-opt	2913	91.67	94.77	98.97
10	NN	100	100.00	108.04	117.50
	NN + 2opt	1146	88.20	93.30	98.54
	NN + Or-opt	5833	88.58	95.29	102.31
	NN + 2opt + Or-opt	2813	88.12	91.34	94.55