Tuesday, March 14, 2017


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.
    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
NN + 2opt146093.9696.65100.64
NN + Or-opt646094.6497.26102.54
NN + 2opt + Or-opt312692.2994.5997.28
NN + 2opt126886.9390.1995.17
NN + Or-opt810689.0093.09101.05
NN + 2opt + Or-opt321885.3088.3391.93
NN + 2opt107585.4889.2093.58
NN + Or-opt654386.9192.3598.14
NN + 2opt + Or-opt312585.0187.1990.52
NN + 2opt136087.3791.0296.94
NN + Or-opt707987.9295.32104.80
NN + 2opt + Or-opt291985.8389.1994.70
NN + 2opt107593.4396.66103.79
NN + Or-opt468793.1297.78103.31
NN + 2opt + Or-opt283192.2894.29100.36
NN + 2opt125387.0290.9798.85
NN + Or-opt614687.4392.79100.48
NN + 2opt + Or-opt291386.8489.1894.75
NN + 2opt125390.0694.1497.89
NN + Or-opt635392.1895.90100.65
NN + 2opt + Or-opt343988.4491.2895.44
NN + 2opt166688.1091.0897.24
NN + Or-opt687990.6596.09102.98
NN + 2opt + Or-opt374686.1688.8492.96
NN + 2opt114692.3597.09101.10
NN + Or-opt542094.4099.33105.41
NN + 2opt + Or-opt291391.6794.7798.97
NN + 2opt114688.2093.3098.54
NN + Or-opt583388.5895.29102.31
NN + 2opt + Or-opt281388.1291.3494.55

No comments:

Post a Comment