王沙沙，張則強(qiáng)，劉俊琦，陳 鳳

(西南交通大學(xué) 機(jī)械工程學(xué)院軌道交通運(yùn)維技術(shù)與裝備四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610031)

0 引言

在我國制造強(qiáng)國戰(zhàn)略的推動(dòng)下，各行各業(yè)積極開展智能制造實(shí)踐活動(dòng)。建設(shè)智能工廠是實(shí)現(xiàn)智能制造的重要手段。設(shè)施布局(Facility Layout Problem, FLP)是智能工廠建設(shè)的重要環(huán)節(jié)，對系統(tǒng)的物料處理成本和吞吐量具有重要的影響[1]。因此，F(xiàn)LP在智能制造實(shí)現(xiàn)過程中扮演著非常重要的角色。過道布置問題(Corridor Allocation Problem, CAP)[2]作為布局設(shè)計(jì)的子類，具有搬運(yùn)效率高的特點(diǎn)，廣泛應(yīng)用于生產(chǎn)生活中；環(huán)形布局問題(Loop Layout Problem, LLP)以其相對較低的投資成本和高度物料處理靈活性[3]，在制造系統(tǒng)中有廣泛應(yīng)用[4]。雙向環(huán)形過道布置問題結(jié)合了二者的特點(diǎn)，具有重要的實(shí)際意義和研究價(jià)值。

在過道布置問題(CAP)中，所有設(shè)施都排布在過道兩側(cè)，起點(diǎn)相同，設(shè)施間無間隙，設(shè)施間的物料流動(dòng)必須經(jīng)過中間過道。根據(jù)以往文獻(xiàn)，可以將CAP分為單層CAP與多層CAP[5-6]兩大類。對單層CAP的研究中，劉思璐等[7]考慮了設(shè)施深度對布局的影響；陳鳳等[8]考慮了設(shè)施擺放方向不同對布局的影響。環(huán)形布局問題(LLP)將制造單元沿物料搬運(yùn)路徑布置，從而形成一個(gè)封閉環(huán)，設(shè)施可以位于環(huán)路的內(nèi)部和外部[4,8]或只位于環(huán)路外部[9-10],根據(jù)不同研究對物料流動(dòng)的限制不同，分為單向[10]和雙向[4]。賈林等[11]提出了環(huán)形過道布置問題，假設(shè)搬運(yùn)路徑為一個(gè)圓環(huán)，設(shè)施放置在圓環(huán)過道兩側(cè)，該問題與LLP中設(shè)施布置在環(huán)路內(nèi)外兩側(cè)的問題具有相似性；王沙沙等[12]通過劃分不同路徑,對環(huán)形過道布置問題進(jìn)行研究。兩篇論文都假設(shè)過道的布置起點(diǎn)不可跨越，而在實(shí)際生產(chǎn)中，環(huán)形過道通常是連通的，設(shè)施之間可以進(jìn)行雙向的物料搬運(yùn)。

