彭 維

(重慶城市管理職業(yè)學(xué)院工商管理學(xué)院 重慶 401331)

0 引 言

包裝配送問題是典型的組合優(yōu)化問題[1]，通?？梢悦枋鰹椋簭囊粋€配送中心出發(fā)，安排若干車輛為客戶配送包裝，要求在滿足交貨時間、車輛載重、客戶需求量等條件下，合理安排配送線路，使配送的路程、時間或者費用達到最優(yōu)。近年來，隨著電子商務(wù)深入發(fā)展，包裝需求量和配送量井噴式增長，包裝配送問題愈發(fā)受到重視，其求解算法也逐漸成為了學(xué)者們的研究熱點。

分析大量文獻可知，包裝配送問題的求解算法可以分為精確算法和啟發(fā)式算法，其中啟發(fā)式算法占比高達85%左右。這主要是由于包裝配送問題屬于NP-hard難題，可行解數(shù)量會隨著問題規(guī)模的增大而發(fā)生“組合爆炸”，計算開銷也隨之呈指數(shù)式增長[2-3]。精確算法在求解該類問題時，求解效率低、運行速度慢，往往無法取得令人滿意的結(jié)果。相比之下，啟發(fā)式算法具有快速尋優(yōu)能力，可以在較短時間內(nèi)求得大規(guī)模問題的較好解，因此成為了包裝配送問題的主要求解算法。目前，應(yīng)用于包裝配送問題的主要啟發(fā)式算法包括：遺傳算法[4]、螢火蟲算法[5]、禁忌搜索算法和其他算法[6]。

雖然已有大量優(yōu)秀算法，但追求更高效的算法一直都是包裝配送及其他組合優(yōu)化問題的重要研究方向[7]。對此，本文引入一種新型啟發(fā)式算法—水波算法(WWA)，并將其應(yīng)用于包裝配送問題中。WWA算法由鄭宇軍教授于2014年首次提出，具有參數(shù)較少、實現(xiàn)簡單、計算開銷小等優(yōu)勢[8]。在標(biāo)準(zhǔn)WWA算法基礎(chǔ)上，本文對算法個體編碼方式進行重新設(shè)計，并引入混沌機制和碎波系數(shù)自適應(yīng)調(diào)整機制，提出了基于包裝配送問題的CAWWA算法。實驗表明，CAWWA算法能夠很好地適用于包裝配送問題的求解。

1 包裝配送問題的數(shù)學(xué)模型

假設(shè)配送中心安排K輛車為L個客戶配送包裝，車輛最大載重量為Q，客戶需求量為qi(i=1,2,…,L)，用i=0表示配送中心，cij表示客戶i到j(luò)的配送成本(如距離、費用等)，定義決策變量為：

則包裝配送問題的數(shù)學(xué)模型可表示為[9]：

(1)

(2)

(3)

(4)

(5)

(6)

xijk=0或1 ?i,j,k

(7)

yik=0或1 ?i,k

(8)

其中:式(2)表示車輛最大載重約束；式(3)-式(5)表示每個客戶都有且僅有一輛車配送；式(6)表示消除子回路；式(7)-式(8)表示變量取值范圍。

2 標(biāo)準(zhǔn)水波算法

2.1 基本原理

WWA算法是模擬淺水波運動模型求解問題的過程而設(shè)計的一種新型啟發(fā)式算法[10]。算法將問題求解空間看作為海床，每個可能解看作一個波高為h和波長為λ的水波。水波的適應(yīng)度值與水波到海床的垂直距離成反比，即水波距海床越遠，適應(yīng)度值越小，內(nèi)含能量也越小，且波長λ越長，波高h越低，這使得優(yōu)質(zhì)水波可以在最優(yōu)解附近進行局部搜索，而劣質(zhì)水波則能夠跳出局部最優(yōu)進行大范圍搜索，進而求得問題最優(yōu)解。WWA算法包括傳播、折射和碎波3個算子。不同深度水域的波形如圖1所示。

圖1 不同深度水域的波形

2.2 傳播算子

假設(shè)問題維度為D，水波每一維位置為x(d)(1≤d≤D)，每次迭代中水波通過傳播公式對自身位置進行更新。

x′(d)=x(d)+rand(-1,1)·λ·L(d)

(9)

式中:rand(-1,1)表示[-1,1]之間的均勻隨機數(shù)；L(d)表示第d維搜索空間的長度。位置更新后，如果適應(yīng)度函數(shù)值f(x′)>f(x)，則用x′代替x，水波波高h重置為最大值hmax；反之，保留x，水波波高h伴隨能量的損耗而衰減。水波位置更新后，水波波長也發(fā)生改變，公式如下：

λ=λ·α-(f(x)-fmin+ε)/(fmax-fmin+ε)

(10)

