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

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

0 引言

設(shè)施布局問(wèn)題(Facility Layout Problem, FLP)指按確定的布局形式，在滿(mǎn)足一定約束的情況下，對(duì)其所屬的多個(gè)設(shè)施單元進(jìn)行布置。設(shè)施布局是影響生產(chǎn)效率和成本的重要因素之一，科學(xué)的設(shè)施布局可以有效提高空間利用率、合理化物流路徑，降低生產(chǎn)過(guò)程中10%～30%的物料搬運(yùn)成本并提高生產(chǎn)效率[1]。由于其重要的研究意義和實(shí)際應(yīng)用價(jià)值，工業(yè)界和學(xué)術(shù)界對(duì)FLP進(jìn)行了一系列研究與實(shí)踐[2-6]。

過(guò)道布置問(wèn)題(Corridor Allocation Problem, CAP)是FLP中的一個(gè)分支，由AMERAL[7]于2012年首次提出，其主要特點(diǎn)為：以最小化設(shè)施間的總物料搬運(yùn)成本為目標(biāo)，通道兩側(cè)的設(shè)施從同一起點(diǎn)開(kāi)始布置，且相鄰設(shè)施間無(wú)間隙。由于CAP具有較好的物流運(yùn)輸結(jié)構(gòu)和效率，被廣泛應(yīng)用于工業(yè)和服務(wù)領(lǐng)域，如醫(yī)院走廊兩側(cè)各職能房間的布置[8]、學(xué)校學(xué)習(xí)及辦公室的安排[9]、大型購(gòu)物中心商鋪的布局、半導(dǎo)體生產(chǎn)線(xiàn)的布置[4]等。針對(duì)CAP問(wèn)題的NP-hard屬性，眾多學(xué)者設(shè)計(jì)了不同的智能算法，均取得較好的結(jié)果[10-11]。為進(jìn)一步深入探究CAP，學(xué)者們結(jié)合實(shí)際應(yīng)用不斷對(duì)傳統(tǒng)CAP進(jìn)行拓展。劉思璐等[12]提出考慮設(shè)施深度的CAP，并采用煙花算法進(jìn)行求解；ZHANG等[13]在傳統(tǒng)CAP的基礎(chǔ)上加入過(guò)道寬度約束，采用改進(jìn)分散式搜索算法進(jìn)行仿真求解；管超等[14]考慮雙層布局更節(jié)約布局用地成本，以及實(shí)際生產(chǎn)中場(chǎng)地受限制等情況，提出以最小化物料搬運(yùn)成本為目標(biāo)的雙層CAP，建立雙層CAP的混合整數(shù)規(guī)劃模型，隨后設(shè)計(jì)改進(jìn)花授粉算法進(jìn)行求解[15]；王沙沙等[16]結(jié)合生產(chǎn)中的環(huán)形布局特征，提出多路徑交互環(huán)形CAP，并采用改進(jìn)蟻獅算法進(jìn)行求解。以上研究主要集中在優(yōu)化物料搬運(yùn)成本，而在實(shí)際車(chē)間布局中還需要同時(shí)優(yōu)化布局成本、空間利用率等多個(gè)目標(biāo)。KALITA等[17]在2014年考慮通道長(zhǎng)度對(duì)布局成本的影響，以最小化過(guò)道長(zhǎng)度和物料搬運(yùn)成本為目標(biāo)，首次提出雙目標(biāo)過(guò)道布置問(wèn)題(bi-objective CAP, bCAP)，并設(shè)計(jì)多目標(biāo)遺傳算法求解，然后于2019年設(shè)計(jì)融合局部搜索技術(shù)的改進(jìn)遺傳算法求解bCAP[18]。隨后，學(xué)者們考慮通道寬度和設(shè)施受約束等情況對(duì)基礎(chǔ)bCAP問(wèn)題進(jìn)行拓展[19-20]。賈林等[21]在環(huán)形布局問(wèn)題中將布局面積作為優(yōu)化目標(biāo)之一，建立了雙目標(biāo)環(huán)形CAP的數(shù)學(xué)模型，并對(duì)面積成本與總物流成本作無(wú)量綱處理，將兩個(gè)目標(biāo)統(tǒng)籌為總成本進(jìn)行優(yōu)化，結(jié)果證明設(shè)施布置方案對(duì)布局面積有較大影響。然而，在與直線(xiàn)型CAP相關(guān)的研究中，鮮有學(xué)者考慮優(yōu)化布局面積。布局面積又是影響布局用地成本的重要因素之一，對(duì)于利潤(rùn)空間較小的制造業(yè)，即使用地成本的小幅下降也可能轉(zhuǎn)化為可觀的額外利潤(rùn)，因此將最小化布局面積作為新增優(yōu)化目標(biāo)能更好地提高面積利用率，降低車(chē)間用地成本。另外，物料搬運(yùn)成本與布局面積的量綱存在差異，而且不同決策者對(duì)兩方面的側(cè)重點(diǎn)不同，針對(duì)上述兩個(gè)目標(biāo)優(yōu)化布局問(wèn)題能夠提供多個(gè)較優(yōu)決策方案來(lái)滿(mǎn)足不同場(chǎng)景的需求。

設(shè)施方向是設(shè)施布置約束之一[22]，不等面積布局研究中通?？紤]設(shè)施方向?qū)δ繕?biāo)函數(shù)的影響[23]。在CAP問(wèn)題上通常默認(rèn)設(shè)施布置方向一定，而在生產(chǎn)或服務(wù)部門(mén)，各矩形設(shè)施寬度和深度不同的情況比較常見(jiàn)，在設(shè)施布置方向無(wú)特殊規(guī)定時(shí)，矩形設(shè)施可以以相鄰兩側(cè)的任意一側(cè)靠近過(guò)道。此時(shí)，即使設(shè)施布置順序相同，矩形設(shè)施布置方向的變化也會(huì)導(dǎo)致設(shè)施的物料交互點(diǎn)位置改變，最終使設(shè)施間的物料搬運(yùn)成本和布局面積出現(xiàn)差異。因此，在矩形設(shè)施的深度和寬度不同的CAP中，考慮設(shè)施的布置方向可以避免占用多余的用地面積，減少物流成本。

