改進禁忌搜索算法求解CVRP問題

李佳慧，姜志俠

（長春理工大學 理學院，長春 130022）

近年來隨著國民經濟增長方式的轉變，結構調整的穩步推進，產業結構的不斷優化，物流業作為各行業的輔助行業已滲透到了各類經濟領域中，它跟隨著其他行業的發展而發展，雖然現代物流業的服務水平在逐漸提高，但是物流成本高一直以來都是國家和物流企業所關注的重點問題。車輛路徑問題[1]（Vehicle Routing Prob?lem，VRP）作為物流配送中的一個核心問題，受到了廣泛的關注。

1 相關工作

帶容量限制的車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP）是車輛路徑問題研究的基本問題之一，它是旅行商問題（Traveling Salesman Problem，TSP）的升級版，已被證明是一個NP問題。由于該問題本身的復雜性及其在現實生活中極強的實用價值，吸引了國內外廣大學者理論研究的關注，并且不斷提出各種方法及改進算法來尋求更好的解決方案。傳統的精確算法往往適用于求解小規模CVRP問題，而實際求解中問題規模較大，精確算法無法在短時間內給出較好的結果，因此啟發式算法受到了廣大研究者的青睞。張海軍等人[2]改進了蟻群算法的信息素更新方式，并且在搜索過程中與禁忌搜索算法相結合，添加新的參數記憶訪問過的客戶節點來求解CVRP問題。蔡延光等人[3]提出一種融合量子進化算法和變鄰域優化策略的變鄰域量子煙花算法求解CVRP問題，實驗結果表明所提算法具有較好的尋優能力和收斂速度。姜婷[4]為解決CVRP問題采用差分算法改進人工蜂群算法，使用全局最優解引導的鄰域搜索策略，引入差分算法的交叉更新策略進行局部優化。孫晶等人[5]采用排序的螞蟻系統更新蟻群算法的全局信息素并且設置了全局信息素的最大最小值來求解CVRP問題。

禁忌搜索算法[6]（Tabu Search，TS）在1986年由Glover提出，它區別于其他現代優化算法的顯著特征是利用記憶來引導算法的搜索過程。為了改進局部鄰域搜索容易陷入局部最優點的不足，禁忌搜索算法引入禁忌表，對已經搜索過的局部最優點進行記錄，在下次搜索中對禁忌表中的信息有選擇地進行搜索，以此跳出局部最優點，實現全局優化。迄今為止，禁忌搜索算法在組合優化和全局優化問題方面顯示了它良好的性能，已被成功應用于旅行商問題、生產調度、機器學習等領域。但是禁忌搜索算法也有明顯的不足，王永勝等人[7]通過貪心算法的思想給出較好的初始解，以禁忌搜索算法為框架，使用動態增長的禁忌長度來解決帶2維裝箱約束的車輛路徑問題，避免了迂回搜索。雷開友等人[8]提出一種在禁忌搜索集中性和多樣性自動平衡下的增強搜索策略算法，在集中性搜索與多樣性搜索之間保持合理平衡的同時，進一步對結果加強集中性搜索或多樣性搜索，以獲得全局最優解。

本文以標準禁忌搜索算法為基礎，針對禁忌搜索對初始解有較強依賴的缺陷以及算法在搜索過程中容易陷入局部最優的可能，采用I&D（Intensification and Diversification）搜索策略，首先在優良解的鄰域上進一步搜索到局部最優解結束，以實現集中性搜索的目的；然后對局部最優解進行變異以達到多樣性搜索的目的。改進的禁忌搜索算法給出兩種作用于局部最優解的變異算子來拓寬算法的搜索區域，并且針對CVRP問題設計了初始解的產生方式。

2 CVRP問題描述和數學模型

CVRP問題具體描述為：已知一定數量的客戶，各客戶點有不同的貨物需求量，配送中心向客戶提供配送服務，由若干車輛（相同型號）負責，設計最優的配送路線使得所有客戶的貨物需求得到滿足，并且使配送的總成本最低。

設G=(N，A)，N=N0?Nc，其中N0代表配送中心節點，這里只考慮一個配送中心的情況；Nc代表客戶節點，A={(i,j)|i,j∈N}表示客戶點i到客戶點j之間的有向線段。

符號說明如下：

K：配送車輛集合；

Q：車輛載重（配送車輛型號一致）；

qi：客戶點i的需求量；

dij：車輛由客戶點i行駛至客戶點j的距離成本；

nc：Nc的真子集，|nc|表示集合nc中所含元素的個數。

上述模型中，目標函數（1）考慮最小化車輛配送路徑長度；約束（2）表示配送時須滿足車輛載重限制；約束（3）表示每個客戶只能被一輛車服務；約束（4）和（5）表示同一條線路上的客戶由同一配送車輛服務且每個客戶僅被服務一次；約束（6）和（7）表示各配送車輛均從配送中心0出發，最后回到配送中心0；約束（8）用來消除客戶點之間的子回路。

3 改進禁忌搜索算法求解CVRP問題

3.1 I&D搜索策略

I&D搜索策略即集中性搜索和多樣性搜索策略。集中性搜索策略用于加強對當前搜索的優良解的鄰域做進一步更為充分的搜索，以期能找到全局最優解；多樣性搜索策略則用于拓寬搜索區域，尤其是未知區域，當搜索陷入局部最優解時，多樣性搜索可以改變搜索方向，跳出局部最優，從而實現全局優化[9]。