式中：α表示最大波長減少率；ε表示為保證分母不為0而設(shè)置的極小正數(shù)；fmax、fmin分別表示本次迭代中最優(yōu)水波和最差水波對應(yīng)的適應(yīng)度值。分析式(10)可知，波長與適應(yīng)度值成反比。適應(yīng)度值越大，水波波長越短，傳播范圍越窄；反之，水波波長越長，傳播范圍越大。

2.3 折射算子

水波傳播過程中，有的水波會在淺水域聚集，最終在深水域發(fā)散反射。具體來說，當(dāng)水波波高h變?yōu)?時，水波將進行反射，對應(yīng)位置根據(jù)下式進行更新：

(11)

式中：x*(d)表示當(dāng)前種群的最優(yōu)水波，N(μ,δ2)表示均值為μ、標(biāo)準(zhǔn)差為δ的高斯隨機數(shù)。折射后的波長為：

(12)

2.4 碎波算子

隨著能量的不斷增加，水波波峰變得越來越陡峭，最終破碎成大量獨立的小波浪。WWA算法只對最優(yōu)水波進行碎波操作，公式如下：

x′(d)=x*(d)+N(0,1)·β·L(d)

(13)

式中:β為碎波系數(shù)。碎波操作后，如果f(x′)>f(x*)，則用x′代替x*；否則，不更新。

3 混沌自適應(yīng)水波算法

3.1 個體表達式構(gòu)造

步驟1：生成隨機矩陣。隨機生成一個L×L(L表示客戶數(shù)量)的客戶矩陣M，每個元素mij(i、j為橫坐標(biāo)和縱坐標(biāo))的值介于0～1之間。

步驟2：生成概率矩陣。對矩陣M每一行進行歸一化處理，得到概率矩陣M1。比如，假設(shè)M第一行為[0.20.30.80.9]，對應(yīng)四個元素相加之和為0.2+0.3+0.8+0.9=2.2，各元素分別除以2.2，可得歸一化處理結(jié)果為[0.090.140.360.41]，將其作為M1的第一行。同理，可生成M1其他數(shù)據(jù)。可知，M1中每一行元素之和均為1，且每個元素表示該客戶在客戶序列中某個位置的概率。比如，假設(shè)M1的第一行為[0.090.140.360.41]，則表示第一個客戶排在第一位的概率為0.09，排在第二位的概率為0.14，排在第三位的概率為0.36，排在第四位的概率為0.41。

3.2 個體表達式解析

步驟1生成0-1矩陣。將概率矩陣M1元素與波長λ進行比較，若小于λ，則相應(yīng)位置為1，反之為0，得到0-1矩陣M2，如圖2所示(假設(shè)λ=0.2)。進行矩陣調(diào)整，確保M2每行每列都只有一個1。調(diào)整原則為：如果第i列只有一個1，則保留該1，如圖2的第2列；如果第i列不止一個1，假設(shè)所有1后面的列都還有1出現(xiàn)，則優(yōu)先保留第一個1，假設(shè)有的1后面的列全是0，則優(yōu)先保留該1，其他1變?yōu)?，如圖2中的第1列和第3列。

步驟2生成配送路徑。根據(jù)M2生成客戶序列，并按照車輛載重約束生成配送路徑。圖2中客戶序列為x=3-1-4-2。假設(shè)客戶1到客戶4的包裝需求量分別為50、20、40和20，車輛最大載重量為70。則可得兩條配送子路徑，分別為x1=0-3-1-0(0表示配送中心)，x2=0-4-2-0。每條子路徑的配送成本(距離、費用等)之和即為該方案的配送成本。

圖2 個體表達式構(gòu)成及解析

3.3 混沌初始化

啟發(fā)式算法對初始種群具有嚴(yán)重依賴性，如果初始種群個體在最優(yōu)解鄰域內(nèi)，那么算法能夠快速收斂到較好解甚至最優(yōu)解。如果初始種群個體離最優(yōu)解較遠，則算法收斂速度較慢，且求解精度會大幅降低?；煦缡且环N廣泛存在于社會和自然界中的非周期性運動，具有隨機性、遍歷性和規(guī)律性等特征，能夠在一定范圍內(nèi)不重復(fù)地遍歷所有狀態(tài)[11-12]。對此，本文采用混沌機制來克服啟發(fā)式算法初始種群分布不理想的缺點，以提高初始種群質(zhì)量。本文采用混沌Logistic映射生成初始隨機矩陣，公式如下：

Mn+1=μMn(1-Mn)

(14)

n=0,1,2,… 0≤μ≤4

(15)

3.4 碎波系數(shù)自適應(yīng)調(diào)整