綜上所述，由于布局面積直接影響布局成本，而且考慮矩形設(shè)施布置方向可有效降低物流成本，提高面積利用率，本文以最小化物料搬運(yùn)成本和布局面積為目標(biāo)，考慮設(shè)施布置方向，提出一種擴(kuò)展雙目標(biāo)過(guò)道布置問(wèn)題(extend bi-objective Corridor Allocation Problem, ebCAP)，并構(gòu)建了該問(wèn)題的混合整數(shù)非線(xiàn)性規(guī)劃模型(Mixed Integer Nonlinear Programming model, MINLP)，然后通過(guò)LINGO軟件精確求解證明所提模型的正確性，并為算法提供參考依據(jù)。由于精確求解需遍歷整個(gè)解空間，求解大規(guī)模問(wèn)題難度高，本文提出一種基于Pareto占優(yōu)和模擬退火搜索的多目標(biāo)改進(jìn)分散搜索(Multi-objective Improved Scatter Search, MISS)算法。該算法以雙層編碼構(gòu)造可行解，采用自適應(yīng)模擬退火操作雙向改進(jìn)精英參考集，動(dòng)態(tài)更新參考集以及時(shí)利用新個(gè)體優(yōu)勢(shì)，并設(shè)置閾值減少多余迭代過(guò)程。應(yīng)用所提算法求解設(shè)施布置方向不受限的雙目標(biāo)CAP，再通過(guò)與精確算法計(jì)算結(jié)果對(duì)比，證明了MISS算法的有效性。為進(jìn)一步說(shuō)明MISS算法的優(yōu)越性，應(yīng)用所提算法求解bCAP問(wèn)題，并與其他算法的求解結(jié)果對(duì)比，證明了MISS算法具有更高的求解效率和質(zhì)量。

1 ebCAP數(shù)學(xué)模型

1.1 問(wèn)題描述

傳統(tǒng)CAP以最小化物料搬運(yùn)成本為目標(biāo)，將給定的n個(gè)大小不同的矩形設(shè)施合理地排布在過(guò)道兩側(cè)。在CAP中要求相鄰設(shè)施間無(wú)間隙，兩行設(shè)施均從左側(cè)同一水平線(xiàn)開(kāi)始向右布置，各矩形設(shè)施的物料交互點(diǎn)位于設(shè)施靠近通道一側(cè)的中點(diǎn)。物料交互點(diǎn)的坐標(biāo)可以直接根據(jù)所有設(shè)施的相對(duì)位置確定。與傳統(tǒng)CAP相比，ebCAP以最小化總物料搬運(yùn)成本和布局面積為目標(biāo)，考慮了通道寬度對(duì)物流成本的影響，且矩形設(shè)施的布置方向靈活可變。因此，處理ebCAP時(shí)需確定設(shè)施的布置順序，并明確設(shè)施的布置方向。然而，ebCAP不僅為以上兩個(gè)問(wèn)題疊加，設(shè)施布置順序還會(huì)影響設(shè)施布置方向；反之，設(shè)施布置方向不同時(shí)，最優(yōu)設(shè)施布置序列也會(huì)變化。因此,ebCAP的關(guān)鍵在于找到最適配的設(shè)施布置順序和設(shè)施布置方向，以實(shí)現(xiàn)物料搬運(yùn)成本和布局面積的最小化。

另外，設(shè)施布置方向?qū)ξ锪习徇\(yùn)成本和布局面積有較大影響，如圖1所示的9規(guī)模設(shè)施布局方案，3個(gè)方案中設(shè)施的相對(duì)位置相同(第1行{9 1 5 2}，第2行{4 7 8 6 3})，圖1a中任意設(shè)施i只能以邊L1i靠近過(guò)道，圖1b和圖1c則分別為設(shè)施方向不固定時(shí)物料搬運(yùn)成本最小和布局面積最小所對(duì)應(yīng)的布局方案。圖中c，H，L0分別表示通道寬度、布局寬度和通道長(zhǎng)度，L1i和L2i分別為矩形設(shè)施i相鄰兩邊的長(zhǎng)度。由圖1明顯可見(jiàn)，圖1a～圖1c中部分設(shè)施方向的變化影響了布局的寬度H和通道長(zhǎng)度L0，進(jìn)而影響了布局方案的面積。同時(shí)，設(shè)施物料交互點(diǎn)也隨之變動(dòng)，導(dǎo)致設(shè)施間的物料搬運(yùn)成本發(fā)生變化。

1.2 基本假設(shè)條件

(1)設(shè)施形狀為矩形，且設(shè)施間的單位距離物流交互成本已知。

(2)設(shè)施的物流交互中心位于設(shè)施靠近通道一側(cè)的中點(diǎn)。

(3)相鄰設(shè)施之間無(wú)間隙。

(4)上下行設(shè)施均從最左側(cè)起沿通道邊線(xiàn)布置，即各行布置起點(diǎn)的橫坐標(biāo)為0。

(5)設(shè)施布置方案不受場(chǎng)地大小及其他條件限制。

(6)矩形設(shè)施的布置方向不固定。

1.3 數(shù)學(xué)模型

為便于描述模型，給出參數(shù)與變量的定義，如表1所示。

表1 參數(shù)與變量定義

續(xù)表1

本文采用曼哈頓距離計(jì)算設(shè)施間的物料搬運(yùn)距離，如圖2所示。圖中虛線(xiàn)表示設(shè)施間的物流交互路徑，設(shè)施的物流交互點(diǎn)位于設(shè)施靠過(guò)道一側(cè)的中點(diǎn)，用“■”表示。若設(shè)施同行布置，如設(shè)施i和設(shè)施m，則設(shè)施間的物流交互距離dim為設(shè)施橫坐標(biāo)差xm-xi；若設(shè)施異行布置，如設(shè)施i和設(shè)施j，則設(shè)施間的物流交互距離為c+xj-xi。

