基于自適應遺傳模擬退火算法的多目標車間布局優化*

盧義楨 李西興 朱傳軍 吳 銳

（①廣東工業大學管理學院，廣東 廣州 510000；②湖北工業大學現代制造質量工程湖北省重點實驗室，湖北 武漢 430068）

車間設施布局問題是智能制造精益生產中面臨復雜問題之一，其實質是一種非線性組合優化問題，需要尋求合理高效的車間設施布局方案來提高車間空間利用率，降低車間物流成本，提高生產效率。車間設施布局是否合理對整個生產系統的總體性能有著重要的影響。

當前車間布局優化問題主要利用智能優化算法進行求解。國內研究中，謝潔明等[1]提出了基于仿真的遺傳網格自適應直接搜索算法（GMADS）用于求解具有單向導向路徑網絡、多重嵌套封閉環形物料儲運系統的布局優化問題。郭源源等[2]采用粒子群算法求解二維設施布局問題并將粒子群算法與SLP法進行結合，提高了初始解的合理性和尋優過程的高效性。陳勇等[3]為滿足低成本、高穩健性的車間布局要求，設計了以單位面積布置成本、單位產品物流成本和布局熵為優化目標的車間布局優化模型，提出了基于Pareto優化的聚類并行多目標遺傳算法。國外學者對應用智能算法求解布局問題也有諸多研究，Frederico Galaxe Paes等[4]通過引入經分解策略改進后的遺傳算法解決不平等區域設施布局問題（UA-FLP）時，尋優表現優于普通遺傳算法。Jose Fernando Goncalves等[5]針對不平等區域設施布局問題提出了偏向性的隨機關鍵遺傳算法（BRKGA）確定設施布局方案。

在車間設施布局優化研究中，多將車間不同作業單元間搬運距離總和作為優化目標[6?7]，而沒有考慮到實際生產中不同作業單元之間物料搬運方式可能存在差異的情況針對該問題，本文考慮不同作業單元之間物料搬運方式不同的情況，以最小車間物流成本與最短車間搬運時間為優化目標，采用自適應遺傳模擬退火算法對車間設施布局問題進行求解，并通過實例分析驗證了模型和算法的有效性。

1 問題描述

在制造車間中，零件按各自批量和工藝流程依次經過不同的作業單元完成加工過程。在這個過程中，不同的車間設施布局方案會對物料搬運過程的時間、成本等指標產生影響，需要建立數學模型，通過運算求解出一套較優的布局方案以滿足降低生產成本、提高生產效率的要求。

1.1 問題假設

（1）假設各作業單元形狀均為標準矩形，長和寬均已知。

（2）假設各作業單元均為橫平豎直，作業單元的邊界分別平行于車間四周邊界。

（3）假設物料是從一個作業單元的幾何中心搬運到下一個作業單元的幾何中心。

（4）假設物料搬運的路徑平行于車間邊界的直線。

（5）假設不同作業單元之間物料搬運速度不同且均已知。

基于以上假設，建立車間設施布局示意圖如圖1所示。

圖1 車間設施布局

在圖1中，X軸為車間的長度方向；Y軸為作業車間的寬度方向；mi為車間第i個作業單元，i=1,2,···,N（N為車間作業單元總數）；L為作業車間總長度；W為作業車間總寬度；li、wi分別為車間i作業單元的長度、寬度；xi、yi分別為i作業單元幾何中心點的橫坐標、縱坐標；sij為i作業單元與j作業單元邊界之間的凈間距[8]。

1.2 數學模型

本文同時考慮車間物流成本最小與車間搬運時間最短兩個目標進行建模，目標函數表達式如下所示。

式中：G1為第一個優化目標車間物流成本；G2為第二個優化目標車間搬運時間；Pij為i作業單元與j作業單元之間單次物料搬運單位距離的費用；Dij為i作業單元與j作業單元幾何中心點之間的曼哈頓距離；Fij為i作業單元與j作業單元之間物料搬運頻率；Vij為i作業單元與j作業單元之間物料搬運速度。當i=j時，Pij、Fij、Vij=0。

采用歸一化因子u1、u2來統一量綱[9]，u1、u2的計算如式（3）、式（4）所示。考慮到實際生產中對多個優化目標的側重不同，加入加權因子w1、w2，且滿足w1+w2=1(w1、w2∈(0,1))，最終得到目標函數表達式如式（5）所示。

式中：G為加權后的目標函數值；Dmax為兩作業單元間可能存在的最大曼哈頓距離，近似為車間的長和寬之和；v′ij為車間所有路徑上物料搬運速度的平均值。

1.3 約束條件

在對車間不同作業單元的布局進行建模優化時，還需要結合實際情況建立約束條件，主要包括以下內容。

（1）間距約束。不同作業單元之間需要保持一定的距離，即

（2）通道約束。各作業單元之間與車間墻壁之間需要保留一定的距離，即

（3）尺寸約束。同一行或同一列的所有作業單元在在X軸或Y軸方向上的布局不得超過車間的長度或寬度，即

式中：s為 最小間距。

2 自適應遺傳模擬退火算法

為了對上述模型進行求解，提出一種自適應遺傳模擬退火算法，即在傳統遺傳算法上對交叉變異算子采用自適應調整策略；同時利用模擬退火算法的概率突跳性來降低過早收斂的可能性，進一步增強算法求解性能并基于Metropolis準則判斷是否接受新個體。算法流程如圖2所示。

圖2 算法計算流程

2.1 種群初始化

本文采用實數編碼的方式構建個體的基因序列，編碼樣式為[m1,m2,m3,m4,···,mN]，代表的含義是自車間區域自左下角依次沿X軸正方向布置作業單元，當布置的作業單元總長度超出車間長度時，沿Y軸正方向另起一行，從最左端繼續向右依次布置，例如個體編碼[2,7,3,10,1,4,5,···]的布局即圖3所示。