在WWA算法中，碎波算子主要用于對最優(yōu)水波附近的空間進行搜索，而碎波系數(shù)β是控制搜索范圍的一個重要參數(shù)。β越大，搜索范圍越廣，反之則搜索范圍越小。傳統(tǒng)WWA算法采用固定的碎波系數(shù)，明顯無法滿足算法前期和后期的不同搜索需求，無法達到全局搜索和局部搜索的平衡，不利于算法求解質(zhì)量的提高。對此，本文提出了基于對數(shù)遞減的碎波系數(shù)自適應(yīng)調(diào)整機制。在算法前期，碎波系數(shù)較大，算法可以大范圍地進行全局搜索，從而得到更優(yōu)的水波。而在算法后期，碎波系數(shù)較小，算法能夠更加精準(zhǔn)地進行局部搜索，進而提高算法求解精度。公式如下：

β=βmax-γ(βmax-βmin)×logiterMaxiter

(16)

式中:βmax、βmin分別表示最大最小碎波系數(shù)；γ表示對數(shù)調(diào)整因子；iter表示算法當(dāng)前迭代次數(shù)，iterMax表示最大迭代次數(shù)。

3.5 CAWWA算法求解包裝配送問題

步驟1設(shè)置算法參數(shù)，包括初始種群規(guī)模Num、初始水波波高hmax、波長λ、波長減少率α、最大碎波系數(shù)βmax、最小碎波系數(shù)βmin、對數(shù)調(diào)整因子γ和算法最大迭代次數(shù)iterMax，令當(dāng)前迭代次數(shù)iter=0。

步驟2根據(jù)第3.3節(jié)生成Num個初始隨機矩陣。

步驟3判斷iter是否大于或等于iterMax。若是，算法停止，輸出最優(yōu)水波x*及f(x*)；反之，算法進入步驟5。

步驟4按照第3.1節(jié)對個體矩陣進行歸一化處理，并根據(jù)第3.2節(jié)解析個體并計算適應(yīng)度值，記錄最優(yōu)水波x*及適應(yīng)度值f(x*)。

步驟5利用式(9)對每個水波x進行傳播，得到新的水波x′，利用式(10)更新波長λ。如果f(x′)>f(x)，則用x′代替x，重置波高為hmax；反之，保留x，令波高h=h-1。

步驟6判斷水波波高h是否等于0。若是，則利用式(11)-式(12)進行折射操作。

步驟7利用式(13)對最優(yōu)水波x*進行碎波操作，得到新的水波。如果f(x′)>f(x*)，則用x′代替x*；反之，保留x*。

步驟8令iter=iter+1，返回步驟3。

4 仿真實驗

為驗證算法有效性，本文在8×quad core 2.3 MHz CPU、64 GB內(nèi)存、Window10系統(tǒng)環(huán)境下，利用CAWWA算法對包裝配送實例進行仿真測試。其中，配送中心位置為(30 km,30 km)，30個客戶需求量及位置信息如表1所示，車輛最大載重為8 t。

表1 客戶信息

如表2所示，完成此次配送任務(wù)所需車輛數(shù)為8，最優(yōu)配送距離為809.59 km。由此可知，CAWWA算法能夠有效應(yīng)用于包裝配送問題的求解。為進一步驗證算法的求解性能，分別利用CAWWA算法、GA算法[13]、ACO算法[14]和TS算法[15]對配送問題的國際通用算例進行50次求解，統(tǒng)計求得最好解(BS)、平均運行時間(AT)等指標(biāo)如表3所示。各算例最優(yōu)配送路徑如表4所示。

表2 最優(yōu)配送方案

表3 GA算法、ACO算法、TS算法和CAWWA算法仿真結(jié)果對比

表4 最優(yōu)配送方案

續(xù)表4

由表3可知， TS算法只能求得B-n31-k5算例的已知最優(yōu)解，GA算法和ACO算法分別還能求得E-n23-k3、E-n33-k4算例的已知最優(yōu)解，CAWWA算法不但能求得所有算例已知最優(yōu)解，還更新了B-n31-k5、B-n51-k7和P-n55-k8的已知最優(yōu)解。由此可見，CAWWA算法全局尋優(yōu)能力最強，GA算法和ACO算法次之，而TS算法最弱。同時，CAWWA算法求解各算例的平均運行時間最短，說明該算法運行速度最快、搜索效率最高。這主要得益于混沌機制提高了算法初始種群質(zhì)量，自適應(yīng)碎波系數(shù)增強了算法前期全局搜索能力，并提高了算法后期的搜索精度，進而優(yōu)化了算法綜合求解性能。

綜上分析，CAWWA算法能夠很好地適應(yīng)包裝配送問題的求解，且求解性能優(yōu)于GA算法、ACO算法和TS算法。

5 結(jié) 語

本文主要對求解包裝配送問題的CAWWA算法進行了研究。首先，設(shè)計了基于包裝配送問題的個體編碼方式；然后，引入混沌機制生成初始種群，并提出了自適應(yīng)調(diào)整的碎波系數(shù)，擴大算法前期搜索范圍，提高后期搜索精度。仿真結(jié)果表明，CAWWA算法求解性能優(yōu)于GA算法、TS算法和ACO算法，能夠適應(yīng)于包裝配送問題的求解。