根據(jù)雙行布局問(wèn)題中布局面積的定義[24-25]，布局面積為能覆蓋布局方案中所有設(shè)施的最小矩形區(qū)域的占地面積，其中矩形區(qū)域的寬度稱(chēng)為布局寬度H，尺寸由每行中最深的機(jī)器確定。如圖2所示，H等于上下行設(shè)施深度最深的設(shè)施m和j的深度與通道寬度c的和；矩形區(qū)域的長(zhǎng)度等于通道長(zhǎng)度L0，為最左側(cè)起點(diǎn)到最右側(cè)設(shè)施右端點(diǎn)的水平距離。

如圖3所示，本文統(tǒng)稱(chēng)設(shè)施靠過(guò)道一側(cè)的邊長(zhǎng)為設(shè)施的寬度，與過(guò)道垂直的邊的長(zhǎng)度為設(shè)施深度。矩形設(shè)施i的寬度有L1i，L2i兩種情況，決策變量ri用于確定設(shè)施i的寬度和深度，ri=1表示設(shè)施i的寬度為L(zhǎng)1i，ri=0表示設(shè)施i的寬度為L(zhǎng)2i，因此設(shè)施i的寬度wi和深度Di分別為：

wi=ri·L1i+(1-ri)·L2i,1≤i≤n；

(1)

Di=ri·L2i+(1-ri)·L2i,1≤i≤n。

(2)

當(dāng)ri=1時(shí)(1-ri)=0，設(shè)施i以邊L1i靠近過(guò)道，因此設(shè)施i的寬度為L(zhǎng)1i，深度為L(zhǎng)2i。

綜上所述，設(shè)施布置方向不受限的ebCAP數(shù)學(xué)模型如下：

目標(biāo)函數(shù)：

F=min{F1,F2}；

(3)

(4)

F2=L0·H。

(5)

s.t.

(6)

dij≥xi-xj,1≤i

(7)

dij≥xj-xi,1≤i

(8)

(9)

1≤i,j≤n,i≠j；

(10)

(11)

H≥Di·yiU+Dj·yjD+c,

1≤i,j≤n,i≠j；

(12)

1≤i

(13)

Zijk+Zjik+1≥yik+yjk,

1≤i

(14)

1≤i,j≤n,i≠j；

(15)

(16)

yik∈{0,1},1≤i≤n,k∈K；

(17)

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

(18)

ri∈{0,1},1≤i≤n；

(19)

Zijk∈{0,1},1≤i,j≤n,i≠j,k∈K。

(20)

本文在模型中引入決策變量yik，qij，ri，Zijk，以確定各設(shè)施的排列順序和布置方向，進(jìn)而確定設(shè)施的相對(duì)位置和精確位置。式(3)表示兩個(gè)目標(biāo)函數(shù)最小化。式(4)為目標(biāo)函數(shù)F1，表示總物料搬運(yùn)成本，其中dij+c(1-qij)為設(shè)施i，j之間的物流交互距離，若兩個(gè)設(shè)施布置在同行，則qij=1，設(shè)施間的物流交互距離為dij；若兩設(shè)施異行布置，則qij=0，物流交互距離為dij+c。式(5)表示最小化設(shè)施布局方案的總面積，其取值為能夠包圍布局方案的最小矩形區(qū)域的面積，F(xiàn)2達(dá)到最小意味著在該布局方案下，所有設(shè)施所在的矩形區(qū)域中未被利用的空余面積最小，此時(shí)平面空間利用率最高，其中布局方案的總占地面積表示為L(zhǎng)0H，H為布局寬度，H=max{Di×yiU,Di×yiD}，L0為通道長(zhǎng)度，L0=max{wi×yiU,wi×yiD}。

約束條件中，式(6)為設(shè)施的坐標(biāo)約束，用以確定各設(shè)施的物流交互中心位置；式(7)和式(8)用于確定各設(shè)施之間沿過(guò)道的水平距離dij；式(9)確保每個(gè)設(shè)施只能布置在過(guò)道一側(cè)；式(10)避免布置在同一行的兩相鄰設(shè)施重疊，若設(shè)施i與設(shè)施j布置在同行，且設(shè)施i在設(shè)施j的左側(cè)，則Zijk=1，兩設(shè)施滿(mǎn)足xj-xi≥(wi+wj)/2，即約束布置在同一行的兩相鄰設(shè)施坐標(biāo)的最小距離；式(11)和式(12)分別用于約束布局區(qū)域總長(zhǎng)度和寬度；式(13)和式(14)用于約束二進(jìn)制變量Zijk；式(15)和式(16)用于約束變量qij；式(17)～式(20)限定0-1決策變量的取值。

2 求解ebCAP的MISS算法

分散搜索(Scatter Search, SS)算法[26]是一種元啟發(fā)式進(jìn)化算法，具有能同時(shí)兼容多種調(diào)節(jié)機(jī)制的柔性框架，易與其他算法結(jié)合[27]。該算法采用系統(tǒng)性的方法構(gòu)造新解，并兼顧種群的最優(yōu)性和多樣性，適用于求解多目標(biāo)優(yōu)化問(wèn)題。SS算法最初是為連續(xù)性的單目標(biāo)優(yōu)化問(wèn)題而設(shè)計(jì)的，近年來(lái)許多學(xué)者將分散搜索算法與其他算法融合，用于求解多目?jī)?yōu)化問(wèn)題[28-30]，并取得了較為滿(mǎn)意結(jié)果。因此，針對(duì)ebCAP問(wèn)題的離散優(yōu)化和多目標(biāo)優(yōu)化特性，本文開(kāi)發(fā)了一種基于Pareto占優(yōu)和模擬退火搜索的MISS算法。MISS算法的主要思想為：

(1)采用雙層編碼定義可行解，每個(gè)可行解由代表設(shè)施布置的實(shí)數(shù)序列和代表設(shè)施布置方向的0-1編碼序列表示。

(2)隨機(jī)產(chǎn)生初始種群，并通過(guò)非支配排序選擇精英參考集，根據(jù)多樣性指標(biāo)選擇多樣性參考集。

(3)在參考集中選取父代，基于雙層交叉和雙層變異算子產(chǎn)生子代，并通過(guò)連續(xù)局部變異操作擾動(dòng)第2層編碼來(lái)改良子代個(gè)體。

