三空間分割遺傳算法的環(huán)氧乙烷滅菌裝載問題

張美洲， 周敏， 黃靜文， 陳燕軍

(1.武漢科技大學冶金裝備及其控制教育部重點實驗室, 武漢 430081； 2.武漢科技大學精密制造研究院, 武漢 430081； 3.武漢科技大學機械傳動與制造工程湖北省重點實驗室, 武漢 430081)

環(huán)氧乙烷(ethylene oxide, EO)滅菌作為醫(yī)療器械(口罩、紗布片、手術(shù)衣等)終末滅菌的主要選擇，是保證產(chǎn)品達到無菌條件[1]的關(guān)鍵工序。隨著新型冠狀病毒肺炎疫情的爆發(fā)，無菌醫(yī)療器械的供應一度嚴重短缺，EO滅菌再度引起了中外眾多學者的關(guān)注。何樂春等[2]和Weiss 等[3]用實驗的方法對滅菌參數(shù)進行了優(yōu)化研究，提出可以通過縮短滅菌周期來提高企業(yè)的滅菌產(chǎn)能，但是存在滅菌參數(shù)驗證周期時間較長的缺點。雖然輻照滅菌被認為是一種高效的滅菌方式[4]，但是眾多研究表明輻照滅菌不適用于醫(yī)療口罩產(chǎn)品的滅菌生產(chǎn)[5-6]。作為一種綠色的滅菌方式，超臨界二氧化碳滅菌技術(shù)目前還處于實驗室階段，暫沒有工業(yè)生產(chǎn)的案例[7-8]。

工業(yè)EO滅菌需要在防泄漏、防爆炸的密閉鋼制滅菌柜[9]中進行，以便能對產(chǎn)品進行批量滅菌，從而提高滅菌效率，降低單次滅菌成本，因此提高滅菌柜的容積利用率是消除滅菌工序瓶頸的主要方法之一。待滅菌產(chǎn)品裝載到滅菌柜的過程，就是一個三維裝箱的多項式復雜非確定性完全問題(non-deterministic polynomial hard，NP-hard)。自從Johnson[10]在20世紀60年代率先提出一種近優(yōu)的裝箱算法后，該領域已從一維裝箱問題發(fā)展到了三維裝箱問題的研究。尚正陽等[11]提出了一種概率較優(yōu)空間分割和底面積匹配放置規(guī)則的快速求解三維裝箱問題的優(yōu)化算法。于明正等[12]和張鈞等[13]都使用了空間分割和遺傳算法相結(jié)合的方式，來解決三維裝箱問題。由于裝箱問題有著眾多的實際應用背景，Erbayrak 等[14]考慮了平衡性和產(chǎn)品族對于三維裝箱的影響；張長勇等[15]和Paquay 等[16]分別用改進遺傳算法和兩階段啟發(fā)式算法對航空領域的裝箱問題進行了研究；Saraiva等[17]采用分層算法研究了三維裝箱問題在汽車公司的應用。

綜上所述，目前對于產(chǎn)品EO滅菌效率提升主要集中在參數(shù)優(yōu)化和方法替代上，對于滅菌裝載問題的研究中外均沒有相關(guān)文獻?；诖耍F(xiàn)采用三空間分割的遺傳算法來解決產(chǎn)品EO滅菌裝載效率低的問題。為保證有交期要求的產(chǎn)品能夠優(yōu)先進行裝載，引入三段式基因編碼。同時運用懲罰函數(shù)弛批次約束，消除了不符合批次要求的裝載組合對結(jié)果的影響。雙精英保留策略也可以確保有交期要求的產(chǎn)品占比和滅菌柜容積利用率兩種裝載組合形式都可以得到最優(yōu)值，以便于對實際生產(chǎn)進行指導。與實際生產(chǎn)中的經(jīng)驗裝載方案對比，本算法的裝載方案在裝載時間和滅菌柜容積利用率上都有很大的提升。

1 EO滅菌裝載問題的數(shù)學模型

1.1 問題描述及約束條件

EO滅菌裝載問題定義為：給定一個容積長、寬、高為L、W、H的滅菌柜和i種長寬高為li、wi、hi數(shù)量為Mi的產(chǎn)品，在考慮產(chǎn)品交期要求和批次要求約束的同時，確定合理的產(chǎn)品EO滅菌裝載方案，最大化地利用滅菌柜的容積。

