1.程序功能描述
基于禁忌搜索算法的TSP問題最優路徑搜索，旅行商問題（TSP）是一個經典的組合優化問題。其起源可以追溯到 19 世紀初，最初是在物流配送、線路規劃等實際場景中被提出。簡單來說，給定一組城市和城市之間的距離，旅行商需要從一個城市出發，訪問每個城市恰好一次，最后回到起始城市，目標是找到總路程最短的路線。

2.測試軟件版本以及運行結果展示
MATLAB2022A版本運行

3.核心程序

% 定義城市的數量為 30
Ncity = 30; 
% 定義裝卸速度為 0.8
v1    = 0.8; %裝卸速度
% 定義行車速度為 20
v2    = 20; %行車速度
% 定義固定損耗成本為 20
c     = 20; %固定損耗成本
% 定義車損與載重質量的損耗系數為 0.025
r     = 0.025; %車損與載重質量的損耗系數
% 生成裝貨時間數組，第一個和最后一個元素為 0，中間元素為隨機數
q     = [0,10*rand(1,Ncity-2),0]; %裝貨時間
% 生成等待時間數組，第一個元素為 0，其余元素為隨機數
t1    = [0,20*rand(1,Ncity-1)]; %等待時間
% 生成最晚時間窗數組，元素為隨機數
t2    = [50*rand(1,Ncity-1)]; %最晚時間窗
% 生成城市坐標矩陣，第一個和最后一個坐標為特定值，中間元素為隨機數
Clist = [[5000,4000];6000*rand(Ncity-2,2);[5500,2500]]; 
% 初始化距離矩陣 Mlist
for i=1:Ncity
    for j=1:Ncity
        % 計算城市 i 和城市 j 之間的歐幾里得距離，并存儲在 Mlist 中
        Mlist(i,j) = sqrt((Clist(i,1)-Clist(j,1))^2 + (Clist(i,2)-Clist(j,2))^2); 
    end
end
 
...............................................................................
% 創建新的圖形窗口
figure; 
% 用紅色繪制最優成本的變化曲線，線寬為 2
plot(yfitsave,'r','LineWidth',2); 
hold on; 
% 用藍色繪制當前解的適應度變化曲線，線寬為 2
plot(tmps2,'b','LineWidth',2); 
% 顯示網格
grid; 
% 顯示圖例，區分最優解和當前解
legend('最優解','當前解'); 

4.本算法原理
禁忌搜索（Tabu Search，TS）算法是一種元啟發式算法，它最早由 Fred Glover 在 1986 年提出。它的靈感來源于人們在解決復雜問題時的記憶和避免重復錯誤的行為。最初用于解決整數規劃問題，后來被廣泛應用于各種組合優化問題，包括 TSP。隨著研究的深入，學者們對禁忌搜索算法進行了諸多改進，如改進禁忌列表的結構、動態調整禁忌長度等，以提高算法的性能。

禁忌列表（Tabu List）

禁忌列表是禁忌搜索算法的核心概念之一。它是一個存儲結構，用于記錄最近訪問過的解或移動操作，以避免算法在短時間內重復訪問這些解或執行相同的操作。通過禁止算法在一定步數內再次訪問禁忌列表中的元素，使得搜索過程能夠跳出局部最優解，增加搜索的多樣性。例如，在 TSP 中，如果剛剛交換了城市和城市的訪問順序，那么在禁忌列表規定的禁忌期內，禁止再次交換這兩個城市的順序。

假設禁忌列表是一個先進先出（FIFO）的隊列。當執行一個移動操作（如交換兩個城市的訪問順序）時，將這個操作記錄在禁忌列表的頭部。在每次選擇新的移動操作時，檢查該操作是否在禁忌列表中。如果在禁忌列表中，根據藐視準則（后面會介紹）來決定是否仍然執行這個操作。

禁忌長度（Tabu Tenure）

禁忌長度是指一個解或移動操作在禁忌列表中被禁止訪問或執行的步數。它是一個重要的參數，直接影響算法的搜索能力。對搜索能力的影響：如果禁忌長度太短，算法可能會很快重新訪問之前的解，陷入局部最優解；如果禁忌長度太長，可能會過度限制搜索空間，導致算法搜索效率低下，錯過一些潛在的好解。例如，在 TSP 中，如果禁忌長度設置為 1，那么可能剛剛禁止交換兩個城市的順序，下一次就又可以交換了，這樣很難跳出局部最優；而如果禁忌長度設置為（為城市數量，這是所有可能的城市交換操作的數量），那么算法可能會在很長時間內無法訪問一些可能的好解。

確定合適的禁忌長度可以通過實驗和經驗來選擇。一種常見的方法是根據問題的規模和性質，設置禁忌長度為一個與問題規模相關的函數。例如，在 TSP 中，可以設置禁忌長度為（為城市數量），并在算法運行過程中根據搜索情況動態調整。

藐視準則（Aspiration Criterion）

藐視準則是一種機制，用于在某些情況下允許算法訪問禁忌列表中的解。當一個禁忌解滿足一定的條件時，算法可以選擇這個解，即使它在禁忌列表中。

它可以避免算法因為過度禁忌而錯過一些可能是全局最優的解。例如，在 TSP 中，如果一個被禁忌的城市交換操作能夠產生一個比當前找到的最優解還要好的解，那么根據藐視準則，算法可以執行這個操作。