(4)動(dòng)態(tài)更新參考集以及時(shí)利用子集優(yōu)勢(shì)，設(shè)立外部檔案避免遺失非劣解。

(5)為避免可行解陷入局部最優(yōu)，采用局部變異算子改進(jìn)參考集，通過(guò)自適應(yīng)模擬退火雙向改進(jìn)機(jī)制提高參考集的質(zhì)量，并自適應(yīng)終止算法，避免重復(fù)性的迭代工作。

2.1 解序列的編碼和解碼

解的編碼方式對(duì)算法的求解效果極其重要，根據(jù)所提問(wèn)題特點(diǎn)，本文采用雙層編碼方式定義可行解。可行解表示為{π,Y}，其中：π為第1層編碼，是可行解的前n個(gè)單元，采用實(shí)數(shù)編碼，用有序的設(shè)施編號(hào)排列表示設(shè)施布置方案，排列中設(shè)施編號(hào)的位置即為相對(duì)應(yīng)設(shè)施的位置；Y為第2層編碼，是可行解的n+1～2n單元，采用0-1編碼，Y作為設(shè)施寬度索引確定設(shè)施寬度取值，當(dāng)索引值為1時(shí)，表示設(shè)施寬度為L(zhǎng)1i。若設(shè)施數(shù)為n，則隨機(jī)排列設(shè)施集合{1,2,3,…,n}中的設(shè)施有n！種可行解。用參數(shù)m表示布置在通道上行的設(shè)施數(shù)，m∈{1,2,3,…,n/2}，因此通道兩側(cè)設(shè)施數(shù)量的分布情況有?(n-1)/2?種組合方式(??表示向下取整)。確定上下行設(shè)施布置順序后，需確定各個(gè)設(shè)施的寬度和深度，以0-1編碼作為設(shè)施寬度索引，每個(gè)設(shè)施的布置方向有兩種方案，每種設(shè)施布置順序下設(shè)施寬度或深度有2n種可能，因此對(duì)于問(wèn)題規(guī)模為n的設(shè)施寬度不定的CAP，共有(n-1)·n!·2n-1種布局方案。

為更加直觀地展示編碼與解碼過(guò)程，以設(shè)施規(guī)模n=6的ebCAP問(wèn)題為例，具體示例如圖4所示。一個(gè)可行解x={4 1 3 2 5 6 1 0 0 1 1 0}，其中m=2表示布置在第1行的設(shè)施數(shù)為兩個(gè)，其設(shè)施布置序列為{4 1}，設(shè)施寬度索引序列為{10}，布置在第2行的設(shè)施序列為{3 2 5 6}，設(shè)施寬度索引序列為{0 1 1 0}。

如圖4所示，假設(shè)上述可行解中各矩形設(shè)施相鄰兩邊L1i和L2i對(duì)應(yīng)的向量為L(zhǎng)1=[6 6 4 3 3 1]，L2=[4 4 6 2 1 3]?？尚薪鈞={4 1 3 2 5 6 1 0 0 1 1 0}，m=2時(shí)，設(shè)施4與設(shè)施1的寬度索引值分別為1和0，表示設(shè)施4以邊L14靠近過(guò)道邊線(xiàn)，設(shè)施1以邊L21靠近過(guò)道邊線(xiàn)，因此設(shè)施4與設(shè)施1的寬度w4=3×1+2×(1-1),w1=6×0+4×(1-0)。同理確定其余設(shè)施的寬度和深度，得到寬度向量W和深度向量D，W=[4 6 6 3 3 3]，D=[1 6 4 4 1 1]；最后根據(jù)上述數(shù)據(jù)可以確定設(shè)施坐標(biāo)、布局寬度和長(zhǎng)度，進(jìn)一步得到可行解的布局面積和物料搬運(yùn)成本,并根據(jù)兩個(gè)目標(biāo)評(píng)價(jià)可行解，詳見(jiàn)第1.3節(jié)。

2.2 多目標(biāo)處理方法

目前，與CAP相關(guān)的大部分研究主要以最小化總物料搬運(yùn)成本為唯一目標(biāo)，本文在最小化總物料搬運(yùn)成本的基礎(chǔ)上新增目標(biāo)F2(最小化總布局面積)。與單目標(biāo)優(yōu)化問(wèn)題相比，多目標(biāo)問(wèn)題的各個(gè)目標(biāo)之間存在沖突和量綱差異，無(wú)法直接比較解的大小。為此，本文用Pareto占優(yōu)思想處理雙目標(biāo)問(wèn)題，對(duì)于任意兩個(gè)可行解x1和x2存在支配、被支配和互不支配3種關(guān)系。若任意兩個(gè)可行解x1和x2滿(mǎn)足式(21)，則稱(chēng)x1支配x2，或稱(chēng)x1Pareto占優(yōu)于x2。若可行解x1不被任何解支配，則稱(chēng)x1為非劣解。多目標(biāo)問(wèn)題的非劣解通常不止一個(gè)，由多個(gè)非劣解組成的非劣解集對(duì)應(yīng)的目標(biāo)矢量組成的曲面或曲線(xiàn)稱(chēng)為Pareto前沿。

(21)

為避免在迭代過(guò)程中丟失高質(zhì)量解，算法每次迭代產(chǎn)生的非劣解都會(huì)記錄到外部檔案并進(jìn)行更新。外部檔案非劣解數(shù)量過(guò)多會(huì)降低算法運(yùn)行速率，兼顧求解質(zhì)量和運(yùn)算效率，引入帶精英策略的快速非支配排序遺傳算法(fast elitist Non-dominated Sorting Genetic Algorithm, NSGA-Ⅱ)中的擁擠距離機(jī)制[31]使解集均勻分布，并設(shè)置外部檔案的容量為10。擁擠距離由相鄰個(gè)體的幾何距離確定，分別基于目標(biāo)F1，F(xiàn)2對(duì)可行解進(jìn)行升序排列，在目標(biāo)s下排序?yàn)榈趇的可行解對(duì)應(yīng)Fs的擁擠距離為

(22)

關(guān)于兩個(gè)目標(biāo)的第i個(gè)非劣解xi的擁擠距離為

(23)

