基于貪婪最佳優(yōu)先搜索算法的方形件排樣優(yōu)化問題研究

劉艷麗，李軍祥 （上海理工大學(xué)管理學(xué)院，上海 200093）

0 引 言

受益于我國良好的制造業(yè)基礎(chǔ)及政府對制造業(yè)智能化轉(zhuǎn)型升級的大力推動(dòng)，近年來智能制造行業(yè)的發(fā)展較為迅速。智能制造裝備具有分析、推理和感知等功能，它是智能技術(shù)、信息技術(shù)和先進(jìn)制造技術(shù)的集成和深度融合[1]。隨著生產(chǎn)技術(shù)的發(fā)展，在工業(yè)4.0 的數(shù)字化轉(zhuǎn)型背景下，眾多企業(yè)開始以個(gè)性化定制和供應(yīng)鏈整合為切入，實(shí)現(xiàn)以用戶為中心的大規(guī)模個(gè)性化定制[2]。當(dāng)前在新一代數(shù)字科技的支撐和引領(lǐng)下，越來越多新興的智能制造企業(yè)開始進(jìn)行數(shù)字化升級、轉(zhuǎn)型和再造，建設(shè)數(shù)字化智能工廠，提升智能制造能力和個(gè)性化定制能力，使得在面對用戶需求時(shí)能夠做到快速響應(yīng)、有效應(yīng)變。

方形件產(chǎn)品是指采用板材為主要用料，經(jīng)過一系列程序加工后生成板式配件，再按照圖紙進(jìn)行組裝后形成的一類產(chǎn)品[3]。這類產(chǎn)品多用于制造企業(yè)，主要面向包括通訊設(shè)備、精密機(jī)床制造、消費(fèi)性電子、金屬板材等產(chǎn)業(yè)的多個(gè)領(lǐng)域。為了保量和以最小化的成本制造滿足顧客需求的個(gè)性化產(chǎn)品，智能制造企業(yè)大多采用多品種、小批量和個(gè)性化定制方式進(jìn)行生產(chǎn)，采用“訂單組批+批量生產(chǎn)+訂單分揀”的模式，通過訂單組批來實(shí)現(xiàn)批量切割以更好地發(fā)揮規(guī)模效益，再整合訂單中的共同需求得到不同客戶的揀取信息進(jìn)行訂單分揀[4]。

其中，個(gè)性化定制生產(chǎn)模式涉及排樣優(yōu)化這一關(guān)鍵性問題。排樣優(yōu)化本質(zhì)上是一個(gè)下料問題，是指將一系列方形件按最優(yōu)方式在板材上進(jìn)行排布，要求方形件排放在板材內(nèi)，各個(gè)方形件互不重疊，并滿足一定的工藝要求。優(yōu)化的目標(biāo)是生成最合理的排樣方式，最大限度地節(jié)約材料、提高材料利用率，實(shí)現(xiàn)切割過程的簡化。該問題是一個(gè)組合優(yōu)化問題，計(jì)算復(fù)雜度很高，也是運(yùn)籌學(xué)領(lǐng)域一個(gè)非常重要的分支。許多制造企業(yè)生產(chǎn)產(chǎn)品和零部件的第一步即下料，過程中會(huì)消耗大量的材料和資源，如果不合理規(guī)劃則會(huì)造成巨大的浪費(fèi)。因此，本文構(gòu)建了一個(gè)排樣優(yōu)化模型，考慮了一系列相關(guān)約束，利用貪婪最佳優(yōu)先搜索算法對模型進(jìn)行求解，針對各數(shù)據(jù)集給出其最佳的排樣效果圖，驗(yàn)證了模型的有效性及可行性。

1 問題描述及假設(shè)

1.1 排樣優(yōu)化問題描述

