%?Travelling?Sales?man?problem?using?Tabu?Search使用禁忌搜索的旅行商問題
%?This?assumes?the?distance?matrix?is?symmetric假設距離矩陣是對稱的
%?Tour?always?starts?from?node?1旅行總是開始從節點1開始
%?**********Read?distance?（cost）?matrix?from?Excel?sheet?“data.xls“******讀取距離（成本）矩陣從Excel表”數據.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;最后訪問節點為K
%shortest?path?from?last?visited?node?is?always?1?where?the?tour旅行商最后一次訪問節點的最短路徑總是1
%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節點1總是固定為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初始化禁忌表”tabu_tenure”給出的迭代次數
%?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:100%迭代次數
fprintf（‘\n*****iteration?number?=?%d*****\n‘?iter）;
nbr?=[];
%?*******************Find?all?neighbours?to?current?tour?by?an?exchange通過變換尋找當前位置的所有鄰居
%******************between?each?pair?of?nodes**************