高 勃，張紅艷，趙宏軍，孫嘉玉，李云志，朱明皓

(1.北京交通大學(xué) a.計算機與信息技術(shù)學(xué)院，b.經(jīng)濟管理學(xué)院, 北京 100044;2.北京機械工業(yè)自動化研究所有限公司，北京 100120;3.國家工業(yè)信息安全發(fā)展研究中心 系統(tǒng)所，北京 100043)

在智能制造過程中，企業(yè)為提高經(jīng)濟效益，需要最大化地節(jié)約成本，給出企業(yè)合理的訂購原材料的方案，減少材料浪費，提高企業(yè)效益.二維排料廣泛應(yīng)用于汽車制造、造船、鋼鐵切割、服裝設(shè)計剪裁，家具下料[1]等工業(yè)設(shè)計與生產(chǎn)中，屬于典型的NP完全問題.對二維排樣進行優(yōu)化是必要的，以此來提高

板材的利用率.在工業(yè)生產(chǎn)實踐中，有許多因素會影響原材料的利用率，比如操作人員的技術(shù)能力，設(shè)備的切割誤差，排樣方案等，其中排樣方案的好壞對原材料的利用率起著決定性的作用.

目前國內(nèi)外學(xué)者對矩形件優(yōu)化排樣問題做了廣泛的研究，最初的排樣算法往往根據(jù)矩形件信息進行直接排樣，例如文獻[2]提出基于動態(tài)分割和合一的排樣算法.文獻[3]提出貪婪算法進行矩形件的排樣，每次排樣時優(yōu)先選擇面積最大的矩形件，以此來實現(xiàn)板材利用率最高的目標(biāo).雖然算法簡單，但板材的利用率低.而后采用較多的方法是文獻[4-7]所提到的模擬退火算法，遺傳算法，蟻群算法等智能算法.雖然智能算法的應(yīng)用使得板材利用率有所提高，但智能算法計算開銷較大，隨著企業(yè)的生產(chǎn)規(guī)模變得越來越大，排料系統(tǒng)的可行性往往會因為計算時間的劇增而不再具有實用性.近幾年學(xué)者根據(jù)零件特征對板材進行啟發(fā)式填充處理，比如文獻[8]改進了在矩形件排樣中的填充算法.文獻[9]提出矩形件簡單塊占角排樣方式的動態(tài)規(guī)劃.文獻[10]采用基于粗糙集的矩形件優(yōu)化填充排樣方法.文獻[11]提出了啟發(fā)式動態(tài)分解算法，根據(jù)矩形件對板材進行正交動態(tài)分解，計算放置耦合度選擇最佳子板，通過干涉關(guān)系對待排子板狀態(tài)更新.上述研究雖已取得一定的成果，但應(yīng)用不具有普遍性，仍存在一定的問題.

基于以上分析，本文作者深入研究了在二維板材下矩形的問題，以最大化板材利用為目標(biāo)，建立優(yōu)化排樣模型，在此基礎(chǔ)上提出了一種新的排樣算法——啟發(fā)式板材排樣優(yōu)化算法，以最大化板材利用率為目標(biāo)，設(shè)計評價函數(shù)，通過比較評價函數(shù)值進行剪枝優(yōu)化，加快排樣過程中零件的定位及定序，進而縮短時間，給出企業(yè)合理訂購原材料的方案，并通過案例分析驗證了該算法的有效性.

1 二維規(guī)則板材排樣問題與數(shù)學(xué)描述

1.1 問題描述

面對節(jié)約性和可持續(xù)發(fā)展的要求，在智能工業(yè)生產(chǎn)過程中，以減少原材料浪費為目標(biāo)，給出企業(yè)合理的原材料調(diào)度與儲備方案，需要在平面區(qū)域內(nèi)給出零件排列的最優(yōu)布局，最大化利用板材，減少材料的浪費.實際生產(chǎn)中，排料的種類有很多，常見的原材料和零件有矩形、圓形以及不規(guī)則的形狀.針對上述問題，本文主要采用針對二維規(guī)則板材下的矩形優(yōu)化切割排樣算法.

對于規(guī)則板材的矩形件排樣問題具體數(shù)學(xué)表述如下

(1)

在矩形件排樣過程中需要滿足以下約束條件：1)矩形件rj排列在板材區(qū)域內(nèi)；2)不同的矩形件ri和rj(i≠j)排列不能重疊；3)矩形件rj的邊與板材邊平行.

1.2 排樣數(shù)學(xué)模型

基于上述分析，以最大限度地節(jié)省原材料為目標(biāo)函數(shù)，構(gòu)建優(yōu)化目標(biāo)，即

(2)

定理1式(2)中的最小化優(yōu)化函數(shù)等價式(3)給出的最大化優(yōu)化函數(shù)，即

(3)

證明 式(2)的優(yōu)化目標(biāo)等價為

(4)

(5)

于是，定理1證畢.

基于定理1，矩形件排樣過程中需要滿足

(6)

(7)

xi+li≤W

(8)

yi+wi≤H

(9)

xi+li≤xj∪yi+wi≤yj