生產(chǎn)訂單都有交期的要求，希望有延期風險的產(chǎn)品能夠盡量多的優(yōu)先生產(chǎn)。因醫(yī)療器械需要滿足追溯的要求[18]，故根據(jù)產(chǎn)品類別和投放市場的不同，特定產(chǎn)品需要在同一批次生產(chǎn)。本文研究主要考慮如下兩種實際約束：①交期要求約束，即有交期要求的產(chǎn)品優(yōu)先安排滅菌；②批次要求約束，即有批次要求的產(chǎn)品需要同時進行滅菌，或者都不在滅菌組合中。

1.2 模型假設

結(jié)合EO滅菌生產(chǎn)實際情況并參照文獻[11-13]，EO滅菌裝載問題需要做如下假設：①滅菌柜內(nèi)部形狀為長方體；②滅菌柜內(nèi)產(chǎn)品的放置位置沒有區(qū)域限制；③待裝載產(chǎn)品均為長方體且質(zhì)量分布均勻；④產(chǎn)品沒有放置方向約束，可以隨意轉(zhuǎn)動，且沒有碼放層數(shù)限制；⑤產(chǎn)品底部完全支撐，不能出現(xiàn)懸空；⑥有批次要求的產(chǎn)品總量占比在20%以內(nèi)，主要為整批生產(chǎn)后的尾單產(chǎn)品。

1.3 模型建立

基于以上分析，現(xiàn)將EO滅菌裝載問題的數(shù)學模型建立如下。

(1)目標函數(shù)為滅菌柜容積利用率最大：

(1)

式(1)中：F為滅菌柜容積利用率；待滅菌產(chǎn)品序號i=1,2,…,n；vi為第i件產(chǎn)品的體積；V為滅菌柜的容積。

(2)產(chǎn)品總體積約束：

(2)

(3)產(chǎn)品裝載三維尺寸約束：

(3)

式(3)中：xi、yi、zi為待滅菌產(chǎn)品i的三維空間坐標；li、wi、hi為長、寬、高；L、W、H為滅菌柜內(nèi)部尺寸。

2 模型求解算法

遺傳算法(genetic algorithm，GA)，又稱為進化算法，因其具有良好的隱形并行性和全局搜索能力，而被廣泛應用于求解NP-hard問題。三空間分割算法的核心思想是將產(chǎn)品按照規(guī)則放入選定的空間中，并對放入后的空間按照上、右、前的方式進行分割，形成3個新的獨立子空間。本文模型求解算法由三個步驟組成：①通過遺傳算法來形成待滅菌產(chǎn)品的初始裝載方案，為后續(xù)的算法準備初始解集；②采用三空間分割算法對初始解集進行解碼求值；③通過適應度函數(shù)找到最優(yōu)的產(chǎn)品裝載方案。三空間分割的遺傳算法流程如圖1所示，虛線框內(nèi)為三空間分割算法。

圖1 三空間分割的遺傳算法流程圖Fig.1 Flow chart of genetic algorithm with three-space segmentation

2.1 三段式基因編碼

針對EO滅菌裝載問題的交期約束，采用三段式基因編碼方式，即編碼由有交期要求產(chǎn)品裝載順序、沒有交期要求產(chǎn)品裝載順序和產(chǎn)品放置方式三段組成，確保有交期要求產(chǎn)品優(yōu)先裝載。

(1)產(chǎn)品裝載順序編碼。設總的產(chǎn)品數(shù)量為n，對產(chǎn)品按照有交期要求和沒有交期要求進行排序，假設1～m為有交期要求的產(chǎn)品，m+1～n為沒有交期要求的產(chǎn)品。采用自然數(shù)對產(chǎn)品進行編碼，然后生成兩段基因：G1={P1,P2,…,Pm}，G2={Pm+1,Pm+2,…,Pn}。

(2)產(chǎn)品放置方式編碼。因本文研究中對產(chǎn)品的旋轉(zhuǎn)方向沒有要求，故每種產(chǎn)品都有6種擺放方式，編碼值用自然數(shù)1～6表示。產(chǎn)品放置方式的基因編碼可以表示為：G3={Pn+1,Pn+2,…,P2n}。

