%travelling sales man problem using tabu search
%this assumes the distance matrix is symmetric
%tour always strats from node 1
%*********read distance (cost) matrix from excel sheel "data.xls" *********
d = xlsread('input_data127.xls');
d_orig = d;
start_time = cputime;
dim1 = size(d,1);
dim12 = size(d);
for i = 1:dim1
d(i,i+1) = 10e+06;
end
%**********initialise all parameters*********
d1 = d;
tour = zeros(dim12);
cost = 0;
min_dist = [];
short_path = [];
beat_nbr_cost = 0;
beat_nbr = [];
%**********generate initial solution*********
%if node pair 1-2 is selected, make distance from 2 to each of ealier
%visited nodes very high to avoid a subtour
k = 1;
for i = 1:dim1 -1;
min_dist(i) = min(d1(k,:));
short_path(i) = find((di(k,:) == min_dist(i)),1);
cost = cost + min_dist(i);
k = short_path(i);
%prohibit all paths from current visited node to all earlier visited
%nodes
d1(k,1) = 10e+06;
for visited_node = 1:length(short_path);
d1(k,short_path(visited_node)) = 10e+06;
end
end
tour(1,short_path(1)) = 1;
for i = 2:dim1 - 1
tour(short_path(i-1),short_path(i)) = 1;
end
%last visited node is k
%shortest path from last visited node is always 1, where the tour
%originally started from
last_indx = length(short_path) + 1;
short_path(last_indx) = 1;
tour(k,short_path(last_indx)) = 1;
cost = cost + d(k,1);
%a tour is represented as a sequence of nodes staring from second node( as
%node 1 is always fixed to be 1
crnt_tour = short_path;
beat_tour = short_path;
best_obj = cost;
crnt_tour_cost = cost;
fprintf('\nIntitial solution\n');
fprintf('\nInitial tour cost = %d\t',crnt_tour_cost);
nbr_cost = [];
%Initialize tabu list "tabu_tenure" giving the number of iterations for
%which a particular pair of nodes are foridden from exchange
tabu_tenure = zeros(dim12);
max_tabu_trnure = round(sqrt(dim1));
%max_tabu_tenure = dim1;
penalty = zeros(1,(dim1-1)*(dim1-2)/2);
frequency = zeros(dim12);
frequency(1,:) = 100000;
frequency(:,1) = 100000;
for i=1:dim1
frequency(i,i) = 100000;
end
iter_snc_last_imprv = 0;
%*********perform the iteration until one of the criteria is met *********
%1.max number of iterations reached
%2.iterations since last improvement in the best obj found so far reaches a
%threshold
best_nbr = crnt_tour;
for iter = 1:10000
fprintf('\n***iteration number = %d ****\n',iter);
nbr = [];
%find all neighbours to current tour by an exchange between each pair
%of nodes
%calculate the obj value(cost) for each of the neighbours
nbr_cost = inf(dim12);
for i = 1:dim1 -2
for j = i+1:dim1 -1
if i == 1
if j-1 == 1
nbr_cost(crnt_tour(i),crnt_tour(j)) = crnt_tour_cost...,
-d(1,crnt_tour(i))+d(1,crnt_tour(j))...,
-d(crnt_tour(j),crnt_tour(j+1))...,
+ d(crnt_tour(i),crnt_tour(j+1));
best_i = i;
bast_j = j;
best_nbr_cost = nbr_cost(crnt_tour(i),crnt_tour(j));
tabu_node1 = crnt_tour(i);
tabu_node2 = crnt_tour(j);
else
nbr_cost(crnt_tour(i),crnt_tour(j)) = crnt_tour_cost...,
-d(1,crnt_tour(i))+d(1,crnt_tour(j))...,
-d(crnt_tour(j),crnt_tour(j+1))...,
+ d(crnt_tour(i),crnt_tour(j+1))...,
- d(crnt_tour(i),crnt_tour(i+1))...,
+ d(crnt_tour(j),crnt_tour(i+1))...,
- d(crnt_tour(j-1),crnt_tour(j))...,
+ d(crnt_tour(j-1),crnt_tour(i));
end
else
if j-i ==1
nbr_cost(crnt_tour(i),crnt_tour(j)) = crnt_tour_cost ...,
-d(crnt_tour(i-1),crnt_tour(i))...,
+d(crnt_tour(i-1),crnt_tour(j))...,
- d(crnt_tour(j),crnt_tour(j+1)) ...,
+ d(crnt_tour(i),crnt_tour(j+1));
else
nbr_cost(crnt_tour(i),crnt_tour(j)) = crnt_tour_cost ...,
-d(crnt_tour(i-1),crnt_tour(i))...,
+d(crnt_tour(i-1),crnt_tour(j))...,
- d(crnt_tour(j),crnt_tour(j+1)) ...,
+ d(crnt_tour(i),crnt_tour(j+1))...,
-d(crnt_tour(i),crnt_tour(i+1))...,
+d(crnt_tour(j),crnt_tour(i+1)) ...,
-d(crnt_tour(j-1),crnt_tour(j))...,
+d(crnt_tour(j-1),crnt_tour(i));
end
end
if nbr_cost(crnt_tour(i),crnt_tour(j)) < best_nbr_cost
best_nbr_cost = nbr_cost(crnt_tour(i),crnt_tour(j));
best_i = i;
best_j = j;
tabu_node = crnt_tour(i);
tabu_node2 = crnt_tour(j);
end
end
end
%*********nrighbourhood cost calculation ends here*********
best_nbr(best_i) = crnt_tour(best_j);
best_nbr(best_j) = crnt_tour(best_i);
%********enter it in tabu list*********
%label tabu nodes such that tabu node2 is always greater than tabu
%node1. this is required to keep recency based and frequenycy based
%tabu list in the same data structure. recency based list is in the
%space above the main diagnoal of the tabu tenure matrix and frequency
%based tabu list is in the space below the main digonal
%
%find the best nrighbour that does not involve swaps in tabu list
%*****override tabu if aspriration criteria met**
%***aspiration criteria is met if a tabu member is better than the best
%solution found so far
%while(tabu_tenure(tabu_node1,tabu_node2)|tabu_tenure(tabu_node2,tabu_node1))>0
while(tabu_tenure(tabu_node1,tabu_node2)) > 0
if beat_nbr_cost < best_obj
%tabu solution better than the best found so far
fprintf('\n best nbr cost = %d\t and best obj = %d\n, hence breaking',best_nbr_cost,best_obj);
break;
else
%****make the cost of tabu move prohibitively high to disallow
%its selection and look for the next best neighbour that is not
%tabu active
nbr_cost(tabu_node1,tabu_node2) = ...,
nbr_cost(tabu_node1,tabu_node2)*1000;
best_nbr_cost_col = min(nbr_cost);
best_nbr_cost = min(best_nbr_cost_col);
[R,C] = find((nbr_cost==best_nbr_cost),1);
tabu_node1 = R;
tabu_node2 = C;
end
end
%*********continuous diversification when best nbr cost gt crnt
%tour cost by penalising obj by frequency of moves
if best_nbr_cost > crnt_tour_cost
fprintf('\nbest nrighbor cost greater than tour cost\n');
min_d_col = min(d);
penal_nbr_cost = nbr_cost + min(min_d_col)*frequency;
penal_best_nbr_cost_col = min(penal_nbr_cost);
penal_best_nbr_cost = min(penal_best_nbr_cost_col);
[Rp,Cp] = find((penal_nbr_cost==penal_best_nbr_cost),1);
tabu_node1 = Rp;
tabu_node2 = Cp;
best_nbr_cost = nbr_cost(tabu_node1,tabu_node2);
end
%*******decrease all tabu tenures by 1
for row = 1:dim1-1
for col = row+1:dim1
if tabu_tenure(row,col) > 0
tabu_tenure(row,col) = tabu_tenure(row,col)-1;
tabu_tenure(col,row) = tabu_tenure(row,col);
end
end
end
%*****recency tabu********
%enter current moves in tabu list with tenure=max tenure
tabu_tenure(tabu_node1,tabu_node2) = max_tabu_tenure;
tabu_tenure(tabu_node2,tabu_node1) = tabu_tenure(tabu_node
评论0