本文采用3 階段切割方式，要求只能進(jìn)行齊頭切且每個(gè)階段只能選擇一個(gè)方向進(jìn)行切割。齊頭切也稱“一刀切”，要求每次進(jìn)行直線切割時(shí)板材都能分成兩塊[5]。3 階段切割方式如圖1 所示，第1 階段進(jìn)行橫向切割，此時(shí)生成的模塊稱為Stripe（條帶），如Stripe1 和Stripe2；第2 階段進(jìn)行縱向切割生成的模塊稱為Stack（棧），如Stripe1 被切割分成Stack1、Stack2 和Stack3；接下來進(jìn)行第三階段的橫向切割，生成的模塊稱之為Item（產(chǎn)品項(xiàng)），如Stack1 繼續(xù)被分成Item1、Item2 和Item3。本文基于以上規(guī)則對方形件進(jìn)行切割。排樣優(yōu)化問題屬于二維組合優(yōu)化問題，通過研究方形件在板材上的排放順序和排放方式，使得方形件在板材上組合排放的利用率達(dá)到最高。具體來說就是根據(jù)同一個(gè)生產(chǎn)排次內(nèi)的方形件尺寸和數(shù)量進(jìn)行原片規(guī)格和數(shù)量的選擇。該問題要求在滿足生產(chǎn)訂單需求和相關(guān)約束條件下，進(jìn)行下料排樣優(yōu)化，盡可能減少板材用量，避免浪費(fèi)，使板材原片的利用率達(dá)到最大。其中需要考慮的約束條件如下：（1） 在相同棧里的產(chǎn)品項(xiàng)的寬度（或長度） 應(yīng)該相同；（2） 最終切割生成的產(chǎn)品項(xiàng)是完整的，非拼接而成。該問題本質(zhì)上是一個(gè)二維裝箱問題，也就是將若干個(gè)矩形物品裝進(jìn)矩形的箱子中，并且在裝箱的過程中不允許將矩形物品斜著放，必須平行于橫坐標(biāo)。一般來說求解的目標(biāo)是使箱子的數(shù)目或者是空間占用率最小。當(dāng)用于矩陣存儲(chǔ)時(shí)，求解的最優(yōu)目標(biāo)便是箱子的空間占用率最大化。

圖1 不同切割階段的形式定義

1.2 假設(shè)與約束條件

（1） 只考慮齊頭切的直線切割方式，切割方向均垂直于板材的一條邊，且每次切割板材都可以分成兩塊；

（2） 切割階段數(shù)不超過3，且同一個(gè)階段的切割方向相同；

（3） 排樣方式為精確排樣，即在三個(gè)階段內(nèi)能切割出準(zhǔn)確尺寸的方形件；

（4） 板材原片只有一種規(guī)格并且數(shù)量充足；

（5） 排樣方案不考慮切割縫隙寬度的影響。

2 排樣優(yōu)化模型構(gòu)建

方形件排樣優(yōu)化問題用數(shù)學(xué)語言可以描述為：將n個(gè)不同規(guī)格的方形零件{k1,k2,…,kn}排入到一個(gè)寬度為M，長度L的板材原片中，且板材原片數(shù)充足，待排樣的毛坯有m種，長、寬、高需求量分別為（li,wi,di），其中i為毛坯型號。B={1,2,…,b}是一個(gè)由b個(gè)相同的方形件組成的集合，stack（k∈B）的寬度為W，高度為H。N={1,2,…,n}是一個(gè)由n個(gè)item組成的集合，其中n≥b。

設(shè)板材原片左下角為原點(diǎn)（0,0），左上角為（0,M），右下角為（L,0），x和y表示item在其分配的stack內(nèi)的位置，即方形件ki的左上角坐標(biāo)為（xi,yi），其中xi≥0，yi≥0，i∈N*。第i個(gè)item（i∈N）的寬度wi≤W，高度hi≤H，若ki旋轉(zhuǎn)了90°，則其寬度和高度互換，ri為是否旋轉(zhuǎn)變量，ri=1 表示旋轉(zhuǎn)，ri=0 不旋轉(zhuǎn)，則ki右下角坐標(biāo)為（xi+（1-ri）wi+rihi,yi-（1-ri）hi-riwi）。N*表示由旋轉(zhuǎn)的重復(fù)項(xiàng)附加的集合N，第i個(gè)item（i∈N）的重復(fù)項(xiàng)是寬度為hi，高度為wi的第n+i項(xiàng)。當(dāng)?shù)趇個(gè)由旋轉(zhuǎn)后的重復(fù)項(xiàng)item不能進(jìn)入stack，即wi≤H，hi≤H，則其相應(yīng)的決策變量沒有被定義，因此忽略不計(jì)，其余相應(yīng)的變量均如此。因此利用（xi,yi）、wi、hi及ri即可確定ki在板材原片中的排樣位置，因此方形件ki可用一個(gè)五元組表示[6]：