目前，求解CAP的方法有精確解法和元啟發(fā)式方法兩種。精確解法主要是數(shù)學(xué)規(guī)劃方法，如CHAE等[13]、AMARAL[2]、陳鳳等[8]對不同過道布置問題建立了混合整數(shù)規(guī)劃模型。但實(shí)際問題中解的空間很大，精確解法需耗費(fèi)大量時(shí)間，因此人們越來越關(guān)注有效的元啟發(fā)式方法。劉思路等[7]采用改進(jìn)煙花算法求解考慮設(shè)施深度的過道布置問題，試驗(yàn)表明改進(jìn)煙花算法在尋優(yōu)精度、收斂效率和穩(wěn)定性方面均有明顯優(yōu)勢；王沙沙等[12]采用改進(jìn)蟻獅算法求解多路徑環(huán)形過道布置問題，取得較好的求解效果；GUAN等[14]采用花授粉算法求解雙層過道布置問題，通過計(jì)算不同規(guī)模標(biāo)準(zhǔn)算例，驗(yàn)證了花授粉算法求解雙層過道布置問題效果優(yōu)于其他算法；KALITA等[15]采用基于置換的遺傳算法求解雙目標(biāo)過道布置問題；毛麗麗等[16]采用改進(jìn)分散搜索算法求解過道布置問題。上述求解過道布置問題的元啟發(fā)式算法都是基于2015年及以前的元啟發(fā)式算法改進(jìn)而來，而最近幾年，出現(xiàn)了一些新的元啟發(fā)式算法如：黏菌算法(Slime Mould Algorithm, SMA)[17]、蜻蜓算法(Dragonfly Algorithm DA)[18]、鯨魚算法(Whale Optimization Algorithm, WOA)[19]、蝗蟲算法(Grasshopper Optimisation Algorithm, GOA)[20]等。這些算法為解決CAP提供了新的思路和方向。WOA以其結(jié)構(gòu)簡單、所需算子少、收斂速度快、勘探開發(fā)階段之間的平衡能力強(qiáng)等優(yōu)點(diǎn)，在各個(gè)工程領(lǐng)域得到了廣泛應(yīng)用。RANA等[21]從2016年～2020年間關(guān)于WOA研究的文章中選取82篇進(jìn)一步研究了WOA在工程各個(gè)領(lǐng)域的應(yīng)用、改進(jìn)和雜交，研究結(jié)果顯示，基于WOA的技術(shù)被應(yīng)用于5個(gè)領(lǐng)域和17個(gè)不同工程領(lǐng)域的子領(lǐng)域，其中61%的工作對算法進(jìn)行改進(jìn)，27%的工作將WOA與其他算法混合，12%的工作應(yīng)用WOA變體解決多目標(biāo)問題;CHEN[22]通過引入隨機(jī)備用或隨機(jī)替換策略和雙重自適應(yīng)權(quán)重策略，提出NAWOA(new adaptive whale optimization algorithm) ，提高了基本W(wǎng)OA算法的收斂速度和整體搜索能力。對3個(gè)基準(zhǔn)函數(shù)以及3個(gè)工程設(shè)計(jì)問題進(jìn)行了綜合研究，驗(yàn)證了其性能。實(shí)驗(yàn)結(jié)果表明，該方法顯著改善了基本算法探索性開發(fā)性以及收斂模式;HEMASIAN-ETEFAGH等[23]引入新的分組思想，克服了WOA早期收斂問題，在30個(gè)標(biāo)準(zhǔn)基準(zhǔn)函數(shù)上應(yīng)用Friedman檢驗(yàn)的方法，結(jié)果顯示與其他基準(zhǔn)算法相比具有更好的性能;LIU等[24]提出一種基于Lévy飛行和差分進(jìn)化的混合進(jìn)化算法來求解車間調(diào)度問題，并將其應(yīng)用于88個(gè)車間調(diào)度問題基準(zhǔn)實(shí)例的求解，并與現(xiàn)有算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果和統(tǒng)計(jì)分析表明，該算法較其他算法性能更優(yōu)。為解決多目標(biāo)問題，GOT等[25]提出一種基于Pareto占優(yōu)的引導(dǎo)種群優(yōu)化算法(Guided Population Archive Whale Optimization Algorithm, GPAWOA)，將擁擠距離納入基本W(wǎng)OA中，以保持種群多樣性，該算法在12個(gè)基準(zhǔn)函數(shù)上進(jìn)行評估，并應(yīng)用于4個(gè)多目標(biāo)工程設(shè)計(jì)問題，實(shí)驗(yàn)結(jié)果表明算法具有很強(qiáng)的競爭力，能夠在收斂性和多樣性方面提供Pareto前沿的良好逼近。

鑒于鯨魚算法求解類似問題具有明顯優(yōu)勢，本文提出混合鯨魚算法，通過嵌入差分進(jìn)化算法和禁忌搜索的機(jī)制，克服鯨魚算法過早收斂的不足，并采用該算法對雙向多路徑交互環(huán)形過道布置問題進(jìn)行求解。

1 雙向多路徑環(huán)交互形過道布置問題

1.1 問題描述

雙向多路徑交互環(huán)形過道布置問題可描述為：現(xiàn)有n個(gè)設(shè)施，排布在環(huán)形回路兩側(cè)。要求滿足以下約束條件：①設(shè)施不能重疊，且設(shè)施之間無間隙；②環(huán)形回路寬度e可變且大于0，寬度由內(nèi)外設(shè)施總長度差確定，且物料沿通道可進(jìn)行順逆雙向交互；③過道內(nèi)外兩側(cè)設(shè)施布置起點(diǎn)相同。

假設(shè)條件：①設(shè)施之間單位距離的加權(quán)物流交互成本固定，為已知量；②設(shè)施的物料交互點(diǎn)均位于設(shè)施靠過道邊線的中點(diǎn)，暫不考慮設(shè)施寬度；③設(shè)施布置不受場地約束和限制；④不考慮環(huán)形過道布置問題中設(shè)施與外界的物料交互；⑤為方便計(jì)算，將環(huán)形回路簡化為一個(gè)正圓。

