Wednesday, May 17, 2017

3-opt symmetric move speedup

p1 p2 p3 p4 p5 p6 A B C
p1 p2 p3 p4 p5 p6
proc Make_3_Opt_Sym_Move_Fast(tour: var Tour_Array;
                              p1, p2, p3, p4, p5, p6: Tour_Index;
                              position: var City_Position_In_Tour) =

  let size_A = (N + p1 - p6 + 1) mod N
  let size_B = (N + p3 - p2 + 1) mod N
  let size_C = (N + p5 - p4 + 1) mod N

  if size_A > size_B + size_C:
    Swap_Segments(tour, p2, p3, p4, p5, position)
  elif size_B > size_A + size_C:
    Swap_Segments(tour, p4, p5, p6, p1, position)
  elif size_C > size_A + size_B:
    Swap_Segments(tour, p6, p1, p2, p3, position)
  else:
    Reverse_Segment(tour, p2, p3, position)
    Reverse_Segment(tour, p4, p5, position)
    Reverse_Segment(tour, p6, p1, position)

No comments:

Post a Comment