Thursday, March 30, 2017

2-opt with Neighbor Lists and Don't Look Bits

proc One_City_2_Opt_ND(tour: var Tour_Array;
                       basePos: Tour_Index;
                       neighbor: Neighbor_Matrix;
                       position: var City_Position_In_Tour;
                       numberOfNeigbors: int;
                       DontLook: var DLB_Array): bool =
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number

  improved = false
  block two_loops:
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
      else:
        i  = (N + basePos - 1) mod N
        X2 = tour[i]
        X1 = tour[(i+1) mod N]  # == tour[basePos]

      for neighbor_number in 0 .. numberOfNeigbors-1:
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          continue

        if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
          Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
          Make_2_Opt_Move(tour, i, j, position)
          improved = true
          break two_loops
  result = improved
proc LS_2_Opt_ND(tour: var Tour_Array;
                 neighbor: Neighbor_Matrix;
                 neighborListLen: int = N-1) =
  ## Optimizes the given tour using 2-opt with neighbor lists
  ## and dDon't Look Bits (DLB)
  var
    locallyOptimal: bool = false
    improved: bool
    DontLook: DLB_Array
    baseCity: City_Number
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)

  Set_DLB_off(DontLook, tour)
  
  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      if isDLB_on(DontLook, baseCity):
        continue
      improved = One_City_2_Opt_ND(tour, basePos, neighbor, position,
                                   numberOfNeigbors, DontLook)
      if not improved:
        Set_DLB_on(DontLook, baseCity)
      else:
        locallyOptimal = false

2 comments:

  1. Hello,

    I am currently working on my Master's Thesis and this site has helped me a lot. To the best of my knowledge, I have not been able to find so much information about local heuristic search methods for TSP as there is here. In addition, everything is written very clearly and precise. I implemented 2-OPT with DLB and neighbours list as shown in this article and it runs perfect (although I had to debug and change some lines depending on how you treat cities, etc).

    Again, thank you very much for your efforts to put up a site like this. May I ask if you work in a Spanish University?

    Thank you,
    Esteban

    ReplyDelete
  2. I'm glad to hear that, Esteban. No, I don't live nor work in Spain.

    Greetings,
    W.K.

    ReplyDelete