2.3 多樣性評(píng)價(jià)標(biāo)準(zhǔn)

因?yàn)榉稚⑺阉魉惴ㄗ⒅貐⒖技亩鄻有院蛢?nèi)部最優(yōu)性，所以結(jié)合ebCAP的特點(diǎn)對(duì)文獻(xiàn)[32]的多樣性產(chǎn)生方法進(jìn)行改進(jìn)，提出如式(24)所示的多樣性評(píng)價(jià)標(biāo)準(zhǔn)構(gòu)建多樣性初始參考集。

D(x1,x2)=

(24)

2.4 交叉算子與變異算子

分散搜索算法中子代解來(lái)源于參考集refset，通過(guò)精英解集和多樣性解集組合產(chǎn)生新解?？紤]可行解的雙層編碼結(jié)構(gòu)特點(diǎn)，本文基于部分映射雜交法(Partial-Mapped Crossover, PMX)設(shè)計(jì)雙層交叉算子，具體過(guò)程如圖5所示。其中雙層交叉運(yùn)算的兩個(gè)父代個(gè)體為Parent1={πp1,Yp1}，Parent2={πp2,Yp2}，交叉后生成的子代個(gè)體分別為Offspring1={πs1,Ys1}，Offspring2={πs2,Ys2}，隨機(jī)選擇兩個(gè)父代個(gè)體的第1層編碼πp1，πp2中的基因片段進(jìn)行交叉操作，并對(duì)第2層編碼序列Yp1，Yp2中對(duì)應(yīng)的基因片段進(jìn)行交叉處理，最后采用部分映射方法消除編號(hào)沖突。

變異算子包括雙層變異算子和局部變異算子，如圖6所示。雙層變異算子通過(guò)交換任意兩個(gè)基因產(chǎn)生新個(gè)體，操作過(guò)程中兩層基因需同步互換變異，即隨機(jī)選擇第1層序列πs1上的兩個(gè)位置，將兩個(gè)位置上的基因互換，同時(shí)確定第2層序列Ys1上相對(duì)應(yīng)的兩個(gè)位置并互換基因。由于本文所提ebCAP考慮矩形設(shè)施布置方向，為使設(shè)施布置方向改變產(chǎn)生新解，針對(duì)第2層編碼序列Ys1設(shè)置局部變異算子，隨機(jī)選擇序列Ys1中的任意基因g，通過(guò)公式g=abs(1-g)進(jìn)行變異操作。

2.5 產(chǎn)生初始參考集

參考集refset由精英參考集refset1和多樣性參考集refset2組成。對(duì)當(dāng)前種群進(jìn)行非支配排序，排序等級(jí)在前b1位的高質(zhì)量可行解構(gòu)成精英參考集refset1，refset2則按多樣性評(píng)價(jià)標(biāo)準(zhǔn)從剩余P-b1個(gè)個(gè)體中選取與精英參考集多樣性程度最高的2個(gè)解放入多樣性參考集refset2，然后在剩余個(gè)體中選取與當(dāng)前refset2中已有個(gè)體的多樣性程度最高的解放入refset2，重復(fù)該過(guò)程直到完成多樣性參考集refset2的構(gòu)造。

當(dāng)前個(gè)體xo與精英參考集refset1的多樣性程度

(25)

當(dāng)前個(gè)體xo與當(dāng)前多樣性參考集refset2所含個(gè)體的多樣性程度

(26)

2.6 子集的產(chǎn)生

因?yàn)樽蛹械慕鈦?lái)源于參考集，所以在精英參考集和多樣性參考集中隨機(jī)選取兩個(gè)父代個(gè)體組合為新個(gè)體。針對(duì)ebCAP雙層編碼的特性，子集的產(chǎn)生分為兩個(gè)階段：①對(duì)父代個(gè)體進(jìn)行雙層交叉和雙層變異操作，得到設(shè)施布置順序改變但設(shè)施布置方向保持不變的新個(gè)體；②對(duì)當(dāng)前新個(gè)體的第2層編碼(設(shè)施寬度索引序列Y)采用局部變異操作，以?xún)?yōu)化新個(gè)體的設(shè)施布置方向，最終產(chǎn)生子代個(gè)體。子集的產(chǎn)生流程如下：

Input:精英參考集中的父代個(gè)體x1、多樣性參考集中的父代個(gè)體x2、連續(xù)局部變異次數(shù)L0

Initialization parameter：l=0；

Begin

while l

if Δf1(Δf2)<0 or Δf1(Δf2)=0∩Δf2(Δf1)<0；

end if

l=l+1；

end while

2.7 解的改進(jìn)

傳統(tǒng)的分散搜索算法采用局部搜索改進(jìn)當(dāng)前種群的每一個(gè)體，雖然能在一定程度上改進(jìn)當(dāng)前解，但是耗時(shí)較長(zhǎng)。參考集在迭代過(guò)程中指導(dǎo)解的進(jìn)化方向，保持高質(zhì)量的參考集能獲得高質(zhì)量的子集。因此，本文僅針對(duì)參考集中的個(gè)體進(jìn)行改進(jìn)，將解的改進(jìn)分為兩部分：①針對(duì)參考集中所有個(gè)體的第2層編碼(設(shè)施寬度索引序列Y)，采用局部變異算子進(jìn)一步優(yōu)化設(shè)施布置方向，以改進(jìn)目標(biāo)值；②針對(duì)精英參考集，采用自適應(yīng)模擬退火操作來(lái)雙向改進(jìn)精英參考集中的全部個(gè)體，指導(dǎo)精英參考集向兩個(gè)目標(biāo)極值方向優(yōu)化。模擬退火雙向改進(jìn)機(jī)制詳見(jiàn)2.8節(jié)。

2.8 模擬退火雙向改進(jìn)機(jī)制

