4-opt* – general idea, part 1

Since full 4-opt is rather complex and time comsuming, Renaud, Boctor and Laporte (1996) proposed a tour improving procedure caled 4-opt*, based on using a specific subset of 4-opt moves. Its main goal is to extend searching for improving moves beyond 2-opt moves, but keep this searching fast.

Elements of 4-opt move	Elements of 4-opt* move

As we can see, the first difference between standard 4-opt and 4-opt* is that while the scheme of general 4-opt move involves four non-overlapping segments with eight endpoints, the scheme of 4-opt* involves only three segments and seven points; fourth segment is reduced to one point between endpoints of two other segments. The layout for standard 4-opt requires four parameters (i, j, k, m), but for 4-opt* it is only three parameters (i, j, k). This allows us to reduce number of corresponding nested loops in searching for an improvement, each of O(N). (There is additional advantage: reduction of possible cases of reconnection. In 4-opt move they result from its four parameters, but 4-opt* cases result from only three parameters. Therefore number of cases (types of reconnection) of a move in 4-opt* is reduced compared to the number of cases in standard 4-opt. For example double bridge cannot be made in 4-opt*).

Moreover, value of j is obtained from: j = i + u, where u <= w and w is some arbitrary number chosen by the developer or a user and usually relatively small compared to N (for example: 10, 15 or 20). Therefore for given u the procedure considers only O(N²) choices, changing values of i and k. This way we consider links at the ends of two not overlaping chains: from position i to i+u+1, and from position k to k+2.

The 4-opt* algorithm starts with u=1 and considers all choices of such two chains of cities. If an improvement is found then it is immediately applied and searching is repeated. When no improvement is found then u is incremented by 1 and the same process is repeated. When the process of improvimg for u==w is finished, then u is reset to 1 and the same procedure is applied once again, until there is no improvement in such full round.

improved = false
while not improved:
  u = 1
  improved = false
  while u <= w:
    block two_loops:
      for i in ... :
        j = i + u
        ...
        for k in ... :
          ...
          # additional speed-up
          ...
          for case_of_move in ... :
            gain = Gain_From_4optAsterisk(i, j, k, case_of_move)
            if gain > 0:
              Make_4optAsterisk_Move(i, j, k, case_of_move)
              improved = true
              break two_loops
    #end_block two_loops
    u = u + 1
  #end_while u loop