f表示將item分配到stack，如果第i個(gè)item被分配到第k個(gè)stack中，其中fik=1，則i∈N*，k∈B，否則為0。l和u是二進(jìn)制的，它們表示兩個(gè)item的相對位置lij=1（uij=1 ），i∈N*，j∈N*，i≠j，j≠i+n且i≠j+n，用于當(dāng)i和j在同一個(gè)stack中使i位于j的左邊。P={p1,…,pk}明確每種排樣方式中所包含的i型毛坯數(shù)量aij、排列位置和順序，確定排樣方式的使用頻率mj,i=1,2,…,m,j=1,2,…,m，其中mj是整型決策變量。

在滿足訂單需求和相關(guān)約束條件下，使得板材原片的用量盡可能少，即使板材原片利用率（零件占用面積/板材原片面積）最大，從而達(dá)到節(jié)省材料的目的。要求滿足的約束條件如下：

（1）ki與kj互不重疊：

其中：（i,j）∈N*2,i≠j,j≠i+n,i≠j+n。

（2） 在板材原片的長度方向，所有零件長度之和應(yīng)不大于板材原片長度L，即：

（3） 在板材原片的寬度方向，所有零件長度之和應(yīng)不大于板材原片的寬度M，即：

（4） 每個(gè)item（i∈N）必須在沒有重疊的情況下進(jìn)行包裝，并且ki必須完全包含在其分配的stack中：

（5）ki的邊必須與板材原片的邊平行，且在放入時(shí)可以進(jìn)行90°旋轉(zhuǎn)：

（6） 最終切割生成的產(chǎn)品項(xiàng)是完整的，非拼接而成：

其中：xj∈N,j=1,2,…,K。

這是一個(gè)二維三階段剪切下料問題，求解的目標(biāo)可以簡述為使用數(shù)量最少的板材原片，排完全部數(shù)據(jù)集給出的所有訂單毛坯[7]。通過建立混合整數(shù)規(guī)劃模型確定所求的目標(biāo)函數(shù)如下：

其中：z為板材原片的數(shù)量，i為毛坯型號，m為待排樣的毛坯種類，aij為毛坯數(shù)量，K為排樣方式的種類，xj為排樣方式使用的頻率且為整型決策變量。

在本文中排樣優(yōu)化問題的解由三階段同質(zhì)排樣方式（3H） 組成，滿足了題中切割時(shí)在相同棧里的產(chǎn)品項(xiàng)的寬度或長度相同約束，而3H中存在約束三階段排樣問題，即求解毛坯在原片板材上的3H排樣方式所得的毛坯價(jià)值最大化，相關(guān)約束排樣問題的整數(shù)規(guī)劃模型表示如下：

其中：Zp表示3H排樣方式最大化板材中所包含的毛坯總價(jià)值，ai表示3H中的i型毛坯的數(shù)量，vi表示i型毛坯的價(jià)值，ri表示i型毛坯的當(dāng)前剩余需求量。

3 仿真實(shí)驗(yàn)設(shè)計(jì)與分析

3.1 仿真實(shí)驗(yàn)

實(shí)驗(yàn)環(huán)境：硬件配置為Intel 酷睿i5，主頻1.80GHz，內(nèi)存12GB；軟件配置為Windows11 64 位操作系統(tǒng)；求解均使用MatlabR2018b 編程實(shí)現(xiàn)。在程序測試時(shí)，設(shè)定板材原片尺寸為2 440×1 220，切縫寬度為1，輸入?yún)?shù)為：（1） 單個(gè)批次產(chǎn)品項(xiàng)總數(shù)上限max_item_num=1 000；（2） 單個(gè)批次產(chǎn)品項(xiàng)的面積總和上限max_item_area=250（m2）。為了增加實(shí)驗(yàn)的可信度，本文針對排樣優(yōu)化問題共收集了4 個(gè)數(shù)據(jù)集進(jìn)行算法的驗(yàn)證，分別為數(shù)據(jù)集dataA1、dataA2、dataA3 和dataA4。各數(shù)據(jù)集均源于中國研究生創(chuàng)新實(shí)踐系列大賽網(wǎng)站（https://cpipc.acge.org.cn），其中各個(gè)數(shù)據(jù)集是相互獨(dú)立的。