為及時(shí)更新參考集，避免算法陷入局部最優(yōu)，針對(duì)精英參考集設(shè)計(jì)模擬退火雙向改進(jìn)機(jī)制。針對(duì)目標(biāo)函數(shù)F1，將精英參考集升序排列，排序序數(shù)為奇數(shù)的個(gè)體分配到真子集1，序數(shù)為偶數(shù)的個(gè)體分配至真子集2，真子集1中的個(gè)體以目標(biāo)F1為優(yōu)先改進(jìn)對(duì)象，目標(biāo)F2為次優(yōu)化對(duì)象，真子集2中的個(gè)體以目標(biāo)F2為優(yōu)先改進(jìn)對(duì)象，目標(biāo)F1為次優(yōu)化對(duì)象。由于所提ebCAP是雙目標(biāo)優(yōu)化問(wèn)題，需要對(duì)Metropolis準(zhǔn)則進(jìn)行改進(jìn)，具體為：當(dāng)優(yōu)先改進(jìn)對(duì)象為目標(biāo)F1時(shí)，若F1(xnew)-F1(xold)<0，則接受xnew替代xold；若F1(xnew)-F1(xold)=0且F2(xnew)-F2(xold)<0，則接受xnew替代xold；若F1(xnew)-F1(xold)>0，則在區(qū)間(0,1)內(nèi)隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)P用于決定是否接受新解，若P>rand則接受當(dāng)前解，否則拒絕新解。同理，當(dāng)優(yōu)先改進(jìn)對(duì)象為目標(biāo)F2時(shí)，若F2(xnew)-F2(xold)<0，則接受xnew替代xold；若F2(xnew)-F2(xold)=0且F1(xnew)-F1(xold)<0，則接受xnew替代xold；若F2(xnew)-F2(xold)>0，則在區(qū)間(0,1)內(nèi)隨機(jī)產(chǎn)生一個(gè)隨機(jī)數(shù)P，若P>rand則接受當(dāng)前解，否則拒絕新解。概率P的計(jì)算公式為：

P=

(27)

式中：Δf0=Fo(xnew)-Fo(xold),Δfc=Fc(xnew)-Fc(xold)，Δf0表示新解xnew與當(dāng)前解xold在主要優(yōu)化目標(biāo)Fo上的差值，Δfc表示新解xnew與當(dāng)前解xold在次要優(yōu)化目標(biāo)Fc上的差值，F(xiàn)o，F(xiàn)c∈{F1,F2}且Fo≠Fc。下面為模擬退火雙向改進(jìn)機(jī)制的偽代碼：

Input:參考集中的精英解x、開(kāi)始溫度T0、終止溫度Tend、連續(xù)未優(yōu)化次數(shù)NoptIters、鏈長(zhǎng)L0

Initialization parameter

x→xbest；

Begin

while T

for l0=1:L0

x′=Mutate(x)/采用雙層變異算子和連續(xù)局部變異算子進(jìn)行貪婪搜索，產(chǎn)生新個(gè)體x′；

計(jì)算可行解x′與x在目標(biāo)函數(shù)F1(F2)上的差量Δf1(Δf2)；

Δf1<0 or Δf1=0∩Δf2<0；/優(yōu)先改進(jìn)對(duì)象為目標(biāo)F1時(shí)

(if Δf2<0 or Δf2=0∩Δf1<0；)/優(yōu)先改進(jìn)對(duì)象為目標(biāo)F2時(shí)

x′→x；

else依據(jù)式(32)計(jì)算接受概率P，隨機(jī)數(shù)rand∈(0,1)；

if P>rand

x′→x；

end if

end if

end for

else

inter=inter+1/降溫過(guò)程中最優(yōu)解保持不變的次數(shù)；

end if

if inter>NoptIters/如果連續(xù)未更新次數(shù)達(dá)到NoptIters，則終止迭代。

Break；

end if

T=T·q；

end while

Output:xbest

為兼顧求解質(zhì)量和效率，算法采用自適應(yīng)模擬退火操作對(duì)精英參考集進(jìn)行雙向改進(jìn)。自適應(yīng)模擬退火操作通過(guò)在算法中設(shè)置雙閾值實(shí)現(xiàn)，參數(shù)glob為外部檔案連續(xù)未更新的次數(shù)，參數(shù)switch為進(jìn)行模擬退火雙向改進(jìn)的次數(shù)。若迭代過(guò)程中外部檔案未更新，則glob=glob+1，否則glob=0。當(dāng)外部檔案連續(xù)未更新次數(shù)達(dá)到閾值glob_max(即glob=glob_max)，則觸發(fā)模擬退火操作來(lái)雙向改進(jìn)精英參考集，并令glob=0,switch=switch+1，當(dāng)執(zhí)行雙向改進(jìn)機(jī)制的次數(shù)switch達(dá)到閾值switch_max時(shí)，不再執(zhí)行該操作。

2.9 參考集更新和停止準(zhǔn)則

參考集更新涉及refset1與refset2更新。為提高算法收斂性能，及時(shí)利用新個(gè)體優(yōu)勢(shì)，本文采用動(dòng)態(tài)方法更新參考集，即每產(chǎn)生一個(gè)新個(gè)體，將其與精英參考集中個(gè)體逐一比較，若新個(gè)體能夠支配精英參考集的解，則將原精英參考集中被支配的解移除，將新個(gè)體加入精英參考集，否則將其與多樣性參考集中的個(gè)體進(jìn)行比較，根據(jù)式(26)計(jì)算新個(gè)體與多樣性參考集中個(gè)體的多樣性程度，若新個(gè)體的多樣性?xún)?yōu)于多樣性參考集中的個(gè)體，則用新個(gè)體替換refset2中多樣性最差的個(gè)體。

在保證求解質(zhì)量的前提下，為提高算法求解效率，設(shè)置閾值避免多余的迭代次數(shù)。當(dāng)不再執(zhí)行模擬退火雙向改進(jìn)機(jī)制(switch=switch_max)時(shí)，若迭代過(guò)程中外部檔案連續(xù)未更新次數(shù)達(dá)到glob_max次，則終止迭代。

2.10 算法流程

綜上所述，所提多目標(biāo)MISS算法流程如圖7所示,具體操作步驟如下：

步驟1初始化參考集容量b、內(nèi)循環(huán)最大迭代次數(shù)count_max、外部檔案連續(xù)未更新最大次數(shù)glob_max、第1行能布置設(shè)施數(shù)量的上限m_max和雙向改進(jìn)機(jī)制最大次數(shù)switch_max等，令計(jì)數(shù)器glob=0，switch=0，count=0。

