考慮物料裝卸點的過道布置問題及改進灰狼算法求解方法

計 丹,張則強+,劉俊琦,陳 鳳,方瀟悅

(1.西南交通大學 機械工程學院,四川 成都 610031;2.軌道交通運維技術與裝備四川省重點實驗室,四川 成都 610031)

0 引言

在競爭日益激烈的壞境下,設施空間布局排布的不同直接影響車間的運營效率與搬運成本[1],這種設施空間的布局問題也被稱為設施布局問題(Facility Layout Problem,FLP)[2-5]。FLP是通過對廠區(qū)設施的合理布置從而達到總物流成本最小化的目的。有效的布局可提高企業(yè)總體生產力和生產效率[6],而不良的布局則會增加其生產時間和搬運成本[7]。據估計,20%～50%的制造成本來源于零件的搬運,而一個良好的設施布局可以將其減少10%～30%[8]。因此,FLP具有極其重要的研究意義及實際應用價值,近幾十年來一直是學術界與制造業(yè)關注的焦點。

過道布置問題(Corridor Allocation Problem,CAP)是AMARAL[9]于2012年提出的一種FLP中的新形式,它采用設施由同一起點連續(xù)且無間隙地布置在過道兩側的布局形式,最終達到最小化物流成本的目的。CAP具有良好的布局形式和高效的運輸效率,在服務業(yè)和制造業(yè)等領域應用廣泛,如學校教室、行政大樓[10]、商場店鋪、醫(yī)院病房等房間的布置以及集成電路板中微芯片的布局設計、半導體生產線的布局設計[11]等。CAP具有廣闊的應用前景和巨大的潛在價值,它的提出引起了人們的廣泛關注,成為設施布局領域的一個新的研究熱點。

CAP是典型的具有NP-hard屬性的組合優(yōu)化問題,研究學者不斷探索尋求解決方法[12]。AMARAL[9]首次建立混合整數規(guī)劃(Mixed Integer Programming,MIP)數學模型,并設計了3種具有不同操作的啟發(fā)式算法進行求解。GHOSH等[13]通過對遺傳算法進行改進,并將其與分散搜索算法對不同規(guī)模算例的求解結果進行比對,證明了前者在大規(guī)模問題的計算上占優(yōu)。AHONEN等[14]以最小化設施之間的加權距離為目標,使用禁忌搜索和模擬退火算法對不同規(guī)模的算例進行驗算并對比,最后得出模擬退火算法性能更加優(yōu)異。為了更加深入地研究CAP,學者們結合實際問題將其進一步拓展。ZHANG等[15]在CAP的基礎上考慮了過道寬度,并對分散搜索算法進行改進,使之求解所提問題的性能更優(yōu)。劉思璐等[16]將設施深度作為約束條件并構建數學模型,采用改進煙花算法進行求解。KALITA[17-18]首次提出以最小化物流成本與走廊長度為目標的雙目標過道布置問題,并采用基于置換的遺傳算法(Permutation-based Genetic Algorithm,PGA)進行求解,隨后通過引入局部搜索操作提高PGA的求解性能。陳鳳等[19]提出考慮設施方向的雙目標過道布置問題,并提出一種改進多目標分散搜索算法進行求解。管超等[20-22]將傳統CAP擴展到雙層過道布置問題(Double Floor Corridor Allocation Problem,DFCAP),并建立了混合整數規(guī)劃模型,隨后采用具有兩階段改進策略的模擬退火算法及帶有變鄰域搜索的遺傳算法對其求解。LIU等[23]在DFCAP的基礎上考慮了雙通道單向電梯對材料總搬運成本的影響,并提出一種自適應變鄰域克隆選擇算法進行求解。上述文獻均對CAP進行了深入的研究,在建模與求解方面也有了一定的改善。