雙向多路徑交互環(huán)形過道布置問題示意圖如圖1所示，圖中設(shè)施序列為1,2,3,4,5,6,7，將其從3、4中間位置分成兩組設(shè)施序列，即1,2,3和4,5,6,7，分別計(jì)算兩組設(shè)施的總長度，假設(shè)1,2,3序列設(shè)施總長較長。圖1中將兩組設(shè)施以粗實(shí)線為布置起點(diǎn)，兩組設(shè)施沿逆時(shí)針進(jìn)行布置;設(shè)施之間物料交互經(jīng)過中間深色通道，假設(shè)兩設(shè)施之間的實(shí)際距離為過道寬度與設(shè)施靠過道邊線中點(diǎn)投影到過道中線上兩點(diǎn)之間的弧線長度之和;位于通道同側(cè)設(shè)施1和設(shè)施3之間路徑如兩設(shè)施之間帶箭頭組合線所示；位于通道不同側(cè)設(shè)施1和設(shè)施4之間路徑如兩設(shè)施之間帶箭頭組合線所示。

1.2 雙向多路徑交互環(huán)形過道布置問題數(shù)學(xué)模型

數(shù)學(xué)模型中各個(gè)符號參數(shù)的定義如表1所示。

表1 數(shù)學(xué)模型中符號參數(shù)定義

在雙向多路徑交互環(huán)形過道布置問題中，過道是一個(gè)封閉的圓環(huán)，任意兩設(shè)施之間物料交互有2個(gè)方向不同、距離可能不等的可選路徑。針對以上特點(diǎn)，以最小化總物料搬運(yùn)成本為目標(biāo)，建立雙向多路徑交互環(huán)形過道布置問題的數(shù)學(xué)模型：

(1)

式(1)為目標(biāo)函數(shù)，計(jì)算所有設(shè)施間單位距離物流成本cij與實(shí)際運(yùn)輸距離dij乘積的最小值。由于設(shè)施所放置的位置不同，設(shè)施間的實(shí)際運(yùn)輸距離計(jì)算有差異，位于通道兩側(cè)的兩個(gè)設(shè)施之間的物料交需跨越中間通道。因此，

1≤i,j≤n，i≠j。

(2)

θij=min(αij,|αij-2π|),1≤i

(3)

αij=|θi-θj|,1≤i

(4)

(5)

1≤i,j≤n;i≠j;

(6)

(7)

式(3)～式(7)用于確定θij，保證設(shè)施之間不發(fā)生重疊。通道內(nèi)外側(cè)邊緣對應(yīng)半徑與通道中線對應(yīng)半徑分別為：

(8)

(9)

計(jì)算通道內(nèi)外側(cè)邊緣長度，并令L1作為通道外側(cè)邊緣長度

(10)

L1≥L2。

(11)

環(huán)形布局中，通道寬度的變化會(huì)影響物料流動(dòng)距離，并且在實(shí)際生產(chǎn)中通道寬度可以根據(jù)生產(chǎn)需要進(jìn)行設(shè)定，本文限制通道寬度大于0。

(12)

e>0。

(13)

為保證每個(gè)設(shè)施都被布置在某個(gè)固定位置，對決策變量xik和ykij約束如下：

(14)

(15)

(16)

ykij+ykji+1≥xik+xjk,k∈K;1≤i

(17)

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

(18)

xik∈{0,1},1≤i≤n;k∈K。

(19)

本文針對雙向多路徑交互環(huán)形過道布置問題的混合整數(shù)規(guī)劃模型確定了每個(gè)設(shè)施布置在通道內(nèi)側(cè)或通道外側(cè)進(jìn)行。文獻(xiàn)[12]中只確定設(shè)施是否布置在通道同一側(cè)，并沒有確定設(shè)施具體放置位置，因此在計(jì)算放置在不同側(cè)設(shè)施投影到過道中線弧長時(shí)，采用設(shè)施沿直線布置時(shí)的距離來近似代替弧長，本文對數(shù)學(xué)模型進(jìn)行改進(jìn)，確定了設(shè)施的具體位置，在計(jì)算放置在不同側(cè)設(shè)施投影到過道中線弧長時(shí)更加準(zhǔn)確。

2 混合鯨魚算法

2.1 經(jīng)典鯨魚算法介紹

鯨魚算法的靈感來源于座頭鯨的起泡網(wǎng)捕食行為。座頭鯨喜歡捕食蝦群和靠近洋面的小魚群，在鯨魚向水面上升時(shí)，會(huì)制造一個(gè)環(huán)繞的起泡網(wǎng)。在WOA算法中，目標(biāo)獵物被認(rèn)為是最優(yōu)解，算法步驟描述如下：

