車間多行布局精準建模與多目標優化研究

徐修立，沈夢超，陳浩杰，張 劍

（西南交通大學 先進設計與制造技術研究所，成都 610031）

0 引言

隨著市場競爭的日趨激烈化，要求企業對生產車間進行精準或者重構布局，以適應市場的快速變化，因此車間布局及優化問題成為了制造領域重要研究課題之一[1]。據統計，一個企業車間的物料搬運費用約為制造總成本的20%～50%，而優化車間布局能減少搬運量、搬運距離和等待時間，使物流成本至少降低10%～30%[2]。

車間布局問題是指將機床設備及其輔助設施在給定的空間內進行布局，并且滿足相應的約束條件，通過優化以獲取最佳目標函數值[3]。目前，在車間布局問題中建立的數學模型主要包括二次分配模型、混合整數規劃模型、二次集合覆蓋模型、線性多行直線布局模型等[4]。在車間布局模型求解方面，已廣泛采用啟發式優化算法[5]。如郭源源[6]將粒子群算法與經典的系統布置設計法相結合來求解面向車間布局的連續空間優化問題，Kulturel-Konak[7]提出了一種混合粒子群算法來求解不等面積的車間布局問題，Pourhassan[8]提出了采用非支配排序遺傳算法（NSGA-II）求解多目標動態設施布局優化問題。由于遺傳算法操作簡單、且具備魯棒性，文獻[9～11]等均采用遺傳算法或其改進來對車間布局問題進行優化求解。

建立車間布局數學模型是一個化繁為簡的過程，但過于簡化往往導致數學模型與實際物理模型之間存在較大的差異。例如布局時不等面積功能區橫縱向放置問題、豎向主干道、行距可變等實際情況被忽略，同時優化的目標通常是物料搬運成本最小化的單目標，而忽略了車間的面積利用率等因素的影響。因此本文基于當前車間布局中較為常用的線性多行直線布局模型，充分考慮車間各種實際約束，建立更為精準的車間總體布局多目標優化數學模型，同時采用求解更為有效的多種群遺傳算法，實現精準布局模型的求解，并將該方法應用于實例中說明其可行性與優越性。

1 車間總體布局精準數學模型的建立

采用多層次式布局策略[12]，對已經劃分布置好的N個不等面積功能區進行車間總體布局，可以減少計算規模。根據車間現場的多重約束和規則，建立精準數學模型，構建多目標優化函數并求解，實現車間中總的物料搬運成本最低、車間面積利用率最大等目標，以便得到最優車間布局解。

1.1 模型假設與符號說明

本文采用線性多行直線布局模型對車間進行總體布局?？紤]實際廠房的空間約束，而功能區單元布置行數未知，故采用自動換行策略。為便于建模和提高計算效率，對多行直線布局做出如下假設：1）待布局的車間為二維平面，且是長寬大小已知的矩形；2）待布置的功能區均為長、寬已知的矩形，忽略其高度；3）各功能區分行排列，且平行于車間長寬方向，即平行于x軸和y軸；4）排列在同一行的功能區其中心點在同一條水平線上。

車間與功能區的幾何模型如圖1所示。

圖1 線性多行設備功能區布局示意圖

其中L、W分別表示待布局車間的長度和寬度，Ai表示功能區單元i，xi表示i功能區的x軸方向坐標，yi表示i功能區的y軸方向坐標，li表示i功能區的長度，bi表示i功能區的寬度，hik表示i功能區和k功能區之間的橫向最小安全距離，Δi表示i功能區和k功能區之間的凈間距，s0表示第一行功能區與車間邊界設定的距離，Sm,m-1表示兩相鄰行之間的行距，hj0表示j功能區與車間邊界的最小安全距離，yn表示n功能區所在行的y軸方向坐標位置值大小。

1.2 優化目標

本文以車間總物料搬運成本最小和面積利用率最大為優化目標建立多目標精準數學模型，以滿足物流原則和布局緊湊原則。

1）車間中總的物料搬運成本最小化

式中：Pij為功能區i和功能區j之間的單位物料在每單位距離之間進行搬運所需的費用，Qij為功能區i和功能區j之間的物料搬運頻率，m為車間總體布局后的總行數，n為功能區的總數量，Dij為功能區i和功能區j之間的矩形距離，其公式如下：

2）車間面積利用率最大化

面積利用率最大問題可以轉化為布局結果所包絡功能區的矩形面積St最小問題，St的計算公式如式(3)所示：

布局過程采用自動換行策略，其中yend為布置在車間最后一行功能區的縱坐標，B(end)max為最后一行功能區中寬度最大的功能區寬度尺寸。由此該目標函數的表達式為：

根據優化目標之間的相對重要程度，采用加權法構造新的優化目標函數，將多目標優化問題轉換為單目標優化問題進行求解：