完整的三段式基因編碼表示為：G={P1,P2,…,Pm,Pm+1,Pm+2,…,Pn,Pn+1,Pn+2,…,P2n}。

2.2 定序規(guī)則

定序規(guī)則是指將產(chǎn)品裝入滅菌柜的先后順序的規(guī)則，產(chǎn)品裝載順序?qū)缇袢莘e利用率有直接影響。為了降低特定的定序規(guī)則對布局質(zhì)量的影響，采用遺傳算法的三段式基因編碼作為產(chǎn)品的定序規(guī)則，即由G1和G2基因段對應的編碼順序來確定產(chǎn)品放入的順序?？梢杂萌缦聜未a來描述定序規(guī)則，如算法1所示。

算法1三空間分割的定序規(guī)則

G1+G2→N#由G1和G2的編碼生成產(chǎn)品序列N

fori=1∶N#通過循環(huán)依次取得產(chǎn)品i

ifi≤N#如果序列中有產(chǎn)品

geti; #得到第i個產(chǎn)品

else

break;

end if

end for

2.3 子空間搜索規(guī)則

選定待裝載的產(chǎn)品后，需要進行子空間的搜索，以確定是否有滿足尺寸要求的子空間，來裝載該選定的產(chǎn)品。當子空間的尺寸和產(chǎn)品的尺寸滿足式(4)時，則此子空間可以作為該產(chǎn)品的裝載空間。

(4)

式(4)中：xb、yb、zb為子空間的長、寬、高；li、wi、hi為產(chǎn)品i的長、寬、高。為了提高滅菌柜容積利用率，采用最小體積策略確定裝載產(chǎn)品的子空間，即在所有的可裝載子空間中，選取體積最小的子空間來裝載選定的產(chǎn)品。其子空間搜索規(guī)則的偽代碼如算法2所示。

算法2三空間分割的子空間搜索規(guī)則

SpaceList→M#子空間的列表為M

ascend by volume ofM#對子空間按照體積升序排列

forj=1∶M#通過循環(huán)依次取得子空間j

ifi≤j#判斷產(chǎn)品i和空間j是否滿足式(4)

getj; #如果滿足式(4)，則選取對應的子空間

else

j+1; #如果不滿足式(4)，則選取下一個空間

end if

end for

ifj=NULL #如果所有子空間都不滿足式(4)

i+1; #跳轉(zhuǎn)到算法1，選取下一個產(chǎn)品

else

break;

end if

2.4 定位規(guī)則

定位規(guī)則是指產(chǎn)品在空間中的放置方式，主要包含兩個方面，一是產(chǎn)品的旋轉(zhuǎn)方向，這個由三段式基因編碼的G3基因段確定三維坐標和產(chǎn)品長(l)、寬(w)、高(h)的對應關(guān)系，即產(chǎn)品的旋轉(zhuǎn)方向，產(chǎn)品放置方式解碼表如表1所示；二是產(chǎn)品在選定的子空間中的放置位置，本文研究采用占角策略，即將產(chǎn)品放置在選定的子空間的左后下角。點(a,b,c)和(e,f,g)為空間的左后下角，產(chǎn)品定位規(guī)則如圖2所示。

2.5 三空間分割規(guī)則

當滅菌柜中裝入一個產(chǎn)品后，滅菌柜中的空間結(jié)構(gòu)發(fā)生了變化，被占用空間除去產(chǎn)品所占用的體積外，剩余部分被分割為上、右、前三個新的子空間，并產(chǎn)生如圖3(a)和圖3(b)兩種三空間分割規(guī)則，如圖3所示。

表1 產(chǎn)品放置方式解碼表

圖2 產(chǎn)品定位規(guī)則圖Fig.2 The map of product positioning rule

圖3 三空間分割規(guī)則Fig.3 Three-space segmentation rule

三空間分割規(guī)則應該避免細小空間的產(chǎn)生，因為細小空間會降低后續(xù)產(chǎn)品放入的概率，從而降低滅菌柜容積利用率。原空間被分割完成后，需要從空間列表中刪除，并剔除分割后的零體積子空間，最后將剩余新生成的子空間加入空間列表中。本文研究的三空間分割規(guī)則的偽代碼如算法3所示。