3.2 模型求解與結(jié)果分析

本文運(yùn)用貪婪最佳優(yōu)先搜索算法對混合整數(shù)規(guī)劃模型進(jìn)行求解。貪婪最佳優(yōu)先搜索是一種啟發(fā)式搜索算法，也可以把它看成廣度優(yōu)先搜索算法的一種改進(jìn)；算法思想是將節(jié)點(diǎn)按距離目標(biāo)的距離進(jìn)行排序，然后以這個(gè)距離為代價(jià)選擇待擴(kuò)展的節(jié)點(diǎn)[8]。在對方形件排樣優(yōu)化過程中，每一步都選用當(dāng)下解空間的最優(yōu)排放順序，通過一次遍歷就可以得到最優(yōu)解。以下是程序運(yùn)行出來的排樣方案效果圖，因數(shù)量太多，此處針對每個(gè)數(shù)據(jù)集僅列舉部分圖片。圖2 至圖5 分別為數(shù)據(jù)集dataA1、dataA2、dataA3和dataA4 的部分排樣圖。從圖中可知，每一塊板材都得到了極大地利用，浪費(fèi)空間很小。

圖2 dataA1 排樣圖

圖3 dataA2 排樣圖

圖4 dataA3 排樣圖

圖5 dataA4 排樣圖

本文以板材利用率（產(chǎn)品項(xiàng)面積之和/使用原片面積之和） 作為結(jié)果指標(biāo)，實(shí)驗(yàn)結(jié)果對比如表1 所示，板材利用率分別為91.70%、90.97%、93.97%和95.07%，說明該算法在節(jié)省板材資源和提高板材利用率方面效果顯著。本文算法在dadaA1、dataA2、dataA3 和dataA4 數(shù)據(jù)集生成排樣方案的過程中分別考察了90 個(gè)、90 個(gè)、88 個(gè)和85 個(gè)排樣方式，平均每個(gè)排樣方式耗時(shí)0.05s。由此可見該算法還具有靈活、高效和計(jì)算方便的優(yōu)點(diǎn)。

表1 實(shí)驗(yàn)結(jié)果對比表

4 小 結(jié)

排樣優(yōu)化問題廣泛地存在于產(chǎn)品制造企業(yè)，如3C、板式家具、玻璃、鈑金件等行業(yè)的生產(chǎn)過程中，一個(gè)好的優(yōu)化算法可解決材料利用率低、生產(chǎn)效率低及個(gè)性化與生產(chǎn)高效性之間的矛盾。針對排樣優(yōu)化問題，本文設(shè)計(jì)了一種基于貪婪最佳優(yōu)先搜索算法生成相同棧里的產(chǎn)品項(xiàng)的寬度或長度相同的三段排樣方式，減少了原材料的浪費(fèi)，提高了板材利用率，為制造企業(yè)進(jìn)行大規(guī)模個(gè)性化定制提供了可能。本文模型結(jié)合實(shí)際情況建立，與實(shí)際情況密切聯(lián)系，通用性和推廣性很強(qiáng)。同時(shí)實(shí)驗(yàn)結(jié)果表明，本文的算法可以有效地減少板材用量，且計(jì)算時(shí)間可以滿足實(shí)際應(yīng)用需要，具有一定的現(xiàn)實(shí)意義。此外訂單組批問題是個(gè)性化生產(chǎn)模式中的另一關(guān)鍵問題，下一步將對此問題進(jìn)行深入研究，通過訂單組批來保證貨物的交貨期，幫助企業(yè)實(shí)現(xiàn)訂單的批量化生產(chǎn)。