考慮設(shè)施方向的雙目標過道布置問題建模與優(yōu)化

陳 鳳，張則強+，劉俊琦，王沙沙

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

0 引言

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

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

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

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

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

1.1 問題描述

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

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

1.2 基本假設(shè)條件

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

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

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

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

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

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

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

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

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

續(xù)表1

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

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

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

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

(1)

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

(2)

當ri=1時(1-ri)=0，設(shè)施i以邊L1i靠近過道，因此設(shè)施i的寬度為L1i，深度為L2i。

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

目標函數(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è)施的排列順序和布置方向，進而確定設(shè)施的相對位置和精確位置。式(3)表示兩個目標函數(shù)最小化。式(4)為目標函數(shù)F1，表示總物料搬運成本，其中dij+c(1-qij)為設(shè)施i，j之間的物流交互距離，若兩個設(shè)施布置在同行，則qij=1，設(shè)施間的物流交互距離為dij；若兩設(shè)施異行布置，則qij=0，物流交互距離為dij+c。式(5)表示最小化設(shè)施布局方案的總面積，其取值為能夠包圍布局方案的最小矩形區(qū)域的面積，F(xiàn)2達到最小意味著在該布局方案下，所有設(shè)施所在的矩形區(qū)域中未被利用的空余面積最小，此時平面空間利用率最高，其中布局方案的總占地面積表示為L0H，H為布局寬度，H=max{Di×yiU,Di×yiD}，L0為通道長度，L0=max{wi×yiU,wi×yiD}。

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

2 求解ebCAP的MISS算法

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

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

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

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

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

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

2.1 解序列的編碼和解碼

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

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

如圖4所示，假設(shè)上述可行解中各矩形設(shè)施相鄰兩邊L1i和L2i對應(yīng)的向量為L1=[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è)施4與設(shè)施1的寬度索引值分別為1和0，表示設(shè)施4以邊L14靠近過道邊線，設(shè)施1以邊L21靠近過道邊線，因此設(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è)施坐標、布局寬度和長度，進一步得到可行解的布局面積和物料搬運成本,并根據(jù)兩個目標評價可行解，詳見第1.3節(jié)。

2.2 多目標處理方法

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

(21)

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

(22)

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

(23)

2.3 多樣性評價標準

因為分散搜索算法注重參考集的多樣性和內(nèi)部最優(yōu)性，所以結(jié)合ebCAP的特點對文獻[32]的多樣性產(chǎn)生方法進行改進，提出如式(24)所示的多樣性評價標準構(gòu)建多樣性初始參考集。

D(x1,x2)=

(24)

2.4 交叉算子與變異算子

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

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

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

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

當前個體xo與精英參考集refset1的多樣性程度

(25)

當前個體xo與當前多樣性參考集refset2所含個體的多樣性程度

(26)

2.6 子集的產(chǎn)生

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

Input:精英參考集中的父代個體x1、多樣性參考集中的父代個體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 解的改進

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

2.8 模擬退火雙向改進機制

為及時更新參考集，避免算法陷入局部最優(yōu)，針對精英參考集設(shè)計模擬退火雙向改進機制。針對目標函數(shù)F1，將精英參考集升序排列，排序序數(shù)為奇數(shù)的個體分配到真子集1，序數(shù)為偶數(shù)的個體分配至真子集2，真子集1中的個體以目標F1為優(yōu)先改進對象，目標F2為次優(yōu)化對象，真子集2中的個體以目標F2為優(yōu)先改進對象，目標F1為次優(yōu)化對象。由于所提ebCAP是雙目標優(yōu)化問題，需要對Metropolis準則進行改進，具體為：當優(yōu)先改進對象為目標F1時，若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)隨機產(chǎn)生一個隨機數(shù)P用于決定是否接受新解，若P>rand則接受當前解，否則拒絕新解。同理，當優(yōu)先改進對象為目標F2時，若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)隨機產(chǎn)生一個隨機數(shù)P，若P>rand則接受當前解，否則拒絕新解。概率P的計算公式為：

P=

(27)

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

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

Initialization parameter

x→xbest；

Begin

while T

for l0=1:L0

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

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

Δf1<0 or Δf1=0∩Δf2<0；/優(yōu)先改進對象為目標F1時

(if Δf2<0 or Δf2=0∩Δf1<0；)/優(yōu)先改進對象為目標F2時

x′→x；

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

if P>rand

x′→x；

end if

end if

end for

else

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

end if

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

Break；

end if

T=T·q；

end while

Output:xbest

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

2.9 參考集更新和停止準則

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

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

2.10 算法流程

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

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

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

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

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

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

步驟6采用模擬退火雙向改進機制改進精英參考集refset1,并重置計數(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解集評價指標

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

CM指標表達式為：

(28)

(29)

SM指標表達式為：

(30)

(31)

(32)

3 算法驗證

3.1 ebCAP問題驗證

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

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

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

續(xù)表3

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

3.2 算法評價

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

3.3 中小規(guī)模算例

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

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

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

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

續(xù)表5

3.4 大規(guī)模算例

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

續(xù)表6

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

4 結(jié)束語

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

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

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

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

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

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