式中：ω1、ω2為加權因子，且滿足ω1+ω2=1，α1、α2為歸一化因子。

1.3 精準數學模型約束條件

建立車間布局精準數學模型的約束條件如下：

式中：（Xi'，Yi'）、（Xi''，Yi''）分別為矩形功能區i的左下角和右上角的坐標；LWl、LWr分別表示豎向主干道沿x軸方向的左、右兩邊的坐標大??；決策變量Zik=1表示功能區i在第k行上，否則Zik=0；決策變量UAi=0表示功能區i橫向放置，UAi=1表示功能區i豎向放置；B(k)max為第k行功能區中寬度最大的功能區寬度尺寸；yi(k)表示功能區i的y軸方向坐標（功能區i位于第k行），y(k-1)表示第k-1行的y坐標大小，WP表示設定橫向主干道的尺寸大小，一般不設定橫向主干道則WP=0。

式(6)、式(7)表示功能區的橫縱坐標方向不超過車間最大長度和最大寬度，式(8)保證功能區布局避開豎向主干道，式(9)保證同一行的功能區不能重疊且滿足其安全距離，式(10)保證一個功能區在布局中只能出現一次，式(11)表示功能區可橫向、豎向選擇放置，式(12)表示設置自適應行距：即布置有功能區的任意相鄰兩行k行、k-1行的行距可根據所布置的功能區尺寸大小自適應確定行距大小，而非采用固定行距約束要求：根據所有功能區中最寬功能區的寬度設置每相鄰兩行行距為定值大小[13]，式(13)、式(14)分別表示功能區矩心的橫（x軸）、縱（y軸）坐標求解公式。

2 改進多種群遺傳算法求解

遺傳算法是模擬生物進化過程搜索最優解的方法，具備很強的全局搜索能力和魯棒性，但是也存在早熟收斂和收斂性能差等缺陷與不足[14]。為此，本文采用一種改進多種群遺傳算法（MPGA）對車間總體布局問題進行優化求解，該算法通過模擬自然生態系統協同進化，具有全局、局部搜索能力強和收斂精度高等特點[15]。

2.1 改進多種群遺傳算法流程

多種群遺傳算法流程如圖2所示，具體操作過程如下：

Step1：隨機產生N個初始種群，每個種群的規模大小為M，初始化種群并計算個體的目標函數值。

Step2：利用2.2節中設計的交叉和變異概率參數控制式(15)、式(16)對每個種群分別設定不同的交叉和變異概率控制參數。

Step3：N個種群各自獨立進行標準遺傳算法（simple genetic algorithm，SGA）的選擇、交叉、變異等操作。

Step4：采用移民算子交換種群間信息。

Step5：利用人工選擇算子選出每個種群的最優個體保存至精華種群中。精華種群不進行選擇、交叉、變異等遺傳操作，保證迭代過程中不破壞和丟失最優個體。

Step6：判斷精華種群中的最優個體最少保持代數是否達到設定的最大保持代數，若是，則尋優過程結束，輸出最優解；否，則繼續循環迭代。

圖2 多種群遺傳算法（MPGA）流程示意圖

2.2 交叉和變異概率參數控制公式設計

遺傳算法中交叉概率和變異概率的參數設置決定了全局和局部搜索能力，若按傳統多種群遺傳算法的操作，對每個種群設定相同的交叉概率Pc和變異概率Pm，會存在交叉、變異概率設置不合理致使多種群遺傳算法陷入早熟收斂的問題。故本文通過設計交叉和變異概率參數控制公式給予每個種群不同的控制參數，則不同種群以不同的交叉和變異概率協同進化，兼顧了算法的全局和局部搜索，降低了算法求解陷入局部最優的可能性，提高了多種群遺傳算法的收斂精度。結合交叉概率取值范圍（pcmin，pcmax）和變異概率取值范圍（pmmin，pmmax），設計交叉和變異概率參數控制公式：

其中，randN（0，1）為在0～1區間產生的隨機數，有N個種群則分別產生N個0～1之間的隨機數值。

2.3 多種群遺傳算法設計

2.2.1 基因的編碼

基因編碼方式由功能區排列順序、凈間距和功能區單元橫豎放置選擇三部分構成，采用混合的編碼結構，表達方式為：[{A1，A2，…，An}{Δ1，Δ2，…，Δn}{0，1，0，0，1，...}]。其中：功能區排序時采用整數編碼，Ai為功能區，其順序為功能區i的排列順序；凈間距采用實數編碼，Δi為功能區i和功能區i-1或邊界之間的凈間距；功能區單元橫豎放置選擇采用二進制編碼，1表示功能區單元豎向放置，0表示功能區單元橫向放置。

2.3.2 種群評價函數