(10)

xj+lj≤xi∪yj+wj≤yi

(11)

xi,j，yi,j≥0

(12)

i=j=1,2,…,m

(13)

從所構(gòu)建的數(shù)學(xué)模型可知，其變量是離散不連續(xù)的，問題的解也是離散的，因此矩形件排樣問題是約束離散優(yōu)化問題.一方面，由于該問題是非線性的，傳統(tǒng)的解析法無法求解.同時由于排樣問題是NP完全問題，這類問題在理論上存在一種算法可求得最優(yōu)解，但求解時間隨著問題規(guī)模的增長呈指數(shù)關(guān)系增加，在生產(chǎn)實際中過長的求解時間是不可接受的.因此，本文提出一種基于啟發(fā)式的板材排樣優(yōu)化算法，通過剪枝優(yōu)化，在提高板材利用率的同時，縮短時間，提高求解問題的效率.

2 啟發(fā)式板材排樣優(yōu)化算法

2.1 基本思想

針對矩形件排樣，假定每次排樣總是將零件排列在板材(L,W)的左下方，排樣過程就是求解零件的最優(yōu)排列位置，將板材和零件置于同一個二維平面，則零件的位置(x,y)可根據(jù)矩形件的長寬和排列方式確定.實際中，約定按照大件優(yōu)先原則進行排樣，取得盡可能大的利用率的原則進行優(yōu)化排樣.以3個矩形(A,B,C)為例，在排樣的過程中，可看作為排樣樹，如圖2所示.

由圖2可得，3個矩形所構(gòu)成的排樣樹分支數(shù)已經(jīng)很多，在實際的工業(yè)大規(guī)模生產(chǎn)中，工件種類多、數(shù)量大，構(gòu)成的排列樹的分支數(shù)會急劇增加，屬于計算復(fù)雜性較高的一類NP完全問題，隨著零件的增加解的數(shù)量成指數(shù)倍數(shù)增長，因此確定性算法在龐大的解空間中尋找最優(yōu)解的時間會急劇增加，達到讓人不可接受的程度.為了滿足生產(chǎn)需要，高效的求解矩形件排樣問題，并使排樣結(jié)果盡可能接近最優(yōu)，本文提出了一種基于啟發(fā)式的板材排樣優(yōu)化算法，其是在狀態(tài)空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到最終目標(biāo).這樣可以省略大量無謂的搜索路徑，提高了效率.

2.2 評價函數(shù)

評價函數(shù)是啟發(fā)式算法剪枝優(yōu)化的重要依據(jù)，關(guān)系到算法求解問題的效率，其設(shè)計取決于所要求解的優(yōu)化問題本身.評價函數(shù)利用當(dāng)前與問題有關(guān)的信息指導(dǎo)搜索過程，在排樣搜索過程中，通過比較評價函數(shù)值大小，決定要擴展的下一個待排矩形件，省略大量無謂的矩形件試排搜索路徑，以免盲目地擴展搜索，從而加快排樣速度.針對板材排樣問題，給出了如下的評價函數(shù)

(14)

式中：ηrj表示當(dāng)前零件rj在板材上的利用率；γrj表示當(dāng)前零件rj的緊密度；srj為當(dāng)前零件面積；W為可行域面積，可行域指的是待排矩形件在當(dāng)前布局空間所有可行位置的集合.

式(14)中定義了緊密度指標(biāo)γ，用于衡量量化零件之間的緊密程度.若緊密度越大，則這樣的啟發(fā)式放置將有效排列鄰接各物體，使得排樣中的未利用空隙越小，即容器的面積利用率越高.本文緊密度定義為當(dāng)前零件與已排零件之間的關(guān)系.

假設(shè)已經(jīng)排列好的零件個數(shù)為k，放置新的零件時，總是從已經(jīng)排好的零件出發(fā)，使新排列的零件與已排列的零件具有緊密關(guān)系.假設(shè)當(dāng)前待排零件rj的中心點為(xj,yj)，已排零件的中心點為(xci,yci)，則中心點歐式距離為

臺式高速冷凍離心機SG3-18K購于Sigma公司；5424R高速冷凍離心機購于德國 Eppendorf公司；CFX96 Deep Well Real-time System、QX200 Droplet dPCR系統(tǒng)購于美國Bio-rad公司；Tissue Lyser II組織研磨儀、QIAxpert核酸濃度檢測儀購于德國 Qiagen公司。

在選擇排樣放置位置時，選取最小歐式距離的零件，即當(dāng)前零件與已經(jīng)排列好的零件之間的距離為d=min (d1,d2,…,dk).如圖3所示，求當(dāng)前零件rj與已排零件B之間的距離.當(dāng)零件rj橫放時，緊貼零件B，中心距離為d1；當(dāng)零件rj豎放時，中心距離為d1′.

依次類推，求出當(dāng)前待排零件與所有已排零件的距離，比較得出最小值d，記錄緊貼零件ri，記錄rj的擺放位置是橫放或豎放.距離越小，說明零件之間的緊密度越大，則緊密度記為γrj=1/d.

