Node Shift

Node Shift move

Node Shift is a simple tour optimization heuristics: it consists in shifting a city to other position in tour.

The idea:

Diagrams:

Node Shift move is obtained by removing three links and adding three new links, and therefore it is a special case of 3-opt move:

Gain from Node Shift move

proc Gain_From_Node_Shift(X0_pred, X0, X0_succ,
                          Y1, Y2: City_Number): Length_Gain =
  ## Gain of tour length which can be obtained by performing Node Shift
  # City X0 would be moved from its current position, between X0_pred
  # and X0_succ, to position between cities Y1 and Y2.
  # Assumes: X0_pred!=Y1 (the same as: X0!=Y2);
  #   X0==successor(X0_pred); X0_succ==successor(X0); Y2==successor(Y1)
  let del_Length = distance(X0_pred, X0) + distance(X0, X0_succ) +
                   distance(Y1, Y2)
  let add_Length = distance(X0_pred, X0_succ) +
                   distance(Y1, X0) + distance(X0, Y2)
  result = del_Length - add_Length

Node Shift move implementation

proc Make_Node_Shift_Move(tour: var Tour_Array;
                          i, j: Tour_Index) =
  ## Performs given Node Shift move
  # Shifts the city t[i] from its current position to position
  # after current city t[j], i.e. between cities t[j] and t[j+1].
  # This is a special, simple case of segment shift, thus a special
  # case of 3-opt move.
  var
    left, right: Tour_Index
    X0: City_Number

  let shiftSize = (j - i + 1 + N) mod N

  X0 = tour[i]
  left = i
  for counter in 1 .. shiftSize:
    right = (left + 1) mod N
    tour[left] = tour[right]
    left = right
  # end_for counter loop
  tour[j] = X0

Iterative Node Shift optimization

proc LS_Node_Shift(tour: var Tour_Array) =
  ## Iteratively optimizes given tour using Node_Shift moves.
  # Shortens tour by repeating Node Shift 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, Y1, Y2: City_Number

  while not locallyOptimal:
    locallyOptimal = true

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

      for counter_2 in 1 .. N-2:
        j  = (i + counter_2) mod N  # new position of the city
        Y1 = tour[j]
        Y2 = tour[(j + 1) mod N]

        if Gain_From_Node_Shift(X0_pred, X0, X0_succ, Y1, Y2) > 0:
          Make_Node_Shift_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 2-opt plus Node Shift algorithms. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	106.01	114.87
	NN + 2opt	1253	84.38	89.83	96.82
	NN + 2opt + NodeShift	1459	83.94	87.90	91.71
2	NN	100	100.00	107.45	116.93
	NN + 2opt	1562	88.05	92.40	96.60
	NN + 2opt + NodeShift	1562	87.16	90.34	94.04
3	NN	100	100.00	111.21	121.46
	NN + 2opt	1566	87.41	91.52	95.76
	NN + 2opt + NodeShift	1666	84.99	88.79	92.92
4	NN	100	100.00	106.14	116.83
	NN + 2opt	1146	90.52	93.42	96.88
	NN + 2opt + NodeShift	1353	90.18	91.90	95.45
5	NN	100	100.00	106.30	111.75
	NN + 2opt	833	89.63	93.35	98.55
	NN + 2opt + NodeShift	1253	88.58	91.68	95.80
6	NN	100	100.00	112.73	120.18
	NN + 2opt	1253	89.46	93.60	98.49
	NN + 2opt + NodeShift	1459	88.27	92.00	96.30
7	NN	100	100.00	109.50	124.34
	NN + 2opt	1460	88.66	91.05	96.24
	NN + 2opt + NodeShift	1566	86.47	89.27	92.40
8	NN	100	100.00	108.63	117.53
	NN + 2opt	1146	92.47	96.80	102.24
	NN + 2opt + NodeShift	1566	91.86	95.44	101.14
9	NN	100	100.00	105.75	112.56
	NN + 2opt	400	88.70	91.68	96.63
	NN + 2opt + NodeShift	465	87.85	90.03	94.57
10	NN	100	100.00	115.43	123.97
	NN + 2opt	1460	91.77	95.11	100.35
	NN + 2opt + NodeShift	1459	90.88	93.87	98.72