混沌自適應水波算法在包裝配送問題中的應用

彭 維

(重慶城市管理職業學院工商管理學院 重慶 401331)

0 引 言

包裝配送問題是典型的組合優化問題[1]，通常可以描述為：從一個配送中心出發，安排若干車輛為客戶配送包裝，要求在滿足交貨時間、車輛載重、客戶需求量等條件下，合理安排配送線路，使配送的路程、時間或者費用達到最優。近年來，隨著電子商務深入發展，包裝需求量和配送量井噴式增長，包裝配送問題愈發受到重視，其求解算法也逐漸成為了學者們的研究熱點。

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

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

1 包裝配送問題的數學模型

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

則包裝配送問題的數學模型可表示為[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 標準水波算法

2.1 基本原理

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

圖1 不同深度水域的波形

2.2 傳播算子

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

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

(9)

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

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

(10)

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

2.3 折射算子

水波傳播過程中，有的水波會在淺水域聚集，最終在深水域發散反射。具體來說，當水波波高h變為0時，水波將進行反射，對應位置根據下式進行更新：

(11)

式中：x*(d)表示當前種群的最優水波，N(μ,δ2)表示均值為μ、標準差為δ的高斯隨機數。折射后的波長為：

(12)

2.4 碎波算子

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

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

(13)

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

3 混沌自適應水波算法

3.1 個體表達式構造

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

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

3.2 個體表達式解析

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

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

圖2 個體表達式構成及解析

3.3 混沌初始化

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

Mn+1=μMn(1-Mn)

(14)

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

(15)

3.4 碎波系數自適應調整

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

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

(16)

式中:βmax、βmin分別表示最大最小碎波系數；γ表示對數調整因子；iter表示算法當前迭代次數，iterMax表示最大迭代次數。

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

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

步驟2根據第3.3節生成Num個初始隨機矩陣。

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

步驟4按照第3.1節對個體矩陣進行歸一化處理，并根據第3.2節解析個體并計算適應度值，記錄最優水波x*及適應度值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)對最優水波x*進行碎波操作，得到新的水波。如果f(x′)>f(x*)，則用x′代替x*；反之，保留x*。

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

4 仿真實驗

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

表1 客戶信息

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

表2 最優配送方案

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

表4 最優配送方案

續表4

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

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

5 結 語

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