%?Travelling?Sales?man?problem?using?Tabu?Search
%?This?assumes?the?distance?matrix?is?symmetric
%?Tour?always?starts?from?node?1
%?**********Read?distance?（cost）?matrix?from?Excel?sheet?“data.xls“******
clearclc;
d?=?xlsread（‘tsp_data.xls‘）;
d_orig?=?d;
start_time?=?cputime;
dim1?=?size（d1）;
dim12?=?size（d）;
for?i=1:dim1
d（ii）=10e+06;
end
%?*****************Initialise?all?parameters**********************
d1=d;
tour?=?zeros（dim12）;
cost?=?0;
min_dist=[?];
short_path=[?];
best_nbr_cost?=?0;
best_nbr?=?[?];
%?*******Generate?Initial?solution?-?find?shortest?path?from?each?node****
%?if?node?pair?1-2?is?selected?make?distance?from?2?to?each?of?earlier
%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（（d1（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（k1）=10e+06;
for?visited_node?=?1:length（short_path）;?
d1（kshort_path（visited_node））=10e+06;
end
end
tour（1short_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（kshort_path（last_indx））=1;
cost?=?cost+d（k1）;
%?A?tour?is?represented?as?a?sequence?of?nodes?startig?from?second?node?（as
%?node?1?is?always?fixed?to?be?1
crnt_tour?=?short_path;
best_tour?=?short_path;
best_obj?=cost;
crnt_tour_cost?=?cost;
fprintf（‘\nInitial?solution\n‘）;
crnt_tour
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?forbidden?from?exchange
tabu_tenure?=?zeros（dim12）;
max_tabu_tenure?=?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（ii）=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?objective?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?object?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-i==1
nbr_cost（crnt_tour（i）crnt_tour（j））=crnt_tour_cost-d（1crnt_tour（i））+...
d（1crnt_tour（j））-?d（crnt_tour（j）crnt_tour（j+1））+d（crnt_tour（i）crnt_tour（j+1））;
best_i=i;
best_

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????24576??2011-10-16?21:42??tsp_data.xls
?????文件????????9111??2011-10-16?22:11??taboo_tsp.m