求解帶容量約束車輛路徑問題的離散鯨魚算法*

郭玉潔 張 強 魏永和

（1.東北石油大學計算機與信息技術學院 大慶 163318）

（2.國家電網冀北電力有限公司管理培訓中心 北京 100000）

1 引言

帶容量約束的車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP）是車輛路徑問題（Vehicle Routing Problem，VRP）［1］的經典問題之一。CVRP一直是組合優(yōu)化和運籌學領域的熱點問題，其在物流配送和車輛路徑規(guī)劃等領域具有十分廣泛的應用背景，因此如何有效地解決CVRP具有很高的實際應用和理論研究價值。

隨著啟發(fā)式算法的不斷發(fā)展，運用群智能算法對CVRP問題進行求解是目前的重要研究方向，如何提高求解CVRP問題的效率仍是當前學者們的研究重點。文獻［2］提出一種基于文化基因的狼群算法求解VRPTW。文獻［3］提出一種離散蝙蝠算法求解VRP，該算法引入隨機插入策略和交換搜索來提高算法的局部搜索能力。文獻［4］提出一種基于NSGA-II的蟻群算法求解雙目標VRPTW。文獻［5］等設計一種改進蟻群算法求解VRP，在傳統(tǒng)蟻群算法中引入交通擁堵因子，提高了計算效率。文獻［6］提出一種改進的禁忌搜索算法求解面向倉庫的車輛路徑問題。文獻［7］設計一種具有貪婪轉移準則的多目標蟻群算法求解VRP。文獻［8］將模擬退火算法與遺傳算法結合，設計一個新型編碼解碼方式求解VRP。然而，以上啟發(fā)式算法在不同類型的VRP算例中會出現(xiàn)求解能力不穩(wěn)定、易陷入局部最優(yōu)等問題。

鯨魚優(yōu)化算法［9］（Whale Optimization Algorithm，WOA）是由澳大利亞學者Mirjalili和Lewis于2016年提出的一種新元啟發(fā)式優(yōu)化算法。近年來，許多學者把鯨魚算法應用到實際工程優(yōu)化問題中，但是現(xiàn)有的鯨魚算法不能直接應用到CVRP上。因此，本文提出了一種離散鯨魚算法（Discrete Whale Optimization Algorithm，DWOA）求解CVRP，通過基于距離代價函數的K-means算法將不同位置的客戶劃分為不同的配送區(qū)域，提高初始解的質量；重定義鯨魚算法中包圍捕食、泡泡網捕食、隨機捕食的更新策略，利用新的位置更新策略對區(qū)域組中的路徑進行優(yōu)化，同時引入隨機交換搜索、2-opt、3-opt相結合的鄰域搜索策略，尋找到更多潛在的優(yōu)秀解。實驗結果表明DWOA能夠有效跳出局部最優(yōu)、穩(wěn)定性更高、時間耗費更少。

2 數學模型

帶容量約束的車輛路徑問題（CVRP）是指物流車輛在配送貨物時要滿足車身容量等約束條件，在CVRP問題中有一個配送中心，多個客戶點和配送車輛，求解CVRP的目標是在滿足約束條件的基礎上合理安排車輛路線，使配送的總成本最低。

其中：

式（1）為目標函數，F(xiàn)1為配送車輛數，F(xiàn)2為車輛行駛總距離；式（2）表示每輛車不得超過其最大載重量；式（3）表示車輛從配送中心出發(fā)完成配送任務后必須返回配送中心；式（4）表示車輛服務完客戶i后再去服務客戶j；式（5）表示車輛服務客戶j之前服務客戶i；式（6）表示每個客戶只能被一輛車服務；式（7）和式（8）表示決策變量約束條件。

3 離散鯨魚算法

3.1 區(qū)域劃分

k-means算法是一種典型的聚類方法，核心思想是通過反復迭代優(yōu)化聚類結果，使所有樣本點到各自所屬類別的中心距離平方和達到最小，其公式如下所示：

其中，Jc是k-means聚類方法的誤差平方和準則，Xi為第i聚類的樣本子集，mi為第i聚類Xi中的樣本均值，p為第i聚類中包含的數據。盡管k-means算法能夠有效地解決聚類問題，但不正確的k會影響算法的實際效果。因此，在本文中采用距離成本函數F［10～11］來確定k值。其描述如下：

其中m是所有數據的平均值。當F最小時，聚類結果最好，并且k是根據最小F得到的；通過距離代價函數的k-means算法將大VRP問題轉換成多個小VRP問題后；判斷每個小區(qū)域內所要配送的客戶需求量和車輛最大載重的大小關系，將客戶劃分到不同的區(qū)域。因此，距離代價函數的k-means算法具體實現(xiàn)步驟如下。

2）對于待聚類樣本，計算其與k個聚類中心的距離，并將樣本歸類到最近的聚類群中。