圖3 編碼示例對應的車間布局圖

2.2 適應度函數

本文中綜合優化目標是求最小值，設置適應度函數fi為

式中：G為目標函數；P為懲罰函數。懲罰函數定義為

2.3 選擇算子

為保證種群基因多樣性并且同時提高算法的收斂效率，本文選擇輪盤賭加部分精英保留的策略進行選擇操作。輪盤賭策略中，個體i被選中的概率Pi為

式中：popsize為種群大小；fi為第i個個體的適應度值。

采用輪盤賭的方式選出下一代種群中一半的個體后，采用部分精英保留策略選出另一半的個體，選出的所有個體組合成子代種群。

2.4 交叉算子

由于車間布局問題中個體基因型的代碼具有特殊含義，因此本文采用基于位置的交叉算子，其具體操作如圖4所示。

圖4 交叉過程

2.5 變異操作

在實數編碼下，基因序列上的每一個數字都具有特殊的含義，無法采用二進制編碼下的各種變異方法。針對本問題，為了保證變異之后的個體仍具有意義，采用互換變異的方式進行操作，如圖5所示。

圖5 變異過程

2.6 自適應交叉、變異策略

遺傳算法中，交叉概率Pc和變異概率Pm是影響算法尋優能力的重要參數，由于自適應取值法對交叉、變異算子進行非線性設計，使得交叉概率與變異概率隨種群中個體的適應度值的變化而變化，能夠防止算法陷入過早收斂[10]，因此本文對Pc、Pm的取值采用自適應取值法，取值計算過程如式（15）、式（16）所示。

式中：Pcmax與Pcmin分別為遺傳操作過程中交叉概率取值區間的上、下限，f′為進行交叉操作兩個個體中較大者的適應度值，favg為每代種群的平均適應度值，fmax為當前種群中的最大適應度值，λ為常數。

式中：Pmmax、Pmmin為變異概率取值區間的上、下限，f為變異個體的適應度值，favg為每代種群的平均適應度值，fmax為當前種群中的最大適應度值。

2.7 嵌入模擬退火算法

在遺傳算法中嵌入模擬退火算法，借用模擬退火算法的概率突跳性增強算法全局尋優的能力。設定初始溫度t作為模擬退火尋優的起始點，設定終止溫度Tend作為模擬退火尋優的終止點，在等溫狀態下交換個體前后一半基因并依據Metropolis準則計算新個體被接受的概率，其計算公式如下

式中：Ps為新個體接受的概率；fi(t)為個體變換前的適應度值；fj(t)為個體變化后的適應度值；t為當前溫度。依據式（14）更新當前溫度，即

式中：λ為溫度衰減參數，用于控制退火速度，且取值大小滿足λ∈(0，1)。

3 計算實例

3.1 車間概述

FK公司是一家主要從事汽車零部件設計和制造的公司，該公司生產車間為30 m×25 m的矩形，車間內有11套各式加工機床以及原材料、成品存放區。為方便描述，用序號表示各作業單元，各作業單元的尺寸數據見表1，車間的原始布局如圖6所示。

圖6 車間原始布局

根據產品的工藝流程以及不同作業單元間物料搬運方式的差異，作業單元間的單位費用如表2所示，作業單元間的搬運頻率如表3所示，作業單元間的搬運速度如表4所示。

3.2 優化過程及相關參數設定

設定最小間隔參數s為1 m。由表2、表3、表4的數據，計算出歸一化因子u1=4.905×10?6、u2=5.646×10?5。根據對優化目標的側重不同，設定權重因子w1=0.6，w2=0.4。種群數量設定為50，迭代次數gen為500代，保證算法充分進行尋優搜索。為驗證不同算法的設計以及不同參數的選取對算法尋優的影響，引入4種不同的方案進行對比，具體如表5所示。

表2 作業單元間的單位費用 元/m

表3 作業單元間的搬運頻率 次/天

表4 作業單元間的搬運速度 m/s

表5 算法參數設定對比

3.3 優化結果及分析

在MATLAB軟件上運行各套算法對車間布局問題進行求解，運行結果如圖7所示。從圖7可以看出，各算法在迭代一定代數之后停止了波動，達到收斂。經計算，方案1至方案3求解得到的最優目標函數值分別為0.180、0.175、0.169，本文提出的自適應的遺傳模擬退火算法求解得到的最優目標函數值為0.158，比普通遺傳算法尋優結果更優秀，由本文算法求解得到的最優個體為[5,13,10,1,11,4,3,6,2,8,9,7,12]，其車間作業單元布局如圖8所示，各作業單元的位置坐標如表6所示。

表6 優化后作業單元位置坐標

圖7 算法優化過程迭代圖

圖8 優化后車間作業單元布局

為了評估優化效果，將原布局與優化后的布局下的搬運費用及搬運時間進行對比，如表7所示，對比發現優化效果顯著。

表7 優化前后對比

4 結語

針對車間設施布局優化問題，本文以最低車間物流成本與最短車間搬運時間為優化目標建立數學模型，采用自適應遺傳模擬退火算法對問題進行求解，并通過4種參數設定方案對比驗證了自適應策略的算法的優越性。給出了FK公司的車間設施布局優化案例，結果表明，經遺傳模擬退火算法優化后得到的車間布局方案，相較于原始布局方案，其車間物流成本降低了9.98%，車間搬運時間縮短了20.8%，證明該算法有較強的尋優能力，可以為企業車間生產制造減少浪費，提高效率。

在后續工作中，還需要繼續結合其他算法的思路對算法進行改進，同時車間布局數學模型的復雜度需結合實際情況作進一步的完善。