混沌自適應(yīng)水波算法在包裝配送問(wèn)題中的應(yīng)用

彭 維

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

0 引 言

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

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

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

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

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

則包裝配送問(wèn)題的數(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)表示每個(gè)客戶都有且僅有一輛車配送；式(6)表示消除子回路；式(7)-式(8)表示變量取值范圍。

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

2.1 基本原理

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

圖1 不同深度水域的波形

2.2 傳播算子

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

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

(9)

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

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

(10)

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

2.3 折射算子

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

(11)

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

(12)

2.4 碎波算子

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

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

(13)

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

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

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

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

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

3.2 個(gè)體表達(dá)式解析

步驟1生成0-1矩陣。將概率矩陣M1元素與波長(zhǎng)λ進(jìn)行比較，若小于λ，則相應(yīng)位置為1，反之為0，得到0-1矩陣M2，如圖2所示(假設(shè)λ=0.2)。進(jìn)行矩陣調(diào)整，確保M2每行每列都只有一個(gè)1。調(diào)整原則為：如果第i列只有一個(gè)1，則保留該1，如圖2的第2列；如果第i列不止一個(gè)1，假設(shè)所有1后面的列都還有1出現(xiàn)，則優(yōu)先保留第一個(gè)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。每條子路徑的配送成本(距離、費(fèi)用等)之和即為該方案的配送成本。

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

3.3 混沌初始化

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

Mn+1=μMn(1-Mn)

(14)

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

(15)

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

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

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

(16)

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

3.5 CAWWA算法求解包裝配送問(wèn)題

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

表1 客戶信息

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

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

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

表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)解。由此可見(jiàn)，CAWWA算法全局尋優(yōu)能力最強(qiáng)，GA算法和ACO算法次之，而TS算法最弱。同時(shí)，CAWWA算法求解各算例的平均運(yùn)行時(shí)間最短，說(shuō)明該算法運(yùn)行速度最快、搜索效率最高。這主要得益于混沌機(jī)制提高了算法初始種群質(zhì)量，自適應(yīng)碎波系數(shù)增強(qiáng)了算法前期全局搜索能力，并提高了算法后期的搜索精度，進(jìn)而優(yōu)化了算法綜合求解性能。

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

5 結(jié) 語(yǔ)

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