物料裝卸點(Material Loading and Unloading Points,MLUP)是以人力或機械將物料裝入運輸設備或卸下的指定地點,是設施布局中的重要因素[24],其位置的設置直接影響材料的搬運成本。劉俊琦等[24]在CAP中考慮到不規(guī)則物流交互點的影響,并提出一種基于遺傳的混合雞群(Genetic Algorithm—Chicken Swarm Optimization,GA-CSO)算法進行求解,得出考慮交互點可最高降低29.77%的搬運成本的結論。董舒豪等[25]在多行設施布局問題中考慮了MLUP及搬運通道對物流成本的影響,區(qū)別于以往的是MLUP被分開布置,并提出遺傳模擬退火算法進行求解,結果證明MLUP對布局方案影響明顯。傳統的CAP中,MLUP位于設施緊挨過道邊線的中點,而在實際生產活動中為避免產品混雜和搬運路徑交叉,實現高效的裝卸作業(yè),MLUP被置于不同位置,因此在布局過程中考慮MLUP是很有必要的。此外,現有的FLP研究,大多數文獻都假設設施間的流量對稱,然而在生產實際中設施間的流量并非是完全對稱關系。GUAN等[26]在雙行布局問題中考慮了非對稱流量。楊緒洪[27]提出考慮非對稱流量的過道布置問題。非對稱流量的引入使得CAP更加貼合實際,也對今后生產布局的設計有一定的參考意義。

綜上所述,MLUP的區(qū)分可以方便單個設施內流水線的生產活動,提高生產效率及生產力,非對稱流量的引入為實際布局活動提供依據,決策者結合以上兩個因素更易選出較優(yōu)的布局形式。因此,本文首次在CAP中以最小化物流成本為目標,同時考慮MLUP及非對稱流量的影響,建立了混合整數規(guī)劃模型,并使用LINGO優(yōu)化器進行求解,驗證了模型的準確性,同時也為算法提供了一定的參考依據。CAP具有NP-hard屬性,隨著設施規(guī)模的增加,極大提升了精確求解的難度,因此本文針對所提問題及模型的特點,提出一種融合反向學習的灰狼優(yōu)化(Grey Wolf Optimizer with Opposition-based learning,OGWO)算法進行求解,該算法采用雙層整數編碼方式生成初始解,融合反向學習機制和種群更新機制擴大搜索解空間,并添加雙閾值停止準則,降低冗余迭代過程以提高算法的求解效率。使用該算法對考慮MLUP及非對稱流量的過道布置問題進行求解,通過與LINGO求得的結果進行比對,驗證了算法的有效性。為進一步顯示出OGWO算法的優(yōu)越性,應用OGWO算法求解經典CAP,并與其他算法進行對比,證明了OGWO算法在求解質量和效率上都有一定的優(yōu)勢。

1 考慮物料裝卸點的過道布置問題

1.1 問題描述

CAP是在過道兩側從左至右依次安置若干個設施,除滿足設施不重疊的約束外下還受到兩條約束:①過道兩側設施的布置起點相同;②同排設施無縫隙布置。傳統CAP的MLUP位于設施緊挨過道一側的中點且重合,而實際生產實踐中,為滿足設施內部的流水線生產,當設施長度較大時,MLUP常常置于不同位置,且設施之間的物流量也非完全對稱關系,因此針對上述問題,本文提出一種擴展的考慮物料裝卸點及非對稱流量的過道布置問題(extend point Corridor Allocation Problem,epCAP)。該問題更加貼合實際,能夠為CAP在今后的實際實踐中提供一定的理論支撐,epCAP的示意圖如圖1所示。

圖1 epCAP示意圖

1.2 基本假設條件

(1)設施形狀為矩形,相鄰設施緊密布置且不重疊;

(2)設施之間的物流交互量已知,設施長度已知;

(3)設施寬度均相等;

(4)過道的寬度為設施長度中的最小值;

(5)過道兩側設施的布置起點坐標均為0,沿過道向右的方向為x軸的正方向;

(6)設施的布置不受場地的面積大小及其他條件限制;

(7)同一設施間不進行物流交換。

1.3 新增約束

(1)設施長度不超過4 m時,物料交互點位于設施緊挨過道一側的中點;

(2)設施長度超過4米時,物料交互點分為裝料點和卸料點,分別位于約束(1)中交互點的兩側,設施長度的1/4位置;

(3)設施i到設施j的物流量與設施j到設施i的物料流量并非完全對稱關系,由實際情況而定。

考慮到新增約束(1)和約束(2),設施MLUP的橫坐標可由下式求得:

(1)

(2)

式中:xip表示設施i裝料點的橫坐標;xid表示設施i卸料點的橫坐標;變量αki、βi、γi、li的含義如表1所示。

表1 參數名稱與含義

因MLUP的位置不同,兩設施之間的搬運距離可由下式求得:

dij≥|xip-xjd|,1≤i

(3)

dji≥|xjp-xid|,1≤i

(4)

1.4 epCAP的數學模型

參數與變量的含義如表1所示。

epCAP的完整數學模型為:

Objective function

(5)

s.t.

(6)

(7)

dij≥xip-xjd,1≤i

(8)

dij≥xjd-xip,1≤i

(9)

dji≥xid-xjp,1≤i

(10)

dji≥xjp-xid,1≤i

(11)

?i,j∈Q,i≠j;

(12)

?i,j∈Q,i≠j;

(13)

αij+αik+αjk+αji+αki+αkj≥1,

1≤i

(14)

-αij+αik+αjk-αji+αki+αkj≤1,

i,j,k∈Q,i

(15)

-αij+αik-αjk+αji-αki+αkj≤1,

i,j,k∈Q,i

(16)

qij=αij+αji,1≤i,j≤n,i≠j;

(17)

αij∈{0,1},1≤i,j≤n,i≠j;

(18)

qij∈{0,1},1≤i,j≤n,i≠j;

(19)

γi∈{0,1},?i∈Q;

(20)

βi∈{0,1},?i∈Q。

(21)

其中:式(5)為目標函數,minF表示設施間總物流成本最小化;式(6)和式(7)用于計算各個設施的MLUP的橫坐標;式(8)～式(11)用于計算兩設施在x軸方向上的搬運距離;式(12)和式(13)用于約束同行設施不重疊;式(14)～式(16)用于確定決策變量αij;式(17)用于確定決策變量qij;式(18)～式(21)給定決策變量αij、qij、γi、βi的定義域。

2 求解epCAP的OGWO算法

2.1 基本灰狼優(yōu)化算法

MIRJALILI等[28]受灰狼捕食行為的啟發(fā),在2014年首次提出一種新型仿生算法:灰狼優(yōu)化(Grey Wolf Optimizer,GWO)算法。GWO算法通過模擬灰狼的等級制度以及狩獵行為來優(yōu)化目標。GWO算法的結構簡單、所需調節(jié)的參數較少,此外算法包含能夠自適應調整的收斂因子,能夠在局部尋優(yōu)與全局搜索過程中起到較好的平衡作用,因此在問題的求解質量和求解效率方面都表現出良好的性能[29]。GWO算法在連續(xù)問題求解方面應用廣泛,例如無人機路徑規(guī)劃[30]、優(yōu)化功率流[31]問題、停電風險預防[32]等,除此之外,GWO算法也在逐漸被改進并應用于組合優(yōu)化問題,如車間節(jié)能調度問題[33]、有界背包問題[34]、資源分配問題[35]等。因此,本文采用GWO算法對epCAP進行求解,并對GWO算法進行改進,使其能夠更好地解決所提問題。

灰狼群體內部有著嚴格的等級制度,從高到低依次是α、β、δ、ω,狼群中α狼的適應度最高,稱為頭狼;β狼次之,稱為從屬狼;δ狼第三,稱為普遍狼;其余為ω狼,也稱為底層狼。

灰狼追捕獵物時有包圍、狩獵、攻擊3種行為。

(1)包圍行為 灰狼在追捕獵物時,對獵物進行包圍的數學模型如下:

Y(t+1)=Yp(t)-A·D;

(22)

D=|C·Yp(t)-Y(t)|;

(23)

A=2a·r1-a;

(24)

(25)

C=2r2。

(26)

其中:Y為灰狼的位置;t為當前迭代的次數;Yp為獵物的位置;D為灰狼到獵物的距離;A、C為系數向量;a為由2～0線性遞減的收斂因子;r1、r2為[0,1]內的隨機數。

(2)狩獵行為 灰狼根據狼群中α、β、δ的位置不斷調整自身的位置進行狩獵,如圖2所示。其數學模型如下:

圖2 GWO算法中灰狼位置更新示意圖

Dα=|C1·Yα(t)-Y(t)|;

(27)

Dβ=|C2·Yβ(t)-Y(t)|;

(28)

Dδ=|C3·Yδ(t)-Y(t)|;

(29)

Y1=Yα-A1·Dα;

(30)

Y2=Yβ-A2·Dβ;

(31)

Y3=Yδ-A3·Dδ;

(32)

(33)

(3)攻擊行為 隨著收斂因子的縮小,灰狼逐步逼近獵物,當收斂因子為0時,此時系數向量A=0,灰狼開啟攻擊行為,如圖3a所示。

a 攻擊獵物 b 尋找獵物

2.2 融合反向學習的灰狼優(yōu)化算法

2.2.1 解序列的編碼與解碼

結合上述問題及模型的特點,本文初始解的生成采用的是雙層編碼方式。CAP是典型的組合優(yōu)化問題,其可行解序列可由一個有序的設施序列表示,結合epCAP的特性,其可行解表示為[S,G],第一層編碼S包含可行解的前n個單元,采用整數編碼,隨機生成一條有序的設施序列作為設施的布置方案;第二層編碼G是包含可行解的后n個單元,采用0～1編碼,確定物料裝料點的位置。定義第i個灰狼個體為Y(i),Y(i)=[s1,s2,…,sn|g1,g2,…,gn],sj表示布置在第j個位置的設施編號,gj表示布置在第j個位置設施的裝料點的位置,若gj=1,則設施j的裝料點位于其緊鄰過道邊線中點的左側,否則位于右側;狼群Q={Y1;Y2;…;Ynind},其中nind表示狼群中灰狼的個數;參數m表示布置在過道上行設施的數量,m∈[1,2,3,…,floor(n/2)];對于任意一個Y(i)和m都代表了一種布局方案。

為了更加直觀地展示解序列的編碼與解碼,以n=5的epCAP為例,一個可行解Y=[4,3,2,5,1|0,0,1,1,0],其中m=2,表示過道上行有2個設施;第一行的設施序列為[4,3],裝料點的索引為[0,0];第二行的設施序列為[2,5,1],裝料點的索引為[1,1,0]。具體示例如圖4所示。

圖4 解序列的編碼與解碼

2.2.2 GWO算法的改進與離散化處理

(1)收斂因子非線性化

在算法的局部尋優(yōu)與全局搜索階段,收斂因子a能夠起到平衡作用。受a影響的系數向量A的取值決定灰狼的捕獵方式,當|A|>1時,灰狼遠離當前獵物到更大的空間里進行全局搜索;當|A|<1時,灰狼接近獵物,進行局部尋優(yōu)。傳統的GWO算法中的a由2～0線性遞減,算法也隨之收斂,但是灰狼捕食獵物的過程是非線性的,因此線性收斂因子可能會遺漏一些解,最終陷入局部最優(yōu),無法更好地達到協調的效果;在實際應用中,為解決該問題,更偏向于將收斂因子非線性化,以便更清晰地描述灰狼追捕獵物時的路徑。因此,本文采用一種非線性收斂因子[36],其數學公式如下:

(34)

式中:t為當前迭代次數;T為最大迭代次數;ζ為調控因子,能影響a的變化速率,經多次實驗取ζ=20。

如圖5所示為收斂因子的對比圖,由此可以看出未改進前的a從2線性遞減到0;而改進后的a在迭代早期一直處于較高值,算法進行全局搜索,有效地擴大了解空間。迭代中期,a的數值從較高值迅速降到較低值,算法也由全局搜索迅速轉為局部尋優(yōu),達到了較好的協調作用。迭代后期,a的數值則一直處于較低值且不為0,算法進行局部尋優(yōu),算法的收斂速度也得到提升。

圖5 收斂因子對比圖

(2)比例權重動態(tài)化

傳統的GWO算法中,灰狼位置采取的是分別相對于α狼、β狼、δ狼前進后的位置求算數平均值,比例權重始終相等且不變,然而在算法中α狼并不一定是全局最優(yōu),因此在灰狼不斷靠近α狼的過程中極易陷入局部最優(yōu)。為降低算法陷入局部最優(yōu)的概率,本文引用一種動態(tài)的比例權重[37],其數學公式如下:

(35)

(36)

式中:σ1、σ2、σ3為位置向量的比例權重;W1、W2、W3分別為灰狼對于α狼、β狼、δ狼的學習權重。

因此,灰狼位置的更新公式為:

Y(t+1)=W1×Y1+W2×Y2+W3×Y3。

(37)

隨著迭代次數的增加,W1、W2、W3不斷變化,使得α狼、β狼、δ狼動態(tài)領導狼群進行捕獵行為,有效地降低了陷入局部最優(yōu)的概率。

(3)灰狼位置離散化

GWO算法中灰狼在追捕獵物時的位置為連續(xù)性變化,根據epCAP的特點,本文采用一種策略將連續(xù)性的變化轉變?yōu)殡x散序列。迭代次數t=1時生成一組與設施序列等長且單調遞增的隨機小數序列Z=[Z1,Z2,…,Zn];將該序列根據式(37)計算并進行增序重排,然后將更新后的序列按照規(guī)定的準則對應到離散的設施序列中。以n=9的問題為例,原設施序列Y=[8,5,4,2,3,7,9,1,6],隨機生成遞增數組Z,設施序號8對應Z中最小數值0.1,設施序號1對應Z中順序索引為8的數值4.5。經式(37)計算后,將新產生的Z進行遞增排序,此時最小數值為0.2,其對應到設施序列中的8號,順序索引為8的數值6.5,其對應到設施序列中的1號,按照此策略一一對應,最后得到新的設施序列Ynew=[3,8,5,6,2,7,1,4,9]。具體操作如圖6所示。

圖6 灰狼的位置更新

2.2.3 反向學習機制

(38)

傳統GWO算法中灰狼只在前3頭狼的指揮下不斷前進,然而各灰狼之間沒有任何交流,降低了灰狼的捕食效率。因此,本文采用基于交叉算子的兩種方式進行灰狼間的信息交互,如圖7和圖8所示,然后采用局部變異算子更新灰狼位置,使其加速向最優(yōu)解靠近。在信息交互完成后,將產生的新解與原始種群混合,計算適應度并排序,取前nind個個體為新種群,適應度最高的前3匹狼分別為α狼、β狼、δ狼。

圖7 信息交互方式1

圖8 信息交互方式2

2.2.4 局部搜索

本文針對α狼、β狼、δ狼進行局部搜索,如圖9所示,采用基于2-opt機制的雙層變異算子及只有裝料點位置發(fā)生改變的局部變異算子對可行解進行更新產生新解,并以貪心策略作為接受準則,添加閾值v1使算法能夠自適應調節(jié)搜索深度,若連續(xù)運行次數達到v1_max,但分別對于α狼、β狼、δ狼的最優(yōu)解未發(fā)生改變,則認為深度搜索完成。局部搜索算法流程如圖10所示。

圖9 變異算子

圖10 局部搜索流程圖

局部搜索的具本步驟如下:

步驟1初始化參數。輸入初始解Y_α、Y_β、Y_δ,并分別作為各自當前最優(yōu)解,確定最大迭代次數v_max。

步驟2分別對Y_α、Y_β、Y_δ進行雙層變異及局部變異操作,產生新解Y_αnew、Y_βnew、Y_δnew。

步驟3比較新解與初始解的大小,更新Y_α、Y_β、Y_δ及搜索深度。若F(Y_αnew)>min(F(Y_α)、F(Y_β)、F(Y_δ))或F(Y_βnew)>min(F(Y_α)、F(Y_β)、F(Y_δ))或(Y_δnew)>min(F(Y_α)、F(Y_β)、F(Y_δ)),則重置搜索深度v1,否則記鄰域搜索深度前進一步。

步驟4比較搜索深度與閾值的大小,如果未超過閾值則轉步驟5;反之,輸出當前局部最優(yōu)解Y_α、Y_β、Y_δ及其目標函數值F(Y_α)、F(Y_β)、F(Y_δ)。