算法3三空間分割規(guī)則

SelectedSpace→V0#選定的空間V0

#將空間V0按照圖3(a)規(guī)則分割形成前(Vaf)、右(Var)、上(Vat)三個子空間

V0segment according to
Fig.3(a) →Vaf、Var、Vat

#將空間V0按照圖3(b)規(guī)則分割形成前(Vbf)、右(Vbr)、上(Vbt)三個子空間

V0segment according to
Fig.3(b) →Vbf、Vbr、Vbt

ifVaf>Vbr

V0segment according to
Fig.3(b); #采用圖3(b)規(guī)則分割

exclude {Vbf、Vbr、Vbt}=0; #剔除體積等于零的空間

#將剔除零體積后的子空間加入到空間列表SpaceList中

then add {Vbf、Vbr、Vbt} →SpaceList;

else

V0segment according to
Fig.3(a);#采用圖3(a)規(guī)則分割

exclude {Vaf、Var、Vat}=0;

then add {Vaf、Var、Vat} → SpaceList;

end if

deleteV0; #刪除原空間V0

update SpaceList; #更新空間列表

將一件長寬高為a、b、c的產(chǎn)品按照如圖3(a)所示的方法裝入滅菌柜后，其分割后新生成的三個子空間如下。

前空間Vf的空間編碼f及尺寸為

(5)

右空間Vr的空間編碼r及尺寸為

(6)

上空間Vt的空間編碼t及尺寸為

(7)

2.6 子空間合并規(guī)則

將滅菌柜中的細小子空間合并為更大的子空間，不僅可以降低細小子空間不能容納其他產(chǎn)品的情況，而且可以提高滅菌柜容積利用率和空間的搜索效率。其中圖4是子空間的前后合并，圖5是子空間的左右合并。子空間合并規(guī)則的偽代碼如算法4所示。

算法4三空間分割的子空間合并規(guī)則

#用坐標和三維尺寸表示子空間Space1和Space2，其中(a,b,c)為子空間的坐標，(xb,yb,zb)為子空間的長寬高

Space1 {a1,b1,c1,xb1,yb1,zb1}, Space2 {a2,b2,c2,xb2,yb2,zb2}