3）當每個樣本都被分到k個聚類群后，重新計算聚類中心m1，m2，…，mk。

4）重復步驟2）～3），直到k個聚類中心不變。

5）計算距離成本函數F并記錄，直到k值全部計算結束。

6）根據最小F值找到最優(yōu)k值。

7）將客戶集合x=(1，2，3，4，…，d)劃分為k個配送區(qū)域。

8）判斷每個區(qū)域的客戶總需求量是否超出車輛最大載重。

9）若每個區(qū)域的客戶需求量都滿足車輛最大載重，則分區(qū)結束。

10）若在k1區(qū)域（k1∈k），當客戶x1加入后，超出車輛的最大載重量，將x1之前的客戶劃分到當前區(qū)域，余下的客戶組成一個新的區(qū)域，繼續(xù)步驟8），判斷剩余的區(qū)域是否滿足車輛最大載重。

3.2 編碼與解碼

設P∈N*為鯨魚種群規(guī)模，客戶數為n，車輛數為m，維數d=n。定義第i個鯨魚的位置為xi=(xi1，xi22，xi3，…，xid)，i=1，2，…，P，其中xi是(1，2，…，d)的一個置換。

鯨魚位置按照規(guī)則與CVRP路徑形成一一對應關系：”0”認為是配送中心；鯨魚位置前后分別加上“0”，構成一條完整的CVRP路徑；客戶點之間經過的順序構成一臺車輛的訪問路徑。例如：n=9，m=3，xi=(1，3，2，8，9，7，6，4，5)，首先對客戶點進行聚類分組，假設k取值為3，則分為三個小區(qū)域：{1 ，6，4，5}，{9，7，3}，{2，8}，因此，三輛車的訪問路徑分別為{0 ，1，6，4，5，0}，{0，9，7，3，0}，{0，2，8，0}。

3.3 鯨魚位置的更新操作

標準鯨魚優(yōu)化算法用來求解具有連續(xù)性的問題，但是在求解CVRP模型時，客戶節(jié)點的編碼是離散的，因此需要重定義鯨魚優(yōu)化算法的包圍捕食、泡泡網捕食、隨機捕食操作。

1）更新方式選擇

在DWOA算法中，當||A≥1且rand()＜0.5時，鯨魚通過包圍捕食來搜索獵物；當||A＜1且rand()＜0.5時，鯨魚通過泡泡網捕食來攻擊獵物；當rand()≥0.5時，鯨魚通過隨機搜索來尋找獵物。

其中，α在迭代過程中從2到0線性遞減；?為［0，1］隨機數組成的向量。為了保證更新操作后路徑的可行性，對于區(qū)域組內的路徑的更新方式采用基于最短距離的插入、反轉、交換等操作。設x=(x1，x2，xi，xj，xk，…，xd)，i=rand(d)且i∈d，Dij表示客戶i和客戶j之間的距離。

2）包圍捕食重定義

在一條路徑中，隨機選擇一個客戶xi，然后遍歷剩余的客戶點；若存在一個客戶xd，到客戶xi的距離小于原訪問路徑xi到下一個相鄰客戶點xj的距離，則將客戶點xd插入到客戶點xi之后，余下的客戶點依次后移。

3）泡泡網捕食重定義

在一條路徑中，隨機選擇一個客戶xi，然后遍歷剩余的客戶點，計算將其插入xi之后所對應的距離增加量；若存在一個客戶xd，到客戶xi的距離小于原訪問路徑xi到下一個相鄰客戶點xj的距離增加量，將xi到xd之間的客戶點反轉。

4）隨機捕食重定義

在一條路徑中，隨機選擇一個客戶xi，然后遍歷剩余的客戶點；若存在一個客戶xd，到客戶xi的距離小于原訪問路徑xi到下一個相鄰客戶點xj的距離，則將xd與原訪問路徑中xi的下一個客戶點xj交換位置。

因此，鯨魚位置的更新操作從連續(xù)域到離散域的轉換過程：1）通過計算客戶點之間的距離差值，以此對應連續(xù)域中的鯨魚之間的位置差。2）通過判斷插入位置、反轉位置和交換位置時距離的增加量，選擇合適的插入位置，使其不斷向最優(yōu)位置靠攏，符合本算法的新路徑更新定義。

3.4 鄰域搜索策略

根據CVRP的特點，借鑒文獻［12］的鄰域搜索策略，本文提出了隨機交換，2-opt，3-opt相結合的局部搜索策略。

1）交換搜索：對配送路徑進行交換搜索，隨機選取兩個不同位置的客戶點，將兩個客戶點位置交換。

圖1 交換搜索示例圖

2）2-opt搜索：對配送路徑進行2-opt搜索，隨機選取兩個不同位置的客戶點，將兩個客戶點之間的位置全部反轉。

圖2 2-opt搜索示例圖