(1)種群初始化。鯨魚種群中每個(gè)個(gè)體由D維度隨機(jī)向量表示，種群規(guī)模用Np表示，公式如下：

Xi=xmin+rand(1,D)(xmax-xmin),

i=1,2,…,Np。

(20)

式中：xmin和xmax分別為Xi的下界和上界;rand(1,D)表示[0,1]之間的隨機(jī)數(shù)。

(2)包圍獵物。座頭鯨可以根據(jù)獵物的位置來跟蹤、包圍和捕食獵物。在WOA中，獵物的位置即解空間，當(dāng)前最佳候選解為目標(biāo)獵物或接近最優(yōu)解。在包圍獵物階段，鯨魚種群向最優(yōu)解靠近，并更新位置。這個(gè)過程表示如下：

D=|C·X*(t)-X(t)|;

(21)

X(t+1)=X*(t)-A·D。

(22)

其中：t為當(dāng)前迭代次數(shù);X*(t)為當(dāng)前最優(yōu)解的位置;X和D為位置向量;A和C為系數(shù)向量，隨迭代次數(shù)改變。每次迭中，當(dāng)出現(xiàn)更優(yōu)解時(shí)，更新當(dāng)前最優(yōu)解X*。

A=2a·r-a;

(23)

C=2·r。

(24)

a從2到0線性遞減，r為[0,1]的隨機(jī)向量。根據(jù)式(19)，可以將該方法擴(kuò)展到n維空間，鯨魚種群將在超立方體中圍繞當(dāng)前最優(yōu)解移動(dòng)。

(3)氣泡網(wǎng)覓食。座頭鯨在覓食時(shí)沿圓形或“9”形路徑上產(chǎn)生起泡網(wǎng)，兩種策略設(shè)計(jì)如下：

1)收縮包圍機(jī)制。如式(23)所示，隨著迭代進(jìn)行a線性遞減，A取值范圍隨之遞減。更新后鯨魚種群位置可以在初始位置與當(dāng)前最優(yōu)位置之間取得。如圖2所示為(X,Y)到當(dāng)前最優(yōu)位置(X*,Y*)的搜索空間。

2)位置螺旋更新。

為了模擬座頭鯨的螺旋形運(yùn)動(dòng)，建立表示座頭鯨與獵物之間位置的螺旋方程如下：

X(t+1)=D′·ebl·cos(2πl(wèi))+X*(t);

(25)

D′=|X*(t)-X(t)|。

(26)

其中：b定義了對數(shù)螺旋的形狀，b=1;l為[-1,1]之間的隨機(jī)數(shù);D′為第i個(gè)鯨魚到獵物(當(dāng)前最優(yōu)位置)的距離。

鯨魚沿著一個(gè)收縮圈圍繞獵物游動(dòng)，同時(shí)以螺旋形的路徑靠近獵物，如圖3所示。在[0,1]中選擇一個(gè)隨機(jī)數(shù)p，有50%的可能性在兩種模式之間切換以更新鯨魚的位置，如下所示：

(27)

(4)搜索獵物。座頭鯨利用A搜索獵物，它們根據(jù)彼此的位置隨機(jī)搜索。步驟(3)和步驟(4)的區(qū)別在于，當(dāng)|A|>1時(shí)，鯨魚的位置依據(jù)隨機(jī)選擇的鯨魚更新，而不是依據(jù)當(dāng)前最佳位置更新：

D=|C·Xrand-X|;

(28)

X(t+1)=Xrand-A·D。

(29)

其中Xrand為當(dāng)前種群中隨機(jī)選擇的鯨魚位置。

2.2 混合鯨魚算法介紹

WOA用于求解連續(xù)函數(shù)，而不能直接用于環(huán)形過道布置問題這種離散問題的求解。因此，本文對隨機(jī)鍵編碼方式進(jìn)行處理，將連續(xù)問題轉(zhuǎn)化為離散問題，使算法適用于求解環(huán)形過道布置問題。鯨魚的位置不能代表設(shè)施排布順序，但是每個(gè)分量大小不同，將分量進(jìn)行排序，得到設(shè)施序列，如圖4所示。

2.2.1 與差分進(jìn)化算法結(jié)合提高鯨魚算法局部搜索能力(HWOA1)