本文采用I&D搜索策略求解CVRP問題，基本思路如下：搜索從一點出發，在該點的鄰域內不斷尋找更好的解，達到局部最優解結束，此過程為集中性搜索。然后對已搜索到的局部最優解變異，從而實現更大區域的搜索，即多樣性搜索過程。將變異后的局部最優解作為當前解再進行集中性搜索，如此繼續下去。

改進后的算法每一次的集中性搜索都是為了提高解的質量，而每一次的多樣性搜索都是為了跳出局部最優解，達到一些沒有搜索到的點從而拓寬搜索區域。I&D搜索策略使得算法能夠從一個局部最優解迅速地跳到另一個改進的局部最優解，成功避免算法在搜索過程中陷入局部最優的可能，并且大大減少了運算時間。目前，I&D搜索策略已經用于求解背包問題[10]、TSP問題等。

3.2 CVRP問題初始解的構造

本文采用客戶編號與配送中心（用“0”表示）共同排列的編碼方式作為CVRP問題的解的形式。假設一隨機排列為0-1-3-0-2-5-4-0-6-0，則表示3輛車參與了配送服務，其中車輛1-3的配送路線分別為0-1-3-0，0-2-5-4-0，0-6-0。

要構造CVRP問題的初始解，首先初始一個起終位置為“0”，長度為n+2的TSP序列（其中n為待配送的客戶點個數）；然后根據車輛載重約束在TSP序列中添加“0”達到終止當前車輛路線，開始新的路線的目的，最終形成VRP序列即為CVRP問題解的形式。

3.3 變異算子

改進的禁忌搜索算法針對局部最優解設計了兩種變異算子用于拓寬算法搜索區域。

（1）exchange：隨機選擇兩個節點并交換兩節點位置對應的客戶，如圖1所示。

圖1 exchange操作示意圖

（2）2-opt：隨機選擇兩個節點，將兩節點及其之間的所有客戶逆序排列，如圖2所示。

圖2 2-opt操作示意圖

在實際配送過程中，以上兩種變異算子對配送路線的影響如圖3、圖4所示。

圖3 exchange操作對配送路線的影響

圖4 2-opt操作對配送路線的影響

3.4 改進禁忌搜索算法的算法過程

改進的禁忌搜索算法求解CVRP問題步驟如下：

（1）初始化參數：禁忌長度TabuL、候選解個數Ca和最大迭代次數G，置禁忌表為空；

（2）產生初始解s0，在s0處集中搜索至sc=intensification(s0)；

（3）變異產生候選解s=diversification(sc)，記錄變異種類和變異節點的位置，尋找每一代中候選解的最優解，即再次集中搜索sc=intensification(s)；

（4）根據特赦準則更新禁忌表：若滿足，則從候選解中選擇評價值最小的狀態解禁；否則，選擇候選解中非禁忌對象對應的最優解為當前解，更新禁忌表；

（5）判斷算法是否進行到最大迭代次數，若是，結束算法并輸出最優結果；否則，轉步聚（3）。

4 實例分析

4.1 數據收集

本文的仿真實驗均在win10系統MATLAB R2017a環境下進行。數據來源于文獻[11]，已知配送中心的位置為(0 km,0 km)，負責配送車輛載重Q=9t，各客戶點的位置與需求量如表1所示。

表1 客戶信息表

4.2 參數實驗與分析

對于禁忌搜索算法來說，參數的選擇可能會影響到解的質量以及計算耗時。通常，緩慢的搜索求得高質量解的可能性較大，但往往會消耗更多的計算時間。采用單因素分析方法[12]來測定改進的禁忌搜索算法的關鍵參數（禁忌長度TabuL、候選解的個數Ca、最大迭代次數G）對算法性能的影響，每組均計算10次。由表2可以看出，禁忌長度、候選解個數以及最大迭代次數的取值都會影響到計算耗時，在TabuL=4、Ca=60、G=1 000時收斂最快且能計算到最優目標值，因此在接下來實驗中均采用該組參數設置。

表2 改進禁忌搜索算法關鍵參數實驗對比

4.3 對比實驗與分析

本文將改進的禁忌搜索算法（ITS）與標準的禁忌搜索算法（TS）、蟻群算法（ACO）以及文獻[11]中混合魚群遺傳算法（AFGA）、文獻[13]中改進的模擬退火算法（ISA）的計算結果進行對比。表3是實驗進行10次各算法計算得到的目標函數的最優值、平均值，使用車輛數目以及算法的平均耗時。從表3中可以看出，改進禁忌搜索算法無論是在計算結果還是計算時間方面均優于其他算法。圖5是四種算法求解CVRP問題的適應度進化曲線對比圖。

表3 各算法求解CVRP問題結果比較

圖5 適應度進化曲線對比圖

改進的禁忌搜索算法計算得到最優配送路徑長度為41.250 2 km，需使用4輛車完成配送任務，對應的配送路徑如圖6所示。

圖6 配送路線圖

5 結論

本文采用改進的禁忌搜索算法解決帶有容量限制的車輛路徑問題。在標準禁忌搜索算法的基礎上，采用I&D搜索策略，設計了兩種變異算子，避免了算法在搜索過程中陷入局部最優的可能，提高了算法的搜索質量與效率。并且設計了CVRP問題初始解的產生方式，有效解決了帶容量限制的車輛路徑問題。通過實驗確定禁忌搜索算法中關鍵參數的取值，對幾種算法的實驗結果進行比較，可以看出改進的禁忌搜索算法在求解CVRP問題時無論是運算結果還是計算耗時均能取得很好的結果。