郭玉潔 張 強(qiáng) 魏永和

（1.東北石油大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院 大慶 163318）

（2.國(guó)家電網(wǎng)冀北電力有限公司管理培訓(xùn)中心 北京 100000）

1 引言

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

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

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

2 數(shù)學(xué)模型

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

其中：

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

3 離散鯨魚算法

3.1 區(qū)域劃分

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

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

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

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

3）當(dāng)每個(gè)樣本都被分到k個(gè)聚類群后，重新計(jì)算聚類中心m1，m2，…，mk。

4）重復(fù)步驟2）～3），直到k個(gè)聚類中心不變。

5）計(jì)算距離成本函數(shù)F并記錄，直到k值全部計(jì)算結(jié)束。

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

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

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

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

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

3.2 編碼與解碼

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

鯨魚位置按照規(guī)則與CVRP路徑形成一一對(duì)應(yīng)關(guān)系：”0”認(rèn)為是配送中心；鯨魚位置前后分別加上“0”，構(gòu)成一條完整的CVRP路徑；客戶點(diǎn)之間經(jīng)過的順序構(gòu)成一臺(tái)車輛的訪問路徑。例如：n=9，m=3，xi=(1，3，2，8，9，7，6，4，5)，首先對(duì)客戶點(diǎn)進(jìn)行聚類分組，假設(shè)k取值為3，則分為三個(gè)小區(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 鯨魚位置的更新操作

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

1）更新方式選擇

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

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

2）包圍捕食重定義

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

3）泡泡網(wǎng)捕食重定義

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

4）隨機(jī)捕食重定義

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

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

3.4 鄰域搜索策略

根據(jù)CVRP的特點(diǎn)，借鑒文獻(xiàn)［12］的鄰域搜索策略，本文提出了隨機(jī)交換，2-opt，3-opt相結(jié)合的局部搜索策略。

1）交換搜索：對(duì)配送路徑進(jìn)行交換搜索，隨機(jī)選取兩個(gè)不同位置的客戶點(diǎn)，將兩個(gè)客戶點(diǎn)位置交換。

圖1 交換搜索示例圖

2）2-opt搜索：對(duì)配送路徑進(jìn)行2-opt搜索，隨機(jī)選取兩個(gè)不同位置的客戶點(diǎn)，將兩個(gè)客戶點(diǎn)之間的位置全部反轉(zhuǎn)。

圖2 2-opt搜索示例圖

3）3-opt搜索：對(duì)于配送路徑進(jìn)行3-opt搜索，隨機(jī)選取3個(gè)位置的客戶點(diǎn)依次交換。

圖3 3-opt搜索示例圖

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

4 實(shí)驗(yàn)與分析

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

表1 部分算例實(shí)驗(yàn)結(jié)果對(duì)比

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

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

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

圖7 C101算例總成本迭代圖

圖8 C201算例總成本迭代圖

圖9 RC208算例總成本迭代圖

5 結(jié)語

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