Shortest path heuristics (nearest neighborhood, 2 opt, farthest and arbitrary insertion) for travelling salesman problem


/ Published in: MatLab
Save to your folder(s)



Copy this code and paste it in your HTML
  1. --- do_experiments.m
  2. % Usage of heuristics in console:
  3. % [p,l,d]=shortest_path('d198.txt');
  4. % [p2,l2,d2]=insertion_heuristics('d198.txt',@farthest_insertion);
  5. % [p2,l2,d2]=insertion_heuristics('d198.txt',@arbitrary_insertion);
  6.  
  7. function results=do_experiments()
  8. data_files={'d198.txt';'d1291.txt';'rat575.txt'};
  9. number_of_experiments=10;
  10. results=[];
  11. for idx_data=1:length(data_files)
  12. for i=1:number_of_experiments
  13. data=char(data_files(idx_data));
  14. [path,total_length(1),dist]=shortest_path(data);
  15. [path,total_length(2)]=opt2(path,dist);
  16. [path,total_length(3),dist]=insertion_heuristics(data,@farthest_insertion);
  17. [path,total_length(4)]=opt2(path,dist);
  18. [path,total_length(5),dist]=insertion_heuristics(data,@arbitrary_insertion);
  19. [path,total_length(6)]=opt2(path,dist);
  20. results(i+(idx_data-1)*number_of_experiments,:)=total_length;
  21. end
  22. end
  23.  
  24. --- shortest_path.m
  25. % calculates shortest path using nearest neighborhood
  26. function [path,total_length,distances] = shortest_path(data_file,idx_initial_city)
  27. distances=distance(read_location_data(data_file));
  28. n=length(distances);
  29. if nargin < 2
  30. idx_initial_city=ceil(rand(1)*n);
  31. end
  32. path=[];
  33. outside=(1:n);
  34. [path,outside]=add_to_path(path,outside,outside(idx_initial_city));
  35. for i = 1:n-1
  36. entering_city=nearest_neighbor(distances,path(end),outside);
  37. [path,outside]=add_to_path(path,outside,entering_city);
  38. end
  39. total_length=total_length_of_cycle(distances,path);
  40.  
  41. function [path,outside] = add_to_path(path,outside,city)
  42. path(end+1)=city;
  43. outside(outside==city)=[];
  44.  
  45. --- distance.m
  46. function d = distance(a)
  47. n=length(a);
  48. d=zeros(n,n);
  49. for i = 1:n
  50. for j = i+1:n
  51. d(i,j)=norm(a(i,:)-a(j,:));
  52. d(j,i)=d(i,j);
  53. end;
  54. end;
  55.  
  56. --- read_location_data.m
  57. function positions = read_location_data(data_file)
  58. load(data_file);
  59. filename=regexp(data_file,'\w*(?=\.)','match');
  60. positions=eval(filename{1});
  61.  
  62. --- nearest_neighbor.m
  63. function nearest_city = nearest_neighbor(distances,last_city,outside)
  64. min_distance = inf;
  65. for j=1:length(outside)
  66. neighbors_distance = distances(outside(j),last_city);
  67. if neighbors_distance < min_distance
  68. min_distance = neighbors_distance;
  69. nearest_city = outside(j);
  70. end
  71. end
  72. end
  73.  
  74. --- total_length_of_cycle.m
  75. function total_length = total_length_of_cycle(distances,path)
  76. total_length = 0;
  77. for i = 1:length(path)-1
  78. total_length = total_length + distances(path(i),path(i+1));
  79. end
  80. total_length = total_length + distances(path(end),path(1));
  81.  
  82. --- insertion_heuristics.m
  83. % generic insertion algorithm
  84. function [path,total_length,distances] = insertion_heuristics(data_file,insertion_rule,idx_initial_city)
  85. distances=distance(read_location_data(data_file));
  86. n=length(distances);
  87. if nargin < 3
  88. idx_initial_city=ceil(rand(1)*n);
  89. end
  90. path=[];
  91. outside=(1:n);
  92. [path,outside]=add_to_path(path,outside,outside(idx_initial_city),1);
  93. for i = 1:n-1
  94. entering_city=insertion_rule(path,outside,distances);
  95. entry_position=find_entry_position(distances,entering_city,path);
  96. [path,outside]=add_to_path(path,outside,entering_city,entry_position);
  97. end
  98. total_length=total_length_of_cycle(distances,path);
  99.  
  100. function [path,outside] = add_to_path(path,outside,entering_city,entry_position)
  101. old_path=path;
  102. outside(outside==entering_city)=[];
  103. path(entry_position)=entering_city;
  104. for i=entry_position:length(old_path)
  105. path(i+1)=old_path(i);
  106. end
  107.  
  108. function entry_position=find_entry_position(distances,entering_city,path)
  109. min_increase_in_length = inf;
  110. global path_length
  111. path_length = length(path);
  112. for i=1:path_length
  113. before = distances(path(i),path(r(i+1)));
  114. after = distances(entering_city,path(i))+distances(entering_city,path(r(i+1)));
  115. increase_in_length = after-before;
  116. if increase_in_length < min_increase_in_length
  117. min_increase_in_length = increase_in_length;
  118. entry_position = r(i+1);
  119. end
  120. end
  121.  
  122. % if index is greater than the path length, turn the index for one round
  123. function result = r(index)
  124. global path_length
  125. if index > path_length
  126. result = index - path_length;
  127. else
  128. result = index;
  129. end
  130.  
  131. --- farthest_insertion.m
  132. function entering_city=farthest_insertion(path,outside,distances)
  133. max_distance=0;
  134. for i=1:length(path)
  135. for j=1:length(outside)
  136. if distances(path(i),outside(j)) > max_distance
  137. max_distance=distances(path(i),outside(j));
  138. entering_city=outside(j);
  139. end
  140. end
  141. end
  142.  
  143. --- arbitrary_insertion.m
  144. function entering_city = arbitrary_insertion(path,outside,distances)
  145. entering_city=outside(ceil(rand(1)*length(outside)));
  146.  
  147. --- opt2.m
  148. function [path,total_length] = opt2(path,distances)
  149. global n
  150. n = length(path);
  151. for i=1:n
  152. for j=1:n-3
  153. if change_in_path_length(path,i,j,distances) < 0
  154. path=change_path(path,i,j);
  155. end
  156. end
  157. end
  158. total_length = total_length_of_cycle(distances,path);
  159.  
  160. function result = change_in_path_length(path,i,j,distances)
  161. before=distances(path(r(i)),path(r(i+1)))+distances(path(r(i+1+j)),path(r(i+2+j)));
  162. after=distances(path(r(i)),path(r(i+1+j)))+distances(path(r(i+1)),path(r(i+2+j)));
  163. result=after-before;
  164.  
  165. function path = change_path(path,i,j)
  166. old_path=path;
  167. % exchange edge cities
  168. path(r(i+1))=old_path(r(i+1+j));
  169. path(r(i+1+j))=old_path(r(i+1));
  170. % change direction of intermediate path
  171. for k=1:j-1
  172. path(r(i+1+k))=old_path(r(i+1+j-k));
  173. end
  174.  
  175. % if index is greater than the path length, turn index one round off
  176. function result = r(index)
  177. global n
  178. if index > n
  179. result = index - n;
  180. else
  181. result = index;
  182. end

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.