根據1.3節中式(13)、式(14)求出該染色體序列每個功能區的x、y坐標；根據1.2節中式(5)求出加權后的多目標優化函數值C，由于所求目標為極小值，故而適應度函數設為：

其中：f為適應值；T為罰函數，使得不滿足約束條件的較差個體具有較低適應度值。

2.3.3 遺傳算子

選擇操作采用輪盤賭的方式，各種群采用文獻[16]中標準遺傳算法（simple genetic algorithm，SGA）的交叉、變異操作。

2.3.4 算法終止條件

與標準遺傳算法（SGA）中人為設定最大終止迭代次數不同，本文算法通過判斷當精華種群中的最優個體連續保持代數達到設定的保持代數時，則算法終止，輸出最優解。避免因設定迭代次數不合理而導致算法在收斂前過早結束或收斂后浪費計算資源的情況。

2.4 移民算子

由于各種群是相對獨立的，故本文通過引入移民算子將其聯系起來。移民算子是將迭代過程中各種群里的最優個體定期的交換至其他種群，從而實現種群間的信息交換，交換的染色體作為外來優秀個體引入，避免了迭代進化后期因種群多樣性降低致使算法陷入局部最優。移民算子具體操作為：將目標種群中的最差個體用其他種群中的最優個體替換，即將N個種群編號（1，2，…，r，…，N），種群r中的最差個體由種群r+1中的最優個體代替，以此類推，種群1中的最差個體由種群N中的最優個體代替，完成移民操作。

2.5 參數設置

本文分別采用SGA算法和MPGA算法對目標函數進行求解，取加權因子ω1=0.6，ω2=0.4。SGA算法：M=50，Pc=0.8，Pm=0.08，設定終止判據：最大迭代次數為200代；MPGA算法：N=10，M=50，設定Pc取值范圍（0.6,0.9）和Pm取值范圍（0.01,0.1），設定終止判據：最優個體最少保持代數為5代。

3 實例驗證及分析

某制造企業準備建新廠房，長90米，寬60米，考慮在廠房長度方向中間位置處設置一條4米寬的豎向主干道。企業確定了未來五年生產所需設備的類型及數量，同時基于成組技術，對設備進行了功能區單元的構建，功能區劃分構建結果如表1所示。根據零件加工工藝和功能區構建結果，分析物流情況可獲取從至表，同時設置安全距離。

表1 功能區信息表

采用上文的相關參數設置，設計了如表2中的6組實驗；并且根據不同實驗方案，運用Matlab軟件編寫了相應程序。每種實驗方案均運行10次，取其中最優解及目標函數的平均值作為數據結果如表3所示；為了比較算法性能，實驗1與實驗2同時迭代到200代的進化結果對比如圖4所示。

表2 實驗方案表

表3 優化數據結果對比表

圖3 MPGA與SGA進化迭代結果對比圖

結果分析：對比表3中實驗1和實驗2的數據結果，采用多種群遺傳算法（MPGA）比采用標準遺傳算法（SGA）求解的目標函數值小5%，同時從圖3中MPGA與SGA進化迭代結果對比可見，SGA在進化到100代左右即陷入了局部最優解，采用MPGA算法求解的精度明顯比SGA求解精度更高。

對比實驗2和實驗5的優化數據結果，采用自適應行距得出的布局結果會比采用固定行距約束結果更優，其總物流成本降低了3%，面積利用率提高了6%。

對比實驗2和實驗6的數據結果，考慮功能區橫豎放置的最優解精度可提高3%，更容易得到車間布局最優解。

對比實驗2、實驗3（在實驗2布局結果中強行加入豎向主干道）和實驗4的優化結果說明，在不考慮豎向主干道進行優化時，雖然簡化后的優化模型得到目標函數值是這3個實驗中最小的，但是真正加入豎向主干道后，實際目標值卻增大9%，說明在建立數學模型時應考慮豎向主干道的實際約束，從而更能求得符合實際車間布局的最優解。故本文實例最終采取實驗4方案，最大化地減小了物流成本且提高了面積利用率，求解所得布局結果示意圖如圖4所示。

圖4 車間布局方案示意圖

4 結論

本文改進了多行直線布局模型中行與行之間固定行距的約束，給出自適應行距約束定義，使布局面積更小、物流成本更低。同時針對目前車間總體布局數學模型過于簡化的缺陷，在優化數學模型中加入了功能區單元橫豎選擇放置及豎向通道設置，建立了更為符合車間實際布局情況的精準數學模型。采用改進多種群遺傳算法（MPGA）對該數學模型進行多目標優化求解，通過設計交叉和變異概率參數控制公式，使群體保持多樣性，采用移民算子聯系種群，降低了算法求解陷入局部最優的可能性，提高了多種群遺傳算法的收斂精度，最后通過實例驗證了所建模型的實用性和所用算法的優越性。