if (a1>a2 anda1=a2+xb2) or (a1

merge according to
Fig.4 → Space3 {min(a1,a2),b1,c2,

xb1+xb2,yb1,zb1}; #按照圖4合并為空間Space3

delete Space1 and Space2; #刪除子空間Space1和Space2

#將合并后空間添加到空間列表，并更新列表

then add Space3 → SpaceList and update SpaceList;

else if (b1>b2 andb1=b2+yb2) or (b1

merge according to
Fig.5 → Space4 {a1,min(b1,b2),c1,xb1,yb1+yb2,zb1}; #按照圖5合并為空間Space4

delete Space1 andSpace2;

then add Space4 → SpaceList and update SpaceList;

else

break；

end if

圖4 子空間的前后合并Fig.4 Forward and backward merging of subspaces

圖5 子空間的左右合并Fig.5 Left and right merging of subspaces

2.7 懲罰函數(shù)和適應度函數(shù)

在EO滅菌生產(chǎn)中，滅菌參數(shù)和EO氣體的加入量是固定的[19]，故單次滅菌的產(chǎn)品總體積越大，則效率越高，經(jīng)濟效益越好。采用目標函數(shù)，即滅菌柜容積利用率作為適應度函數(shù)，故適應度越大，則子代的適應性越好。同時引入懲罰函數(shù)來松弛批次要求約束，當具有批次要求的產(chǎn)品沒有同時進行滅菌生產(chǎn)時，則直接剔除對應的滅菌裝載方案。

(1)懲罰函數(shù)。設產(chǎn)品的種類為k，Rk=1表示產(chǎn)品k具有批次要求約束，Rk=0表示產(chǎn)品k沒有批次要求約束，SNk表示已經(jīng)裝載到滅菌柜中的第k種產(chǎn)品的數(shù)量，Mk為產(chǎn)品k的總數(shù)量。懲罰函數(shù)為

(8)

只有當產(chǎn)品k具有批次要求約束Rk=1，在滅菌柜中的裝載數(shù)量SNk≠0，且裝載數(shù)量SNk≠Mk時，懲罰函數(shù)α=0，其他情況下懲罰函數(shù)α=1。

(2)適應度函數(shù)。滅菌柜容積利用率越大，則適應度越大，子代基因的適應性越好。但對于不符合批次要求約束的子代基因，可以通過懲罰函數(shù)α=0，將適應度β設置為0，這樣在后期遺傳迭代中該基因會被淘汰。F為滅菌柜容積利用率。

β=αF

(9)

2.8 雙精英保留和輪盤賭選擇算子

選擇算子是指挑選裝載方案的策略，即根據(jù)適應度函數(shù)從父代裝載方案中選擇符合要求的裝載方案。根據(jù)本文問題采用雙精英保留策略，對滅菌柜容積利用率和有交期要求產(chǎn)品占比兩個參數(shù)分別進行精英個體(elite)保留，作為下一代個體基因。然后刪除精英個體，再執(zhí)行多次輪盤賭補足基因種群要求的數(shù)量。

(1)個體方案被選中的概率為

(10)

式(10)中：Pi為個體i被選中的概率；N為篩選后剩余種群總數(shù)。

(2)個體方案被選中的累計概率為

(11)

式(11)中：Qi為個體i被選中的累計概率，即裝載方案在[0-1]區(qū)間上分段，然后通過多次輪盤賭，選擇相應的基因，淘汰未被選中的基因個體。

2.9 順序交叉算子

遺傳算法的基因交叉方式有很多，因順序交叉不僅可以維持原基因段的部分結(jié)構(gòu)，且可以產(chǎn)生較好的子代基因，故以此方式作為交叉算子。根據(jù)三段式基因編碼，產(chǎn)品裝載順序在其各自基因段內(nèi)進行順序交叉，再根據(jù)裝載順序部分交叉點的位置，產(chǎn)品放置方式部分的編碼值在其對應的位置上進行交換。

設編碼字符串長度為2n，通過交叉概率函數(shù)判斷基因交叉是否發(fā)生，若是，則分別以[1,m]和[m+1,n]為取值范圍生成兩對整數(shù)作為交叉點，再根據(jù)順序交叉的方式，來交叉前兩段的基因值；根據(jù)裝載順序部分交叉點位置，放置方式的基因值在與其對應的位置上進行交換。順序交叉示意圖如圖6所示。

F-G1和F-G2表示父代基因；C-G1和 C-G2表示生成的兩個子代基因圖6 順序交叉示意圖Fig.6 The diagram of sequential crossover

2.10 變異算子

變異是保證裝載方案多樣化的關(guān)鍵過程之一。在本問題求解中，產(chǎn)品的放置方式是影響裝載效率的重要因素之一，本文研究中的變異算子主要是對放置方式基因段的編碼進行變異。根據(jù)產(chǎn)品擺放方向約束的限制，放置方式在相應的取值范圍內(nèi)進行隨機變異，基因變異示意圖如圖7所示。

FG表示父代基因；CG表示變異后的子代基因圖7 基因變異示意圖Fig.7 The diagram of gene variation

3 實驗案例與分析

針對實際約束的三維裝載問題，現(xiàn)在沒有統(tǒng)一的國際標準數(shù)據(jù)進行對比，約束的類型和產(chǎn)品種類的多少，都對裝載效果有較大的影響。本文研究的EO滅菌裝載問題采用MATLAB編程語言，算法代碼在MATLAB R2015b上運行，計算機配置數(shù)據(jù)為：Intel?Core i7-1065G7 CPU 1.30 GHz，內(nèi)存8 GB，操作系統(tǒng)為Windows 7專業(yè)版。

3.1 實驗案例設計

綜合本文討論的實際約束，需要確定待滅菌產(chǎn)品是否有交期要求和批次要求，并將此參數(shù)作為算法的約束條件。其中，有交期要求的產(chǎn)品代碼為Rd=1，沒有的為Rd=0；有批次要求的產(chǎn)品代碼為Rb=1，沒有要求的為Rb=0。為了便于觀察仿真的裝載效果，采用紅綠藍(red green blue， RGB)色彩模式對不同產(chǎn)品進行顏色區(qū)分。待滅菌產(chǎn)品主要參數(shù)如表2所示。

遺傳算法的初始參數(shù)設置為：迭代次數(shù)iteration=200，種群規(guī)模population=100，交叉概率cross=0.9，變異概率設置兩個階段，前100代variation=0.5，以便于增加子代的多樣性，后100代variation=0.1，以便于加快結(jié)果的收斂，滅菌柜容積利用率和有交期要求的產(chǎn)品體積占比各保留精英個體比率elite=5%。滅菌柜采用優(yōu)尼克公司生產(chǎn)的20 m3EO滅菌柜，其內(nèi)部有效空間為：L×W×H=900 cm×125 cm×165 cm。

表2 待滅菌產(chǎn)品主要參數(shù)

3.2 實驗結(jié)果與分析

由算法結(jié)果可知，全局最優(yōu)解在迭代到第180代時，基本趨于穩(wěn)定，遺傳算法迭代圖如圖8所示。針對需要求解的滅菌柜容積利用率最大的問題，在交期要求和批次要求的約束下，其對應有4種滅菌裝載方案，如圖9產(chǎn)品裝載圖所示。并根據(jù)方案選擇策略，確定在不同的約束條件下，最終的滅菌裝載方案，滅菌裝載方案及方案選擇如表3所示。其中，A表示有交期要求的產(chǎn)品體積占比，即已裝入滅菌柜的有交期要求產(chǎn)品體積之和與待滅菌產(chǎn)品中有交期要求產(chǎn)品的總體積的比值。B表示滅菌柜容積利用率，即已裝載的產(chǎn)品總體積與滅菌柜容積的比值。

圖8 遺傳算法迭代圖Fig.8 The iteration graph of genetic algorithm

表3 滅菌裝載方案及方案選擇

圖9 產(chǎn)品裝載圖Fig.9 Product loading diagram

由表3可知，當Rb=1時，在Rd=1的情況下選擇裝載方案R1-1，在Rd=0的情況下選擇裝載方案R1-2；當Rb=0時，在Rd=1的情況下選擇裝載方案R1-1，在Rd=0的情況下選擇裝載方案R2-2。

為驗證本文算法的有效性和優(yōu)越性，調(diào)研了中國某醫(yī)療企業(yè)滅菌車間25次滅菌裝載的平均時間和滅菌柜容積平均利用率，并與本次仿真結(jié)果進行對比，遺傳算法和經(jīng)驗裝載結(jié)果對比如表4所示。

表4 遺傳算法和經(jīng)驗裝載結(jié)果對比

由表4對比數(shù)據(jù)可知，采用三空間分割的遺傳算法在裝載時間和滅菌柜容積利用率上，都要優(yōu)于現(xiàn)在的經(jīng)驗裝載方案。經(jīng)驗裝載不僅需要大量的時間進行合適產(chǎn)品的篩選和放置方法的反復調(diào)整，而且會因為裝載方案不當而導致產(chǎn)品延期風險加大和批次管理失效等情況。采用三空間分割的遺傳算法的裝載方案，在給定的條件下，通過對滅菌柜容積利用率不斷的迭代尋優(yōu)，則可避免這些問題。并根據(jù)實際生產(chǎn)需求，結(jié)合不同的約束條件，選擇對應的裝載方案，相比經(jīng)驗裝載滅菌柜容積利用率提高了12.1%～15.9%。

4 結(jié)論

(1)在有交期要求和批次要求兩個實際約束條件下，提出了一種適用于EO滅菌裝載問題的三空間分割遺傳算法，通過三段式基因編碼優(yōu)化產(chǎn)品的放置順序和定位規(guī)則，來最大化的實現(xiàn)滅菌柜容積利用率。

(2)算法中引入了雙精英保留策略，確保在不同的約束條件下，都可以得到相應的滅菌柜容積利用率最大的裝載方案，更加適用于滅菌生產(chǎn)的實際需求。并通過與實際中的經(jīng)驗裝載方案對比，本文算法的裝載方案在裝載時間和滅菌柜容積利用率上都有較大的優(yōu)勢。

(3)通過MATLAB實現(xiàn)了不同約束條件下的裝載方案的可視化，可以更好地指導實際滅菌生產(chǎn)中產(chǎn)品的裝載，提高了三空間分割遺傳算法的工程性。