Posted By

mertnuhoglu on 11/03/07

Who likes this?

2 people have marked this snippet as a favorite

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

/ Published in: MatLab   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)
28. n=length(distances);
29. if nargin < 2
30. idx_initial_city=ceil(rand(1)*n);
31. end
32. path=[];
33. outside=(1:n);
35. for i = 1:n-1
36. entering_city=nearest_neighbor(distances,path(end),outside);
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.
57. function positions = read_location_data(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)
86. n=length(distances);
87. if nargin < 3
88. idx_initial_city=ceil(rand(1)*n);
89. end
90. path=[];
91. outside=(1:n);
93. for i = 1:n-1
94. entering_city=insertion_rule(path,outside,distances);
95. entry_position=find_entry_position(distances,entering_city,path);
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 Subscribe to comments
Posted By: mertnuhoglu on September 30, 2008

I put all the data files under http://sites.google.com/site/mertnuhoglu/programming/files/ie517-heuristics

Posted By: acl on December 3, 2008

Hey, I need help in running this program. I'm currently working on a document delivery program for Clemson University, and I have a shortest path matrix ready to go, but I don't understand why you have three files being input into this program. Any advice would be very very much appreciated.

Andy

Posted By: mertnuhoglu on September 2, 2009

Hi, sorry for late reply. I haven't noticed the question. The files input into the program are just data files for the sample problems. You can change the input as you wish. I put them to show the data format required. Data files reside in: http://sites.google.com/site/mertnuhoglu/programming/files/ie517-heuristics