差分進(jìn)化算法(Differential Evolution algorithm, DE)是一種基于種群差異的進(jìn)化算法，利用群體內(nèi)個(gè)體之間的合作和競爭產(chǎn)生的群體智能模式來指導(dǎo)優(yōu)化搜索的進(jìn)行?；诓罘值暮唵巫儺惒僮?，使WOA具有較強(qiáng)的全局收斂能力和魯棒性，非常適合求解一些復(fù)雜環(huán)境中的優(yōu)化問題。

WOA通過貪婪選擇得到更新后鯨魚個(gè)體位置，這使選擇局限于最優(yōu)解，容易陷入局部最優(yōu)。當(dāng)DE嵌入WOA中時(shí)，會(huì)創(chuàng)建一個(gè)包含當(dāng)前總體和歷史最優(yōu)個(gè)體的外部存檔集，因此在每次迭代時(shí)，大多數(shù)新生成的具有DE搜索策略的解決方案都會(huì)在外部存檔集的指導(dǎo)下更新，這增加了個(gè)體之間的信息共享，極大地提高了WOA的局部搜索和開發(fā)能力。

差分進(jìn)化算法原理：從某一隨機(jī)產(chǎn)生的初始群體開始，通過將種群中任意若干個(gè)體之間的向量差加權(quán)后按一定的規(guī)則比較，產(chǎn)生新個(gè)體;如果新個(gè)體滿足選擇條件，則在下一代用新個(gè)體取代舊個(gè)體，否則舊個(gè)體仍保留下來，通過不斷迭代計(jì)算，保留優(yōu)良個(gè)體，淘汰劣質(zhì)個(gè)體，引導(dǎo)搜索過程項(xiàng)最優(yōu)解逼近。

標(biāo)準(zhǔn)的DE算法包括變異、交叉和選擇操作，具體如下：

(1)變異

根據(jù)參考文獻(xiàn)[24]，DE中的變異操作主要有以下8種：

1)“DE/rand/1”

Vi,g=Xr1,g+F(Xr2,g-Xr3,g)。

(30)

2)“DE/best/1”

Vi,g=Xbest,g+F(Xr2,g-Xr3,g)。

(31)

3)“DE/current/1”

Vi,g=Xi,g+F(Xr2,g-Xr3,g)。

(32)

4)“DE/current-to-best/1”

Vi,g=Xi,g+F(Xbest,g-Xi,g)+F(Xr1,g-Xr2,g)。

(33)

5)“DE/rand/2”

Vi,g=Xr1,g+F(Xr2,g-Xr3,g)+F(Xr4,g-Xr5,g)。

(34)

6)“DE/best/2”

Vi,g=Xbest,g+F(Xr1,g-Xr2,g)+

F(Xr3,g-Xr4,g)。

(35)

7)“DE/current-to-rand/1”

Vi,g=Xi,g+F(Xr1,g-Xi,g)+F(Xr2,g-Xr3,g)。

(36)

8)“DE/current-to-pbest/1”

(37)

(2)交叉

在變異完成后將父代個(gè)體進(jìn)行混合，得到一個(gè)試驗(yàn)向量Ui=[ui,1,ui,2,…,ui,j,…,ui,D]，

其中：j=1,2,…,D；vij,g為個(gè)體Vi,g中第j個(gè)元素;jrand為[1,D]范圍內(nèi)的一個(gè)隨機(jī)整數(shù)，D為變異向量的維數(shù);CR為交叉概率，CR∈[0,1]。

(3)選擇

經(jīng)過變異和交叉操作后，得到一個(gè)試驗(yàn)向量Ui，這時(shí)通過貪婪選擇確定Xi,g+1。當(dāng)Ui的適應(yīng)度值大于Xi的適應(yīng)度值時(shí)，Xi,g+1=Ui,g，否則Xi,g+1=Xi,g，

(39)

2.2.2 鯨魚算法與差分進(jìn)化算法、禁忌搜索算法結(jié)合(HWOA2)

禁忌搜索算法的特點(diǎn)是采用禁忌表技術(shù)，即用一個(gè)禁忌表記錄下已經(jīng)到達(dá)過的局部最優(yōu)點(diǎn)，在新一次搜索中，利用禁忌表中的信息不再或有選擇地搜索這些點(diǎn)，以跳出局部最優(yōu)點(diǎn)。將禁忌搜索與鯨魚算法結(jié)合可以增強(qiáng)算法全局搜索能力，算法流程圖如圖5所示。

HWOA2偽代碼如下：

HWOA2

Initialize the whales’ population by Eq...

Calculate the fitness of each search agent, X*=the best search agent.