3）3-opt搜索：對于配送路徑進行3-opt搜索，隨機選取3個位置的客戶點依次交換。

圖3 3-opt搜索示例圖

選擇上述的鄰域搜索策略對每次迭代得到的最優(yōu)解進行變換，產生更多的鄰域解，選擇適應度最小的值作為每代的最優(yōu)解，本算法的局部搜索策略按照一定的規(guī)則來交換客戶的訪問次序，得到的路徑仍然對應著一個完整的CVRP路徑。

4 實驗與分析

本文采用Solomon的六種類型CVRP算例［13］測試DWOA，然后將DWOA和標準鯨魚算法（Whale Optimization Algorithm，WOA）、粒子群算法［14］（Particle Swarm Optimization，PSO）、模擬退火算法［15］（Simulated Annealing，SA）進行比較實驗，表1給出部分算例實驗結果。DWOA的參數設置如下：MaxIt=1000，po pnum=100，w=0.2，WOA、PSO和SA的基本參數設置同DWOA一致。在表1中，NV是車輛數，TD是總行駛距離。

表1 部分算例實驗結果對比

通過表1分析可知，在求解C型問題時，DWOA的性能略優(yōu)于其他三種算法，其求得配送車輛數和行駛總里程和已知最優(yōu)解車輛數、最優(yōu)里程數十分相近，但在求解C2問題中也存在個別案例未達到最優(yōu)解；在求解R型問題時，DWOA的車輛數明顯少于其它兩種算法，所求的最優(yōu)行駛距離整體上與目前最優(yōu)解接近，其中，R1問題中有部分需求的配送車輛和配送總里程要優(yōu)于當前已知最優(yōu)解，R2問題中需求的配送車輛都獲得了最優(yōu)解，且配送總里程與已知最優(yōu)里程十分接近；在求解RC型問題時，DWOA的最優(yōu)解遠遠優(yōu)于其他兩種算法，甚至優(yōu)于目前已知的最優(yōu)解。

為了具體驗證DWOA算法在求解帶容量約束車輛路徑問題的性能，本文分別用DWOA、WOA、PSO、SA算法對CVRP的數學模型進行求解。在Solomon數據集中以C101、C201、RC208三種算例做具體分析，其結果如下所示。

圖4 C101最優(yōu)路徑圖

圖5 C201最優(yōu)路徑圖

圖6 C208最優(yōu)路徑圖

其中，C101算例得到的最優(yōu)解為832.1701，所需車輛為10，與目前最優(yōu)解828.94接近，從而證明離散鯨魚算法在求解C101上有較好的尋優(yōu)能力；C201算例得到的最優(yōu)解為589.76，所需車輛為3，與目前最優(yōu)解591.56接近，因此，離散鯨魚算法在求解C201上有良好的尋優(yōu)效果；RC208得到的最優(yōu)解為817.8789，所需車輛為3，優(yōu)于目前最優(yōu)解828.94，證明離散鯨魚算法在求解RC208上有很好的尋優(yōu)能力。

圖7、8、9為 四 種 算 法 在 求 解C101、C201、RC208算例時的總成本迭代圖，其中，橫坐標表示算法的迭代次數，縱坐標表示總成本（包括配送車輛數和車輛行駛總距離），圖中反映了DWOA算法有較好的求解能力。在算法迭代初期，總成本大幅下降，表明DWOA算法在前期對客戶點進行聚類操作劃分區(qū)域，可以使算法最短的時間內向最優(yōu)解趨近，從而體現(xiàn)出DWOA算法具有良好的全局搜索能力；隨著迭代次數的增加，總成本變化逐漸變小，DWOA的局部搜索能力逐漸占主導地位，其中，DWOA采用了交換搜索、2-opt搜索、3-opt搜索相結合的鄰域搜索策略，可以使算法在迭代后期跳出局部最優(yōu)。因此，驗證了DWOA算法在在求解CVRP模型時前期存在較強的全局搜索能力，后期則有較強的局部尋優(yōu)能力，所得到的結果要優(yōu)于WOA、PSO和SA三種算法。

圖7 C101算例總成本迭代圖

圖8 C201算例總成本迭代圖

圖9 RC208算例總成本迭代圖

5 結語

針對CVRP的求解，本文提出了一種離散鯨魚算法。算法采用距離代價函數的K-means算法劃分不同的客戶區(qū)域，重定義鯨魚算法的位置更新策略對單個區(qū)域內的訪問路徑進行更新，并引入隨機交換搜索、2-opt、3-opt策略對最優(yōu)路徑進行鄰域變換，增強算法局部搜索能力。算例驗證及分析表明，DWOA能夠有效求解CVRP，尋優(yōu)質量優(yōu)于所對比算法，可跳出局部最優(yōu)。未來將進一步改進DWOA，以加強其在車輛路徑規(guī)劃問題上的應用。