步驟2按照多樣性初始解產(chǎn)生方法生成初始種群，產(chǎn)生初始參考集refset。

步驟3采用模擬退火雙向改進(jìn)機(jī)制改進(jìn)精英參考集refset1，對(duì)參考集refset中的所有個(gè)體進(jìn)行局部變異，并建立外部檔案。

步驟4針對(duì)參考集中任意兩個(gè)解，采用雙層交叉算子和變異算子產(chǎn)生子集，更新參考集，直到參考集中兩兩個(gè)體完成上述操作。

步驟5對(duì)參考集中的所有個(gè)體進(jìn)行局部變異，并更新外部檔案。若外部檔案更新則glob=0，否則glob=glob+1。若glob>glob_max且switchglob_max且switch>switch_max，則退出內(nèi)循環(huán)，令m=m+1，并執(zhí)行步驟8；若glob

步驟6采用模擬退火雙向改進(jìn)機(jī)制改進(jìn)精英參考集refset1,并重置計(jì)數(shù)器glob，令glob=0。

步驟7令count=count+1，若count>count_max則結(jié)束內(nèi)循環(huán)，令m=m+1，并執(zhí)行步驟8；否則，重復(fù)執(zhí)行步驟4和步驟5。

步驟8若m>m_max則算法終止，否則，初始化參數(shù)設(shè)置，并重復(fù)執(zhí)行步驟2～步驟8。

2.11 Pareto解集評(píng)價(jià)指標(biāo)

為分析所提算法性能，采用趨近度指標(biāo)CM[33]和間距指標(biāo)SM[31]評(píng)價(jià)Pareto非劣解集的收斂性和分散程度。CM表示算法所得的Pareto非劣解目標(biāo)空間與真實(shí)Pareto前沿的趨近程度，其值越小，所得Pareto解集越趨近真實(shí)Pareto前沿；SM表示算法所得非劣解在目標(biāo)空間的分布范圍，SM=0表示所得非劣解完全均勻分布，其值越小表示分散程度越高。

CM指標(biāo)表達(dá)式為：

(28)

(29)

SM指標(biāo)表達(dá)式為：

(30)

(31)

(32)

3 算法驗(yàn)證

3.1 ebCAP問(wèn)題驗(yàn)證

本文所有實(shí)驗(yàn)采用的計(jì)算機(jī)硬件配置為Intel(R)Core(TM)i5-8300、主頻2.30 GHz、內(nèi)存8 GB，Windows 10操作系統(tǒng)。由于ebCAP尚無(wú)測(cè)試算例的運(yùn)算結(jié)果，采用LINGO優(yōu)化器根據(jù)MINLP數(shù)學(xué)模型開(kāi)發(fā)相應(yīng)程序求解小規(guī)模算例，以驗(yàn)證所提模型的正確性，并為本文所提算法提供依據(jù)。為驗(yàn)證所提MISS算法的求解性能，應(yīng)用MATLAB R2016b對(duì)40個(gè)不同規(guī)模的測(cè)試算例進(jìn)行仿真試驗(yàn)，測(cè)試算例S5為本文所提算例，其余算例均來(lái)自文獻(xiàn)[12]，設(shè)置模型中的通道寬度為各設(shè)施深度和寬度的最小值，即c=min(min(L1),min(L2))。經(jīng)過(guò)大量算例測(cè)試和程序調(diào)試后，確定的參數(shù)設(shè)置如表2所示，另外兼顧求解效率與質(zhì)量，在大量數(shù)據(jù)測(cè)算后總結(jié)得出兩行分界點(diǎn)m的取值區(qū)間為[floor(n/2)-2,floor(n/2)+1]。參數(shù)含義詳見(jiàn)第2.8節(jié)。

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

表3 MISS算法和精確算法求解ebCAP的結(jié)果

續(xù)表3

對(duì)比LINGO求解器與MISS算法求解結(jié)果，對(duì)于算例S5，所提MISS算法求解得到的極端值與精確算法所得的全局最優(yōu)解相同，證明所建MINLP數(shù)學(xué)模型的正確性以及所提MISS算法的有效性。然而，隨著問(wèn)題規(guī)模的增大，精確求解方法的求解難度增加。設(shè)置LINGO求解器的運(yùn)行時(shí)間為3 600 s時(shí)，精確求解器求解問(wèn)題規(guī)模大于5的算例的結(jié)果略差于MISS算法求得的極端值，且MISS算法得到較優(yōu)解的時(shí)間較短。

3.2 算法評(píng)價(jià)

為驗(yàn)證算法性能，權(quán)衡求解結(jié)果和計(jì)算時(shí)間，以S9，Am13a，H20，N25_03，N30_02，ste_36_02，sko_42_02，sko_49_02為對(duì)象，采用MISS算法對(duì)上述8個(gè)算例重復(fù)運(yùn)行10次，將所得的10組數(shù)據(jù)合并進(jìn)行Pareto篩選，并將得到的非劣解作為各算例的真實(shí)Pareto前沿，分別計(jì)算8個(gè)算例運(yùn)行10次得到的Pareto前沿所對(duì)應(yīng)的10個(gè)CM和SM指標(biāo)，根據(jù)上述指標(biāo)繪制箱型圖，如圖8所示。圖中，上下框線(xiàn)、箱內(nèi)虛線(xiàn)與箱內(nèi)實(shí)線(xiàn)分別對(duì)應(yīng)各指標(biāo)的上下四分位點(diǎn)、平均值和中位值，上邊緣和下邊緣分別表示對(duì)應(yīng)指標(biāo)的最大值和最小值，“+”表示異常值。

3.3 中小規(guī)模算例

