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

4 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
  2. Hi, thank you very much for this blog.
    I have a question. What is the algorithmic complexity of this algorithms?

    Best regards,
    Ronald Sulbaran

    ReplyDelete
    Replies
    1. O(N^3).
      This is why often neigbour lists are used to reduce it (see `Nearest neighbor lists'), that is to make it O(N*K^2), where K is a number of neigbours considered for each city to break or add a link.

      Delete