步驟5(1)若F(Y_αnew)>F(Y_α),令Y_δ=Y_β、Y_β=Y_α、Y_α=Y_αnew;若F(Y_αnew)>F(Y_β),令Y_δ=Y_β、Y_β=Y_αnew;若F(Y_αnew)>F(Y_δ),令Y_δ=Y_αnew;

(2)若F(Y_βnew)>F(Y_α),令Y_δ=Y_β、Y_β=Y_α、Y_α=Y_βnew;若F(Y_βnew)>F(Y_β),令Y_δ=Y_β、Y_β=Y_βnew;若F(Y_βnew)>F(Y_δ),令Y_δ=Y_βnew;

(3)若F(Y_δnew)>F(Y_α),令Y_δ=Y_β、Y_β=Y_α、Y_α=Y_δnew;若F(Y_δnew)>F(Y_β),令Y_δ=Y_β、Y_β=Y_δnew;若F(Y_δnew)>F(Y_δ),令Y_δ=Y_δnew;

若Y_α被更新則重置迭代次數,若Y_β或Y_δ被更新則迭代次數不變,否則記迭代次數加1。

步驟6若迭代次數達到v_max,則輸出當前局部最優(yōu)解Y_α、Y_β、Y_δ及其目標函數值F(Y_α)、F(Y_β)、F(Y_δ),否則循環(huán)步驟2～步驟5,直到滿足局部搜索的終止條件。

2.2.5 種群更新機制

達爾文的進化論中提出“物競天擇,適者生存”的觀點,特別是群居物種更為明顯。本文根據“適者生存”的原則提出一種種群更新機制,在每一次迭代后將適應度較差的N個個體淘汰,然后隨機生成N個新解,以保證種群規(guī)模不變。N值越大,產生的新解越多,種群的多樣性越好,但N值過大,則算法趨近于隨機搜索,不利于算法的收斂;N值越小,隨機生成的新解越少,種群多樣性越差,降低了算法的尋優(yōu)能力。本文采用N=0.25×nind的方式進行自適應調整,既有利于擴大種群多樣性,又易于算法收斂尋優(yōu)。

2.2.6 雙閾值停止準則

在保證算法求解質量的前提下,通過設置雙閾值,減少了不必要的迭代,進一步提高了求解速度。在局部搜索已完成,即局部搜索中連續(xù)未更新次數超過v1_max或迭代次數v>v_max,并進行種群更新后,若外部檔案連續(xù)未更新次數超過glob_max時,停止迭代,輸出最優(yōu)解。

2.3 OGWO算法流程

綜上所述,本文針對epCAP所提的OGWO算法流程如圖11所示。

圖11 OGWO算法流程圖

其詳細步驟如下:

步驟1參數初始化。種群規(guī)模nind、最大迭代次數iter_max、局部搜索最大迭代次數v_max、外部檔案連續(xù)未更新最大次數glob_max、局部搜索閾值v1_max、收斂因子a、系數向量A、C等;

步驟2隨機生成初始種群,計算適應度F(Yi),取適應度最好的前3匹狼分別為α狼、β狼、δ狼,其余狼為ω狼;

步驟3灰狼搜索獵物,更新外部檔案及參數a、A、C;

步驟4利用反向學習機制生成反向解Y′,若Rand

步驟5對α狼、β狼、δ狼進行局部搜索;若外部檔案更新則glob=0,否則glob=glob+1;若glob>glob_max則輸出當前最優(yōu)解,否則轉步驟6;

步驟6令iter=iter+1,若iter>iter_max則算法終止,輸出當前最優(yōu)解,否則重復步驟3～步驟6。

3 算法驗證

3.1 epCAP模型驗證

本文算例測試采用的計算機硬件配置為Pentium(R)Dual-CoreCPUE6700、主頻3.20 GHz、內存4 GB,Windows 7操作系統。鑒于epCAP目前尚無測試算例的運算結果,首先采用LINGO優(yōu)化器根據1.4節(jié)所提MILP編寫程序并對小規(guī)模的算例進行求解,以證明epCAP模型的準確性并為算法提供一定的依據。為進一步測試OGWO算法的求解性能,使用MATLAB R2016運行該算法,針對epCAP的5～49規(guī)模中38個算例進行求解。以上38個測試算例均為本文所提算例。經過大量的實驗及程序調試后,OGWO算法、GWO算法求解epCAP的參數設置如表2所示。此外,考慮到算法的求解效率,經過大量的數據比對,確定過道設施分界點m的取值為[floor(n/2-2),floor(n/2)]。最后,規(guī)定算法的運行次數均為10次,以增強所得數據的準確性與可信性。

