Lin-Kernighan algorithm basics – part 10

When using DLB and subsequent moves we need a variable and a pair of procs to save and restore DLB array:

var
  DontLook_copy: DLB_Array

proc Save_DLB() =
  DontLook_copy = DontLook

proc Restore_DLB() =
  DontLook = DontLook_copy

The last part contains some additional constants, variables and procs used to maintain subsequent moves:

var
  Max_Depth:int = 55
var
  SubseqLvl: int
type
  Link = array[0..1, City_Number]
var
  linksAdded: array[0 .. N-1, Link]
  linksAdded_Len: int = 0

proc LinksAddedClear() =
  linksAdded_Len = 0
  
proc AddToLinksAdded(city_A, city_B: City_Number) =
  var
    city_L, city_R: City_Number
  if city_A < city_B:
    city_L = city_A
    city_R = city_B
  else:
    city_L = city_B
    city_R = city_A
  linksAdded[linksAdded_Len] = [city_L, city_R]
  linksAdded_Len = linksAdded_Len + 1
  
proc isLinkAdded(city_A, city_B: City_Number): bool =
  var
    city_L, city_R: City_Number
  if city_A < city_B:
    city_L = city_A
    city_R = city_B
  else:
    city_L = city_B
    city_R = city_A
  result = false
  for idx in 0 .. linksAdded_Len-1:
    if (city_L == linksAdded[idx][0] and
        city_R == linksAdded[idx][1]):
       result = true
       break
  #end_loop idx

Note that procs for saving and restoring tour are not efficient. They can be replaced by procs for storing and "undoing" exchanges made, but this would reuquire additional means to make sure that recognized type of sequence does not change or is updated.

var
  t_copy: Tour_Array
  p_copy: City_Position_In_Tour
  l_copy: Length

proc Save_Tour() =
  t_copy = tour
  p_copy = position
  l_copy = tourLen
  
proc Restore_Tour() =
  tour     = t_copy
  position = p_copy
  tourLen  = l_copy

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 3-opt with neighbor lists and simple Lin-Kernighan implementation. (Note that this 3-opt implementation uses slower method of applying moves than that in LK.) Neighbor lists size=24, LK breadth=(5, 5 ,3), LK depth=55. Random planar problems, N=100.

Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	109.45	117.82
	3opt-ND(24)	4881	85.95	87.32	90.41
	LK 4+2	2243	85.38	86.29	88.67
2	NN	100	100.00	108.00	115.44
	3opt-ND(24)	4587	86.88	88.36	91.37
	LK 4+2	1468	86.83	87.40	90.19
3	NN	100	100.00	107.33	117.17
	3opt-ND(24)	4981	84.12	85.87	89.60
	LK 4+2	2343	84.12	85.01	90.19
4	NN	100	100.00	106.75	117.44
	3opt-ND(24)	4587	87.10	89.55	92.74
	LK 4+2	2149	87.10	88.47	91.22
5	NN	100	100.00	107.14	123.30
	3opt-ND(24)	4781	89.79	91.33	93.25
	LK 4+2	2149	89.55	90.71	92.17
6	NN	100	100.00	109.40	122.11
	3opt-ND(24)	5074	86.36	87.90	90.88
	LK 4+2	2050	85.88	86.64	88.74
7	NN	100	100.00	109.81	121.38
	3opt-ND(24)	4687	91.82	92.92	96.31
	LK 4+2	1949	91.71	92.36	94.48
8	NN	100	100.00	107.21	118.20
	3opt-ND(24)	4781	87.57	88.84	90.88
	LK 4+2	2837	87.24	88.25	90.63
9	NN	100	100.00	108.36	117.82
	3opt-ND(24)	4981	88.16	89.33	91.96
	LK 4+2	1268	88.16	88.53	91.97
10	NN	100	100.00	108.14	116.89
	3opt-ND(24)	5174	88.76	90.37	93.61
	LK 4+2	2637	88.52	89.24	91.08