Node Swap

Node Swap move

Node Swap is a simple tour optimization heuristics: it consists in swapping two cities in tour.

The idea:

Diagrams:

Node Swap move is a special case of two subsequent 2-opt moves: the first including both cities and the second without them. It involves removing four links and adding four new links, therefore is a specific type of 4-opt move.

Gain from Node Swap move

proc Gain_From_Node_Swap(X0_pred, X0, X0_succ,
                         Y0_pred, Y0, Y0_succ: City_Number): Length_Gain =
  ## Gain of tour length which can be obtained by performing Node Swap
  ## City X0 would be moved from its current position, between X0_pred
  ## and X0_succ, to the position of city Y0 and vice versa
  # Assumes: X0!=Y0
  #          X0=successor(X0_pred); X0_succ==successor(X0);
  #          Y0=successor(Y0_pred); Y0_succ==successor(Y0);
  var
    del_Length, add_Length: Length_Gain
  if (Y0==X0_succ) or (X0_succ==Y0_pred):
    del_Length = distance(X0_pred, X0) + distance(Y0, Y0_succ)
    add_Length = distance(X0_pred, Y0) + distance(X0, Y0_succ)
  elif (X0==Y0_succ) or (Y0_succ==X0_pred):
    del_Length = distance(Y0_pred, Y0) + distance(X0, X0_succ)
    add_Length = distance(Y0_pred, X0) + distance(Y0, X0_succ)
  else:
    del_Length = distance(X0_pred, X0) + distance(X0, X0_succ) +
                 distance(Y0_pred, Y0) + distance(Y0, Y0_succ)
    add_Length = distance(X0_pred, Y0) + distance(Y0, X0_succ) +
                 distance(Y0_pred, X0) + distance(X0, Y0_succ)
  #end_if
  result = del_Length - add_Length

Node Swap move implementation

proc Make_Node_Swap_Move(tour: var Tour_Array;
                         i, j: Tour_Index) =
  ## Performs given Node Swap move: swaps city t[i] with city city t[j]
  # This is a special, simple case of two subsequent 2-opt moves:
  # the first including both cities and the second without them
  #   -a-t[i]-b-t[j]-a-
  #   -a-(t[i]-b-t[j])'-a-  == -a-t[j]-b'-t[i]-a-
  #   -a-t[j]-(b')'-t[i]-a- == -a-t[j]-b-t[i]-a-
  swap(tour[i], tour[j])

Iterative Node Swap optimization

proc LS_Node_Swap(tour: var Tour_Array) =
  ## Optimizes the given tour using Node_Swap.
  # Shortens tour by repeating Node Swap moves until no improvement
  # can by done: in every iteration immediatelly makes permanent
  # the first move found that gives any length gain.
  var
    locallyOptimal: bool = false
    i, j: Tour_Index
    X0_pred, X0, X0_succ, Y0_pred, Y0, Y0_succ: City_Number

  while not locallyOptimal:
    locallyOptimal = true

    for counter_1 in 0 .. N-1:
      i = counter_1  # position of the first city
      X0_pred = tour[(N + i - 1) mod N]
      X0      = tour[i]
      X0_succ = tour[(i + 1) mod N]

      for counter_2 in counter_1+1 .. N-1:
        j  = counter_2  # position of the second city
        Y0_pred = tour[(N + j - 1) mod N]
        Y0 = tour[j]
        Y0_succ = tour[(j + 1) mod N]

        if Gain_From_Node_Swap(X0_pred, X0, X0_succ,
                               Y0_pred, Y0, Y0_succ) > 0:
          Make_Node_Swap_Move(tour, i, j)
          locallyOptimal = false
          break

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 Node Swap algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	107.17	119.19
	NN + 2opt	975	89.53	92.77	99.31
	NN + NodeSwap	293	94.61	103.80	116.17
2	NN	100	100.00	107.49	118.89
	NN + 2opt	1146	90.78	94.51	98.18
	NN + NodeSwap	419	95.23	101.53	110.37
3	NN	100	100.00	107.68	114.62
	NN + 2opt	1175	89.97	93.08	97.98
	NN + NodeSwap	293	94.55	102.50	111.75
4	NN	100	100.00	109.62	122.88
	NN + 2opt	1075	90.74	93.55	98.18
	NN + NodeSwap	293	97.54	106.47	118.40
5	NN	100	100.00	106.67	113.50
	NN + 2opt	1175	90.90	93.91	97.43
	NN + NodeSwap	293	94.35	101.54	107.83
6	NN	100	100.00	109.94	120.93
	NN + 2opt	1253	87.14	90.84	97.60
	NN + NodeSwap	419	93.50	101.63	110.62
7	NN	100	100.00	109.60	121.26
	NN + 2opt	1460	86.22	90.32	94.58
	NN + NodeSwap	420	95.34	103.06	114.27
8	NN	100	100.00	110.14	121.53
	NN + 2opt	975	86.05	90.92	98.23
	NN + NodeSwap	487	91.82	105.68	115.13
9	NN	100	100.00	110.14	121.53
	NN + 2opt	1075	86.05	90.92	98.23
	NN + NodeSwap	393	91.82	105.68	115.13
10	NN	100	100.00	111.65	120.86
	NN + 2opt	833	95.09	97.70	102.49
	NN + NodeSwap	419	97.68	106.43	117.24