Friday, March 10, 2017

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_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_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
1NN100100.00109.03116.16
NN + 2opt136890.4994.2998.80
NN + 3opt6865090.3091.7895.96
2NN100100.00108.27116.78
NN + 2opt146082.1585.9191.02
NN + 3opt7083380.7682.9186.44
3NN100100.00107.71115.96
NN + 2opt136089.2292.7399.68
NN + 3opt6885388.2289.8394.19
4NN100100.00109.01119.52
NN + 2opt125390.8494.85101.98
NN + 3opt6906089.4391.5493.50
5NN100100.00107.84115.52
NN + 2opt146087.1190.5894.76
NN + 3opt7208685.3487.0289.58
6NN100100.00112.18124.09
NN + 2opt166685.3988.5093.23
NN + 3opt7052683.8885.4488.48
7NN100100.00107.35116.78
NN + 2opt136088.5791.1496.73
NN + 3opt7500086.9888.3390.25
8NN100100.00111.81123.85
NN + 2opt136887.5091.4896.90
NN + 3opt6484386.1288.5391.28
9NN100100.00116.59128.45
NN + 2opt146090.8694.2399.83
NN + 3opt6968689.3591.4295.11
10NN100100.00109.34121.81
NN + 2opt107593.0095.2999.78
NN + 3opt6416291.3092.5194.34

2 comments:

  1. DUde,you are great. Whole blog dedicated to TSP. Salute to you. You made 3opt very easy for me, which I was not able to understand properly from any other source. Looking forward to understand LK heuristic from your blog.

    Thank You very much. This is very helpful.

    ReplyDelete