表2 OGWO、GWO求解epCAP的參數設置

如表3所示,LINGO在5～13規(guī)模算例中求解結果與OGWO算法求解結果相同,證明了所提epCAP模型的準確性。隨著問題規(guī)模的增大,其解空間爆炸式擴大,因此LINGO的求解時間也急劇增加,當n>13時便無法在合理的時間期限中求出目標值?？紤]到運行效率,本文規(guī)定LINGO統一運行3 600 s,若3 600 s內還無法求得可行解,則以“—”表示運算結果。采用標準差SD作為衡量求解結果的指標。

表3 LINGO優(yōu)化器、GWO算法與OGWO算法求解epCAP的計算結果

由表3可知,對于算例S5～Am13a,OGWO算法均能得到LINGO所求最優(yōu)解,對于n>13的算例,OGWO算法的求解結果遠遠優(yōu)于LINGO所得較優(yōu)解,驗證了OGWO所求結果的有效性。對比OGWO算法與GWO算法可知,針對大部分算例,改進后的OGWO算法無論是在求解結果還是求解時間方面均優(yōu)于GWO算法,體現了改進的優(yōu)越性及OGWO算法的高效性。其中OGWO求解epCAP的最優(yōu)設施序列見附錄。

3.2 算法評價

為驗證算法的性能優(yōu)良,選取S5、S9H、S11、Am12a、Am13a、N25-05、N30-01、Ste36-01、Sko42-01、Sko49-01等10個算例,運用OGWO算法分別運行10次,并做求解偏差gap的箱型圖,gap=(f-F)/f×100%,f表示算法每次運算結果,F表示單個算例運算結果中的最優(yōu)值。箱型圖中,求解結果的上下四分位點、平均值、中位值和最大最小值分別對應箱子的上下框線、黑色虛線、紅色實線以及上邊線和下邊線。

由圖12可知,在求解epCAP時,對于前5個小規(guī)模算例,OGWO算法所求結果中測試問題求解偏差的箱體長度均為零,說明算法在求解這5個算例時,每次運行結果均為最優(yōu)解。對于中大規(guī)模算例,除Ste36-01外,其余箱體長度較短,這就表明了OGWO算法求解結果的離散度較小,求解穩(wěn)定性較高。整體來看,箱線圖中的10個算例均無異常值,即求解性能較為優(yōu)良。

圖12 OGWO算法求解不同規(guī)模問題的結果箱線圖

此外,選定Am12a算例,運用GWO算法與OGWO算法對epCAP進行求解,為了對比結果明顯,將兩者的參數設置相同,由圖13可以看出,改進前GWO算法無法在規(guī)定條件下求得最優(yōu)解,而改進后的OGWO算法在迭代40次后便趨于平衡,其收斂速度明顯優(yōu)于GWO算法,再次證明了OGWO算法具有良好的求解性能。

圖13 OGWO算法與GWO算法迭代收斂對比圖

3.3 OGWO算法在初始CAP中的應用

當前文獻尚未有對epCAP的研究,因此為更有力地驗證OGWO算法在求解質量和效率方面都有一定的優(yōu)勢,以及該算法具有一定的普適性,運用OGWO算法對9～80規(guī)模的CAP算例進行求解。由于epCAP與CAP編碼上存在差異(epCAP的編碼方式為雙層整數編碼,CAP的編碼方式為單層整數編碼),故OGWO算法在求解CAP時將不存在第二層編碼的交叉與變異且參數的設置也存在差異。由于本文增加反向學習機制、種群更新機制及局部搜索對GWO算法進行改進,局部搜索的引入增加了求解時間,因此,為了算法對比更具說服力,經過大量的實驗及程序調試后,將GWO算法、OGWO算法設置求解CAP的參數設置如表4所示。此外,規(guī)定算法的運行次數均為10次,以增強所得數據的準確性與可信性。

