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

李佳慧，姜志俠

（長春理工大學(xué) 理學(xué)院，長春 130022）

近年來隨著國民經(jīng)濟增長方式的轉(zhuǎn)變，結(jié)構(gòu)調(diào)整的穩(wěn)步推進，產(chǎn)業(yè)結(jié)構(gòu)的不斷優(yōu)化，物流業(yè)作為各行業(yè)的輔助行業(yè)已滲透到了各類經(jīng)濟領(lǐng)域中，它跟隨著其他行業(yè)的發(fā)展而發(fā)展，雖然現(xiàn)代物流業(yè)的服務(wù)水平在逐漸提高，但是物流成本高一直以來都是國家和物流企業(yè)所關(guān)注的重點問題。車輛路徑問題[1]（Vehicle Routing Prob?lem，VRP）作為物流配送中的一個核心問題，受到了廣泛的關(guān)注。

1 相關(guān)工作

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

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

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

2 CVRP問題描述和數(shù)學(xué)模型

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

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

符號說明如下：

K：配送車輛集合；

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

qi：客戶點i的需求量；

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

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

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

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

3.1 I&D搜索策略

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

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

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

3.2 CVRP問題初始解的構(gòu)造

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

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

3.3 變異算子

改進的禁忌搜索算法針對局部最優(yōu)解設(shè)計了兩種變異算子用于拓寬算法搜索區(qū)域。

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

圖1 exchange操作示意圖

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

圖2 2-opt操作示意圖

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

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

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

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

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

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

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

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

（4）根據(jù)特赦準(zhǔn)則更新禁忌表：若滿足，則從候選解中選擇評價值最小的狀態(tài)解禁；否則，選擇候選解中非禁忌對象對應(yīng)的最優(yōu)解為當(dāng)前解，更新禁忌表；

（5）判斷算法是否進行到最大迭代次數(shù)，若是，結(jié)束算法并輸出最優(yōu)結(jié)果；否則，轉(zhuǎn)步聚（3）。

4 實例分析

4.1 數(shù)據(jù)收集

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

表1 客戶信息表

4.2 參數(shù)實驗與分析

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

表2 改進禁忌搜索算法關(guān)鍵參數(shù)實驗對比

4.3 對比實驗與分析

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

表3 各算法求解CVRP問題結(jié)果比較

圖5 適應(yīng)度進化曲線對比圖

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

圖6 配送路線圖

5 結(jié)論

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