鑒于目前尚無(wú)對(duì)ebCAP的研究及仿真運(yùn)算，為驗(yàn)證算法的求解質(zhì)量和效率，采用本文所提MISS算法求解文獻(xiàn)[17]提出的以最小化物料搬運(yùn)成本和最小化過(guò)道長(zhǎng)度為目標(biāo)的bCAP。由于ebCAP和bCAP在編碼方式上的差異(ebCAP采用雙層編碼表示可行解，bCAP采用單層實(shí)數(shù)編碼表示可行解)，MISS算法求解bCAP時(shí)不涉及對(duì)第2層編碼的交叉與變異操作，而且參數(shù)設(shè)置也不同。因此，兼顧求解效率與質(zhì)量，經(jīng)過(guò)大量算例測(cè)試和程序調(diào)試后確定的求解bCAP參數(shù)設(shè)置如表4所示。

表4 MISS求解bCAP的參數(shù)設(shè)置

在求解中小規(guī)模bCAP算例時(shí)，考慮對(duì)比的公平性，每個(gè)算例連續(xù)運(yùn)行30次，與文獻(xiàn)[17]運(yùn)算次數(shù)相同，并選取一組最優(yōu)Pareto非劣解與文獻(xiàn)[17]進(jìn)行比較。表5所示為MISS算法與文獻(xiàn)[17]中pGA(permutation-based genetic algorithm)算法求解中小規(guī)模bCAP測(cè)試算例結(jié)果的對(duì)比，表中第4列和第5列為MISS算法求解的Pareto最優(yōu)解，第6列為算法求解時(shí)間。表中，加粗的數(shù)值表示pGA算法與MISS算法求解的Pareto最優(yōu)解相同，括號(hào)內(nèi)的的數(shù)值表示pGA算法求解的Pareto最優(yōu)值，畫(huà)下劃線(xiàn)的數(shù)值表示對(duì)應(yīng)算法所得結(jié)果更優(yōu)。由表5可得，對(duì)比中小規(guī)模測(cè)試算例，除測(cè)試算例N30_5外，MISS算法均能求得文獻(xiàn)[17]所求10個(gè)算例的最優(yōu)極端值，而且對(duì)于Am12b，Am13a測(cè)試問(wèn)題，MISS算法不但所得結(jié)果更優(yōu)，而且求得與pGA算法所得Pareto最優(yōu)解互不占優(yōu)的非劣解。綜上所述，MISS算法在求解多目標(biāo)中小規(guī)模問(wèn)題上更具優(yōu)勢(shì)。

表5 MISS算法與其他算法求解bCAP中小規(guī)模算例結(jié)果的對(duì)比

續(xù)表5

3.4 大規(guī)模算例

表6 MISS算法與其他算法求解bCAP大規(guī)模算例結(jié)果的對(duì)比

續(xù)表6

對(duì)比表中3種算法的求解結(jié)果，MISS算法所得結(jié)果均能支配文獻(xiàn)[17]中pGA算法所得的兩個(gè)最優(yōu)解；與文獻(xiàn)[18]的混合pGA算法相比，對(duì)于算例AKV60-4和AKV80-4，混合pGA算法所得最優(yōu)解與MISS算法所得最優(yōu)解互不占優(yōu)，均分布在Pareto前沿上，在其余算例的對(duì)比上，除測(cè)試算例AKV60-5，AKV70-5和AKV75-5外，MISS算法所得非劣解完全支配混合pGA的解，求解質(zhì)量更高。綜上，本文所提算法拓寬了Pareto解集的寬度，而且在求解質(zhì)量上更具優(yōu)越性。在求解效率方面，由于文獻(xiàn)[18]未給出求解時(shí)間，僅對(duì)比MISS算法與pGA算法的求解時(shí)間，結(jié)果表明MISS算法運(yùn)行30次的平均時(shí)間均低于pGA算法，其求解效率更高。由以上對(duì)比可知，相比pGA算法和混合pGA算法，MISS算法在求解質(zhì)量和求解效率上具有明顯優(yōu)勢(shì)。

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有CAP研究中忽略布局面積對(duì)成本的影響以及未考慮矩形設(shè)施布置方向的不足，本文以最小化總物料搬運(yùn)成本和布局面積為目標(biāo)，提出考慮設(shè)施方向的雙目標(biāo)CAP，并提出一種MISS算法求解ebCAP，然后通過(guò)大量實(shí)驗(yàn)證明所提算法的優(yōu)越性。本文的主要工作如下：

(1)考慮矩形設(shè)施布置方向，以最小化物流成本和布局面積為目標(biāo)，建立了ebCAP的MINLP模型，并通過(guò)LINGO精確求解器驗(yàn)證該模型的正確性。

(2)由于ebCAP具有NP-hard屬性，本文提出一種基于Pareto占優(yōu)的MISS算法，采用雙層編碼方式構(gòu)造可行解，據(jù)此設(shè)計(jì)雙層交叉和變異算子，并引入擁擠距離機(jī)制保證非劣解的均勻分布；為提高算法搜索效率，本文采用自適應(yīng)模擬退火雙向改進(jìn)機(jī)制優(yōu)化參考集，并設(shè)置閾值減少多余迭代次數(shù)。

(3)采用MISS算法對(duì)40個(gè)不同規(guī)模(5～49)的ebCAP算例進(jìn)行求解，并與精確算法求解結(jié)果對(duì)比，結(jié)果表明針對(duì)問(wèn)題規(guī)模小于9的算例，MISS算法所得結(jié)果與精確解相同，證明了所提算法的有效性。另外，采用MISS算法求解bCAP問(wèn)題，并與pGA算法和混合pGA算法對(duì)比，證明了所提算法在求解質(zhì)量和求解效率上均更具優(yōu)勢(shì)。

(4)以不同規(guī)模的8個(gè)算例為對(duì)象，重復(fù)運(yùn)算10次，計(jì)算每次趨近度指標(biāo)和間距指標(biāo)，數(shù)據(jù)結(jié)果表明MISS算法具有良好的收斂性，所得Pareto非劣解集具有更好的分散性。

未來(lái)研究將進(jìn)一步考慮相鄰設(shè)施間工作區(qū)域的干擾對(duì)布局方案的影響，使其更加貼合實(shí)際情況。另外，還可以考慮由于產(chǎn)品迭代或周期性生產(chǎn)訂單導(dǎo)致的物流動(dòng)態(tài)變化對(duì)具體布局結(jié)果的影響，以權(quán)衡車(chē)間內(nèi)的物流成本和設(shè)備重排成本。