while1(c1

while2(t

for each search agent

Updatea,A,C,Iand p

if1(p<0.5)

if2(|A|<1)

Update the position by Eq.

else if2(|A|<1)

Update the position by Eq.

end if2

else if1(p≥0.5)

Update the position by Eq.

end if1

if3(flag>1)&&(fit(Xi)>fit(X*))

mutation:mutate by Eq.

crossover:cross by Eq.

selection:select by Eq.

flag=0

end if3

flag=flag+1

end for

Check if any search agent goes beyond the search space and amend it.

Calculate the fitness of each search agent, update X*.

t=t+1

end while2

Initial parameters of TS.

if1(t

Generate candidate solutions.Calculate function value.

if2(fit(Xi)

Set the optimal solution with no tabu in candidate solutions as the current solution.

else if2(fit(Xi)≥fit(X*))

Set the solution as the optimal solution.

Update the tabu table.

t=t+1

end if1

c1=c1+1

end while1

return X*

3 計(jì)算結(jié)果及分析

本文所有算例測試試驗(yàn)均是在Window 10操作系統(tǒng)下進(jìn)行，計(jì)算機(jī)硬件配置為：Intel(R)Core(TM)i5-9500U，主頻3.0 GHz，內(nèi)存8 GB。計(jì)算軟件所用版本為：Lingo 11和MATLAB R2016b。本文用到的標(biāo)準(zhǔn)算例S5，S6，S7，S8，S9，S9H，S10，S11，S15來自文獻(xiàn)[26]，N25-05和N30-05來自文獻(xiàn)[27]，N40-01來自文獻(xiàn)[28]，sko42-01和sko49-01來自文獻(xiàn)[29]。

為驗(yàn)證了混合整數(shù)規(guī)劃模型的正確性，利用精確求解器Lingo 11對小規(guī)模雙向多路徑交互環(huán)形過道布置問題進(jìn)行求解，計(jì)算結(jié)果如表2所示。

表2 Lingo求解結(jié)果

Lingo對于設(shè)施數(shù)小于9的測試算例S5～S8均求得最優(yōu)解，驗(yàn)證了第2章所提混合整數(shù)規(guī)劃模型的正確性。但是在對設(shè)施數(shù)為9及以上規(guī)模算例求解時(shí)，Lingo由于自身局限性和問題的復(fù)雜程度，對設(shè)施數(shù)為9的S9問題求到全局最優(yōu)解需要11 464 s。9～15規(guī)模算例已經(jīng)不能夠在較短的時(shí)間內(nèi)進(jìn)行精確計(jì)算，因此對設(shè)施數(shù)為9及以上的問題記錄運(yùn)行3 600 s時(shí)，求得局部最優(yōu)解。當(dāng)設(shè)施數(shù)達(dá)到25時(shí)，在3 600 s內(nèi)已無法求出局部最優(yōu)解。

利用第3章所提混合鯨魚算法對雙向多路徑交互環(huán)形過道布置問題進(jìn)行求解，算法參數(shù)設(shè)置如表3所示。

表3 算法參數(shù)設(shè)置

為了評估所提混合鯨魚算法的性能，對比了WOA，HWOA1和HWOA2等3種算法求解不同規(guī)模雙向多路徑交互環(huán)形過道布置問題的結(jié)果。對不同規(guī)模算例進(jìn)行20次測試試驗(yàn)，結(jié)果對比如表4所示，測試的最優(yōu)計(jì)算結(jié)果及設(shè)施序列詳細(xì)數(shù)據(jù)如附表1所示。

表4 WOA，HWOA1，HWOA2計(jì)算結(jié)果對比表

續(xù)表4

分析表4計(jì)算結(jié)果，HWOA2對不同規(guī)模問題求得的最小值均小于WOA和HWOA1兩種算法，且求解結(jié)果的標(biāo)準(zhǔn)差較小，HWOA2的求解精度明顯優(yōu)于WOA和HWOA1。HWOA1與WOA算法計(jì)算結(jié)果相比，在設(shè)施數(shù)為40及以上時(shí)，求到的最小值比WOA算法求到的最小值大，但是求解結(jié)果的標(biāo)準(zhǔn)差明顯比WOA要小，這表明引入差分進(jìn)化算法增強(qiáng)了WOA求解雙向多路徑交互環(huán)形過道布置題時(shí)的局部搜索能力，但隨著問題規(guī)模的增大，相同參數(shù)下HWOA1比WOA更容易陷入局部最優(yōu)。而禁忌搜索機(jī)制的引入，克服了算法陷入局部最優(yōu)的缺陷，明顯改善了算法求解雙向多路徑交互環(huán)形過道布置問題的性能。

根據(jù)表4的計(jì)算結(jié)果，繪制WOA算法、HWOA1算法和HWOA2算法14組測試算例均值對比圖，如圖6所示。由表4和圖6可以看出，HWOA2算法14組算例求解結(jié)果均屬最優(yōu)值或近似最優(yōu)值，其對應(yīng)的14組均值為119.8，250.2，374.5，599.1，1 086.3，1 835.0，1 176.3，3 078.0，2 949.7，6 974.8，51 896.1，46 719.9，10 176.3，15 832.8。以上數(shù)據(jù)表明,HWOA2算法在求解雙向多路徑交互環(huán)形過道布置問題時(shí)具有良好的求解性能。

根據(jù)表4的計(jì)算結(jié)果，HWOA1算法和HWOA2算法計(jì)算結(jié)果的標(biāo)準(zhǔn)差與WOA算法計(jì)算結(jié)果相比較小，因此繪制兩種算法計(jì)算結(jié)果的箱型圖，如圖7所示。由于不同規(guī)模問題計(jì)算結(jié)果差距較大，為了使箱型圖更加直觀，繪圖時(shí)將每次計(jì)算得到的數(shù)據(jù)均除以該組數(shù)據(jù)的均值。圖中橫坐標(biāo)1表示HWOA1算法計(jì)算結(jié)果的分布情況，2表示HWOA2算法計(jì)算結(jié)果分布情況。從圖7和表4可以看出，HWOA1算法求解各種規(guī)模算例結(jié)果的標(biāo)準(zhǔn)差為：0.0，9.5，2.3，23.4，6.6，8.3，65.5，48.2，62.1，206.7，1 043.6，1 339.2，153.6，97.6，而HWOA2算法的平均偏差分別為：0.0，0.0，0.0，5.6，0.0，0.0，0.0，16.9，29.7，8.4，122.9，69.9，4.8，11.7，說明HWOA2算法求解更穩(wěn)定。

為驗(yàn)證算法對于環(huán)形過道布置問題法的求解性能，利用HWOA2算法對文獻(xiàn)[11]考慮面積成本的雙目標(biāo)環(huán)形過道布置問題和文獻(xiàn)[12]多路徑交互環(huán)形過道布置問題中13組算例進(jìn)行求解，設(shè)置相同的求解參數(shù)(迭代次數(shù)、種群規(guī)模等)，對不同規(guī)模問題進(jìn)行10次求解，如表5所示。

表5 HWOA2計(jì)算文獻(xiàn)[11]和文獻(xiàn)[12]結(jié)果對比表

通過表5可以看出，與文獻(xiàn)[11]問題相比：8規(guī)模及以下HWOA2算法均可以求得最優(yōu)值，8規(guī)模以上問題HWOA2求得的結(jié)果均優(yōu)于文獻(xiàn)[11]最優(yōu)解，且30規(guī)模最優(yōu)解提升9.60%；與文獻(xiàn)[12]中問題對比：9規(guī)模及以下HWOA2算法均可以求得最優(yōu)值，9規(guī)模以上問題HWOA2求得的結(jié)果優(yōu)于文獻(xiàn)[12]最優(yōu)解，且40規(guī)模最優(yōu)解提升7.32%。

分析表5可知，HWOA2算法對于單一路徑和多路徑環(huán)形過道布置問題求解均表現(xiàn)出良好的求解效率和質(zhì)量。

4 實(shí)例應(yīng)用

X金屬制品廠位于四川省成都市，是一家集設(shè)計(jì)、開發(fā)、制造、銷售、為一體的專業(yè)門窗生產(chǎn)企業(yè)。主要開發(fā)生各種鋼、鋁合金推拉門、防盜門以及其他五金制品。以防盜門為例，其主要生產(chǎn)車間和工藝流程如圖8所示。

該企業(yè)防盜門種類有44種，包括生態(tài)原銅門、仿銅門、電控單元門、復(fù)合門等多種類型，企業(yè)產(chǎn)品供應(yīng)四川省多家醫(yī)院、學(xué)校、校區(qū)等場所。該企業(yè)對市場形勢有非常好的認(rèn)知，生產(chǎn)的新型防盜門使用玻璃夾層，不但起到了良好的防盜作用，并且透光、美觀、保溫效果好，產(chǎn)品受到廣大消費(fèi)者的青睞。連續(xù)幾年，企業(yè)處于供不應(yīng)求的狀態(tài)。

由于該公司生產(chǎn)產(chǎn)品種類較多，制造過程以離散為主，流程為輔。在這種生產(chǎn)情況下，不能采用單一流水線生產(chǎn)，車間區(qū)域布置較為混亂。根據(jù)課題組2016年對其生產(chǎn)情況的調(diào)研發(fā)現(xiàn)，該公司生產(chǎn)車間布置缺乏科學(xué)理論的指導(dǎo)，導(dǎo)致車間搬運(yùn)效率較低，生產(chǎn)周期較長。針對該公司生產(chǎn)狀況，本章對該企業(yè)生產(chǎn)車間布局進(jìn)行分析和優(yōu)化。

該生產(chǎn)車間各區(qū)域的長度信息以及對應(yīng)的主要加工設(shè)備如表6所示，各區(qū)域之間的物流交互量如表7所示。在現(xiàn)存布局情況下，車間的總物流成本為69 157.27 kg·m。

表6 加工區(qū)設(shè)備信息

由于防盜門的生產(chǎn)周期為20天左右，從顧客預(yù)訂到上門安裝大概一個(gè)月左右，因此課題組統(tǒng)計(jì)車間加工區(qū)一個(gè)月的物流量，針對一個(gè)標(biāo)準(zhǔn)防盜門的生產(chǎn)工藝流程，所用到的設(shè)備是確定的，各設(shè)備之間的物流量也是確定的，但是一個(gè)月的時(shí)間內(nèi)，加工車間并不是生產(chǎn)單一產(chǎn)品，除了防盜門，還有窗以及其他五金制品。因此，加工區(qū)物流量并不是生產(chǎn)單一產(chǎn)品時(shí)物流量，不同設(shè)備之間存在較大的物料流動(dòng)。經(jīng)過統(tǒng)計(jì)和整理，該車間加工區(qū)物流量如表7所示。

表7 加工區(qū)物流量 kg

從表7以看出，在統(tǒng)計(jì)中并沒有區(qū)分每兩個(gè)區(qū)域之間的物流量的方向，如區(qū)域1到區(qū)域3的物流量為320 kg，從區(qū)域3到區(qū)域1的物流量也為320 kg。其實(shí)，320表示的為區(qū)域1和區(qū)域3之間總的物流量，不涉及物料流動(dòng)的方向。

運(yùn)用所提混合鯨魚算法對該實(shí)例進(jìn)行求解，算法運(yùn)行環(huán)境與參數(shù)設(shè)置均與第4章算法參數(shù)設(shè)置相同。應(yīng)用閉環(huán)布局形式對車間優(yōu)化后的設(shè)施序列為2-9-7-6-4，1-3-5-8-10，優(yōu)化后物流成本降低到60 124.14 kg·m，較原布局方案減少了13%的成本。然而，由于受到重排成本、加工設(shè)備精度要求、電氣管道布置、場地大小等因素的限制，車間的實(shí)際布局情況較本文提出的雙向環(huán)形過道布置問題更為復(fù)雜，因而本文得出的布局優(yōu)化方案與實(shí)際最優(yōu)方案還存在一定的差距，仍需進(jìn)行深入研究，進(jìn)一步擴(kuò)展問題模型。

5 結(jié)束語

本文提出了雙向環(huán)形過道布置問題，并建立其混合整數(shù)規(guī)劃模型，通過精確求解器Lingo對小規(guī)模問題求精確解，驗(yàn)證了混合整數(shù)規(guī)劃模型的正確性。針對所提問題，提出了混合鯨魚算法，在WOA中引入差分進(jìn)化和禁忌搜索策略來求解大規(guī)模雙向環(huán)形過道布置問題，加入差分進(jìn)化操作提高了WOA的局部搜索能力，禁忌搜索機(jī)制增強(qiáng)了算法的全局搜索能力。為了評價(jià)混合鯨魚算法，首先用該算法求解了14個(gè)不同規(guī)模算例，并與文中2個(gè)算法進(jìn)行比較；其次，用該算法分別求解環(huán)形過道布置問題和多路徑交互環(huán)形過道布置問題，并與參考文獻(xiàn)中的結(jié)果進(jìn)行對比。兩個(gè)試驗(yàn)結(jié)果驗(yàn)證了所提算法的性能優(yōu)于對比算法。最后將混合鯨魚算法應(yīng)用到實(shí)際問題中，為車間布局提出了改善建議。

當(dāng)前研究主要集中在單層與靜態(tài)環(huán)形過道布置問題，后續(xù)將針對更符合實(shí)際生產(chǎn)的多層及動(dòng)態(tài)環(huán)形設(shè)施布局問題進(jìn)行深入分析和解讀。