2.3 算法流程

在矩形件優(yōu)化排樣中，矩形件的排放順序和排放方式，影響著板材的利用率.

2.3.1 排樣矩形件定序

待排矩形件的排放順序(矩形件定序)是每種排樣算法不可避免考慮的問題.在排樣研究中，部分算法通?？紤]矩形件自身屬性特征，比如面積大小、長寬比等.根據(jù)式(14)給出的評價函數(shù)，提出的算法對尚未排樣的矩形件在矩形空間的利用價值進行評價，找到其中最大的評價函數(shù)值Fj=max (Fi,i=1,…,m)，則rj作為當(dāng)前待排的矩形件.

2.3.2 排樣矩形件定位

確定待排矩形件的排放順序后，優(yōu)化當(dāng)前待排零件在布局空間中的擺放位置.根據(jù)2.2節(jié)提到的緊密度策略，得出：

1)計算緊密度值最大放置矩形件，如存在多個零件與該零件的緊密度值最大，則進行下一步驟；

2)比較多個零件的中心坐標(biāo)值(xcj,ycj)，若xck

2.3.3 算法主要步驟

算法的主要步驟如圖4所示.

3 實驗驗證及算法性能分析

3.1 實驗環(huán)境及參數(shù)設(shè)置

算法采用1.2節(jié)給出的板材排樣模型，采用 Hopper 和Turton給出的C1～C5組公開案例[12]，同時另定義一組測試案例C6，板材大小為2 000 cm1 500 cm，所用矩形件規(guī)格和數(shù)量分別為：90 cm120 cm， 30；150 cm100 cm，30；280 cm120 cm，28；150 cm250 cm，20；60 cm50 cm，10；50 cm150 cm，5；180 cm220 cm，4；55 cm80 cm，4.

為驗證本文算法的有效性，將其與貪婪算法、模擬退火算法在相同的案例數(shù)據(jù)下分別進行比較.貪婪算法因其算法簡單，在最初研究排樣時廣泛應(yīng)用，其基本思路是從問題的某個初始可行解出發(fā)，逐步向目標(biāo)函數(shù)靠攏.模擬退火算法為當(dāng)前解決問題中常用的智能算法，是解決組合優(yōu)化問題的隨機搜索技術(shù)，不斷對當(dāng)前解迭代，從而達到使目標(biāo)函數(shù)最優(yōu).

模擬退火算法設(shè)置迭代次數(shù)為200，溫度T的初始值設(shè)置是影響模擬退火算法全局搜索性能的重要因素之一，雖T值越大性能越高，但速度也越慢，通常設(shè)置初始溫度T=1 000、終止條件T<1，衰減函數(shù)T′=0.9T.使用Matlab搭建了實驗環(huán)境進行了仿真實驗，針對實驗結(jié)果進行算法性能分析.

3.2 算法性能分析

3.2.1 板材利用率分析

表1中給出3種算法在測試案例數(shù)據(jù)下的板材利用率，所用板材數(shù)以及算法運行時間的情況.由表1中數(shù)據(jù)可得，在案例數(shù)據(jù)C1和C2中，本文算法得板材利用率雖不是最優(yōu)，但隨著矩形件數(shù)量及種類的增加，本文算法相比于另外兩種算法都有較大的提高，因此，本文提出的啟發(fā)式優(yōu)化算法表現(xiàn)出較強的全局尋優(yōu)能力.

表1 不同算法性能比較

圖5為測試案例C6下3種算法的排樣結(jié)果.從圖5中可以看出本文算法排樣結(jié)果相對規(guī)整，產(chǎn)生的空隙廢料少，具有較好的排樣效果.

3.2.2 時間復(fù)雜度分析

根據(jù)表1可知，不同算法耗時情況隨著矩形件數(shù)量的增加，本文算法排樣時間仍保持較低增長且耗時遠低于模擬退火算法，而模擬退火算法耗時急劇上升.另外，由于模擬退火算法中通過退火溫度控制著求解過程向最小值的優(yōu)化方向進行，通常情況下，為了能夠使求解的值接近全局最優(yōu)解，退火速度會設(shè)置較小值，則增加了運算規(guī)模.因此在大規(guī)模工業(yè)生產(chǎn)中，會耗費大量時間，不符合實際生產(chǎn)需求.

4 結(jié)論

1)本文提出的啟發(fā)式板材排樣優(yōu)化算法，主要是利用問題本身的信息作為啟發(fā)式的搜索信息，通過分析零件之間的緊密度及利用率，設(shè)計評價函數(shù).在排樣過程中，通過比較評價函數(shù)值的大小，可進行剪枝，在提高利用率的同時，縮短時間.

2)實驗結(jié)果表明所提方案的有效性和可行性，符合現(xiàn)代大規(guī)模工業(yè)生產(chǎn)的需求.

本算法還可以進一步研究，比如考慮板材為不規(guī)則板材以及裁剪的零件為多邊形零件或不規(guī)則零件，使研究方案更加符合生產(chǎn)需求，尋找合理的方法解決后續(xù)的問題.