表4 OGWO算法、GWO算法求解CAP的參數設置

與epCAP不同的是,在求解初始CAP時,其目標函數為:

(39)

根據式(39),分別采用4種不同算法進行求解。將對小規(guī)模CAP(9～18規(guī)模)的求解結果匯總如表5所示,通過表5中數據對比可得,OGWO算法的求解質量相對于GWO算法具有顯著提升。為了證明OGWO算法對中大規(guī)模CAP同樣具有良好的求解能力,采用OGWO算法對中大規(guī)模CAP(20～80規(guī)模)進行求解并將求解結果匯總至表6。通過對比表6中的數據可得,中規(guī)模CAP(20～49)中,除Ste36-04、Ste36-05外,OGWO算法的求解質量相對于CAP-Heuristic、GA、GWO算法均較好,表明了OGWO算法在處理中規(guī)模問題上同樣具有一定優(yōu)勢。對于大規(guī)模問題(60～80),OGWO算法在求解結果及求解時間方面均優(yōu)于GWO算法,說明了改進后的算法具有明顯的優(yōu)勢,求解質量與效率顯著提高。綜上,OGWO算法在求解傳統CAP上同樣具有高效性及穩(wěn)定性。

表5 OGWO算法與其他算法求解CAP的小規(guī)模問題計算結果對比

表6 OGWO算法與其他算法求解CAP的中大規(guī)模問題計算結果對比

此外,本文選取S9H、Am13a、H20、N30-01、Ste36-01、Sko42-01、Sko49-01、Akv70-01等8個算例,運用OGWO算法和GWO算法分別運行10次,并做求解偏差gap的箱型圖,如圖14所示。

圖14 OGWO算法與GWO算法求解不同規(guī)模CAP的偏差箱線圖

由圖14可知,針對不同規(guī)模算例,OGWO算法的箱長較小且數值集中,證明OGWO算法所求結果的數據離散度較低、算法收斂性較強,說明了改進后的OGWO算法具有明顯的優(yōu)勢。

4 結束語

本文針對MLUP在CAP中研究的不足,結合實際生產布局,提出了以最小化物流成本為目標,考慮MLUP及非對稱流量的過道布置問題,并設計了一種OGWO算法進行求解,通過大量算例的計算表明算法具有良好的優(yōu)越性。本文的主要成果如下:

(1)考慮MLUP位置對布局的影響及設施間流量的非對稱性,構建了相關數學模型,并運用LINGO求解器對該模型進行求解,驗證了epCAP模型的準確性。

(2)結合問題的特點提出了一種改進的灰狼優(yōu)化算法,該算法采用雙層整數編碼方式生成初始解,融合反向學習機制對個體進行改進,加入局部搜索過程增強算法的搜索性能,并設置雙閾值停止準則,減少多余的迭代次數。

(3)選取epCAP的10個算例,經OGWO算法重復運行10次,分析求解偏差并繪制箱型圖,數據表明OGWO算法在求解epCAP上具有良好的收斂性。根據Am12a算例的GWO算法與OGWO算法計算迭代曲線對比,再一次證明改進后的OGWO算法性能優(yōu)良。

(4)應用OGWO算法對規(guī)模5～49中38個算例進行求解,S5～Am13a,OGWO算法均能得到LINGO所求最優(yōu)解,證明了所提OGWO算法的有效性;將該算法與CAP-Heuristic、GA、GWO算法對CAP的求解結果進行比較,證明其在CAP上同樣具有良好的性能。

epCAP模型的提出使得CAP更加貼合實際,但為了簡化模型,本文將MLUP置于設施1/4的位置上,在實際生活中,MLUP的位置有可能不固定,也有可能兩者具有某種約束關系。此外,單目標epCAP并不能完全顯示出實際生活中其他目標對布局的影響。因此,探究MLUP的位置和約束關系,考慮多目標的CAP及繼續(xù)改進GWO算法使其在其他領域也可以高效地計算大規(guī)模算例等在未來都是值得進一步探索的問題。

附錄

表1 OGWO算法求解epCAP的最優(yōu)設施序列