基于禁忌搜索的含異形板件的板式家具碼垛優(yōu)化算法

摘要： 為了減少含異形板件的板式家具打包的包裹個數(shù)，提出基于禁忌搜索的該類板式家具碼垛優(yōu)化算法； 分析該類板式家具碼垛問題的約束條件，并建立目標函數(shù)；采用可以有效確定訂單中所有該類板式家具碼垛順序與旋轉(zhuǎn)方向的編碼方式，并利用啟發(fā)式算法生成實時監(jiān)測包裹質(zhì)量的較優(yōu)初始解，以便利用禁忌搜索求解該類板式家具碼垛問題； 結合臨界多邊形和最低水平線法，設計將編碼轉(zhuǎn)換為對應碼垛方案的解碼方式，并給出所提出算法的適配值函數(shù)及鄰域結構； 利用禁忌搜索計算該類板式家具訂單，確定并優(yōu)化每個板件的碼垛順序、 旋轉(zhuǎn)方向與碼垛位置，得到包裹個數(shù)較少的碼垛方案； 選取歐洲排樣問題興趣小組（ESICUP）提供的算例測試所提出的算法，并與已有研究中可復現(xiàn)的板件智能分包方法對比。結果表明，相對于對比方法，所提出算法所得該類板式家具打包的包裹個數(shù)減少38.46%，驗證了所提出算法的可行性與有效性。

關鍵詞： 家具打包； 碼垛優(yōu)化； 禁忌搜索； 異形板件； 臨界多邊形； 最低水平線法； 板式家具

中圖分類號： TP391.7

文獻標志碼： A

開放科學識別碼（OSID碼）：

Stacking Optimization Algorithm for Panel-type Furniture Containing

Irregular Panels Based on Tabu Search

JI Yanqing， ZHAO Shikui

（School of Mechanical Engineering， University of Jinan， Jinan 250022， Shandong， China）

Abstract： To reduce parcel number for packing panel-type furniture containing irregular panels， a stacking optimization algorithm for the panel-type furniture based on tabu search was proposed. Constraints of thestackingproblemforthepanel-type furniture were analyzed， and an objective function was established. An encoding mode was adopted to determine stacking sequences and rotation directions of the panel-type furniture in orders， and heuristic algorithm was utilized togeneratebetterinitialsolutionsforreal-time monitoring of parcel mass， so astousetabusearchtosolvethestackingproblem forthepanel-typefurniture.Combinedwithnofitpolygonandlowesthorizontalline method， a decoding mode was designed to convert the encoding into the corresponding stacking scheme， and a fitness function and a neighborhood structure of the proposed algorithm were given. Tabu search was used to calculate the orders of the panel-type furniture to determine and optimize stacking sequence， rotation direction and stacking position of each panel， and a stacking scheme with fewer parcels was thus obtained. The proposed algorithm was tested on examples provided by European Special Interest Group on Cutting andPackingandcomparedwithanexistingreproducibleintelligentpacketmethod. The results show that compared with the contrast method， the proposed algorithm reduces parcel number for packing the panel-type furniture by 38.46%， verifying feasibility and effectiveness of the proposed algorithm.

Keywords： furniture packing; stacking optimization; tabu search; irregular panel; no fit polygon; lowest horizontal line method; panel-type furniture

隨著現(xiàn)代科技的不斷發(fā)展，人們對個性化的要求越來越高。在充滿多樣化和個性化需求的時代，家具企業(yè)的生產(chǎn)方式逐漸由傳統(tǒng)的大批量生產(chǎn)模式轉(zhuǎn)向大規(guī)模定制的生產(chǎn)模式^［1］。板式家具通常經(jīng)過一系列設備加工^［2］和智能分揀^［3］后進行包裝和運輸； 但定制板式家具可能含有較多的非標準板件，即含異形板件的板式家具（簡稱異形板式家具），因此加大了加工、 打包的難度。陳炫銳等^［4］提出一種板式家具訂單組批的啟發(fā)式算法，提高了設備的利用率以及原材料的利用率。一個合理的碼垛方案能夠有效減少包裹個數(shù)及包裹內(nèi)空隙，從而降低包裝和運輸成本。一些學者研究了板式家具打包的碼垛問題。汪金朋^［5］提出一種基于啟發(fā)式算法和混合遺傳算法的串級優(yōu)化組合算法，有效提高了家具裝箱的質(zhì)量和算法運行效率。羅斌等^［6］提出一種可復現(xiàn)的板件智能分包方法，按照板式家具板件尺寸由大到小的順序，利用最低水平線法，由底層開始逐層碼垛板件以解決板式家具的碼垛問題，結果表明，板件智能分包方法能有效解決不含異形板件的板式家具碼垛問題。

板式家具并不只含有矩形板件。當板式家具中含有較多異形板件且所有板件厚度相同時，異形板式家具碼垛問題即可轉(zhuǎn)化為具有特殊約束的二維不規(guī)則多邊形排樣問題。二維不規(guī)則多邊形排樣問題在工業(yè)領域中應用廣泛，國內(nèi)外許多學者深入研究了該問題，提出了很多可行的不規(guī)則多邊形排樣算法。Agrawal^［7］通過不規(guī)則圖形的最小包絡矩形將不規(guī)則多邊形排樣問題轉(zhuǎn)化為矩形排樣問題，降低了求解難度。Jakobs^［8］提出在不規(guī)則圖形轉(zhuǎn)化為矩形排樣后，對排樣結果實施擠壓運算，減小圖形之間的間隙，從而優(yōu)化排樣結果。Adamowicz等^［9］提出基于多邊形表示法的臨界多邊形（no fit polygon，NFP）算法，通過獲得不規(guī)則多邊形的NFP，快速判斷2個多邊形之間的干涉情況，由此確定圖形的排樣位置是否合理。Bennell等^［10］研究了NFP的生成方法及其位置狀態(tài)評估方法，結果表明，利用NFP算法可以實現(xiàn)不規(guī)則多邊形的高效排樣。將不規(guī)則多邊形排樣算法與智能優(yōu)化算法相結合可以更好地處理實際問題。劉胡瑤等^［11］基于NFP最低重心位置放置規(guī)則并結合遺傳算法，在處理板材內(nèi)部帶孔洞或邊界形成空腔等特殊情況時取得了較好的效果。梁利東等^［12］針對不規(guī)則件排樣問題，提出應用粒子群算法優(yōu)化求解的方法，提高了船體零件智能排樣系統(tǒng)自動排樣的效率，獲得了較好的排樣結果。韓偉等^［13］基于模擬退火算法思想引入溫度參數(shù)控制權重的變化率，探討貫通約束不規(guī)則凸多邊形的排樣問題，有效提高了排樣出材率。閆嘉等^［14］提出一種改進的免疫遺傳算法優(yōu)化零件排放次序，結合NFP及基于底左（bottom-left）算法選擇排放點，有效提高了材料利用率。

雖然目前有些算法能夠使含矩形板件的板式家具（簡稱矩形板式家具）的碼垛問題取得較好的解， 但是在實際應用過程中， 此類板式家具碼垛算法^［5-6］并沒有將異形板式家具考慮在內(nèi)。 由于異形板件比矩形板件含有更多的尺寸信息， 因此導致異形板式家具的打包任務無法順利完成。 本文中通過分析異形板式家具碼垛問題的約束條件， 建立目標函數(shù)； 利用禁忌搜索優(yōu)化板件的碼垛順序與旋轉(zhuǎn)方向， 并結合NFP及最低水平線法選擇碼垛位置， 提出基于禁忌搜索的異形板式家具碼垛優(yōu)化算法（簡稱本文算法）； 選取歐洲排樣問題興趣小組（ESICUP）提供的算例測試本文算法， 并且與板件智能分包方法^［6］對比， 驗證本文算法的可行性與有效性。

1 異形板式家具碼垛問題描述

異形板式家具打包是將一個訂單中所有板件按照一定順序和約束規(guī)則碼垛到足夠多的托盤上，再由打包機器將托盤上的板件打包形成包裹。托盤使用數(shù)量的增加代表該訂單打包的包裹個數(shù)的增加。異形板式家具碼垛問題以實現(xiàn)所有板式家具打包且包裹個數(shù)最少為目標，研究如何將板式家具打包到盡可能少的包裹中，旨在解決訂單中每個板件的碼垛順序、 旋轉(zhuǎn)方向、 碼垛位置等。

由于板件的厚度相同并且形狀類似薄片， 因此可以將異形板式家具碼垛問題看作具有特殊約束條件的二維排樣問題， 目標函數(shù)是所用包裹的最少個數(shù)。異形板式家具碼垛問題的約束條件如下： 1）單塊底板約束。碼垛時托盤上板件最下層只能有1塊板件，稱為底板， 底板為該托盤上底面積最大的板件。根據(jù)托盤的長度、 寬度和板件在托盤上允許碼垛的高度， 可以生成一個假想的三維長方體空間， 稱為托盤空間。托盤的底板確定后， 該托盤空間的長度、 寬度縮小至與底板的包絡矩形長度、 寬度相同。 2）外形約束。 板件之間不能在空間上發(fā)生重疊， 并且板件邊緣不能超出托盤空間。 3）質(zhì)量、 高度約束。包裹的質(zhì)量、 高度均不能超過限定大小。

根據(jù)上述描述，異形板式家具碼垛問題的目標函數(shù)為

min N=∑Mj=1Yj ，（1）

Yj= Cjgt;0 ，

0， Cj=0 ，（2）

式中： N為打包的包裹個數(shù)； M為托盤總個數(shù)且足夠大； Yj為第j個托盤的使用狀態(tài)； Cj為第j個托盤上的板件個數(shù)。當?shù)趈個托盤在使用狀態(tài)時， Cj大于0， Yj記為1，打包機器在后續(xù)打包過程中將1個托盤上碼垛的板件打包形成1個包裹。

2 禁忌搜索求解過程

禁忌搜索^［15］是模擬人類智力過程而形成的一種全局逐步尋優(yōu)算法。針對異形板式家具的碼垛問題，本文算法的原理如下： 在針對該問題的優(yōu)化變量編碼后，利用啟發(fā)式算法生成初始解； 通過鄰域結構搜索鄰域，生成候選解； 利用解碼方法與適配值函數(shù)判斷候選解的優(yōu)劣，即比較候選解對應的狀態(tài)與記錄的最優(yōu)狀態(tài)，如果存在候選解對應的狀態(tài)更優(yōu)，則將此候選解作為當前解，否則，將候選解中非禁忌對象對應的最佳解作為當前解； 選擇當前解對應的禁忌對象實施禁忌，在迭代過程中逐漸獲得較優(yōu)解，即較優(yōu)的碼垛方案。圖1所示為本文算法流程。

2.1 編碼方式

在本文算法的后續(xù)碼垛過程中不區(qū)分矩形板件和異形板件，所有板件均按異形板件處理。由于異形板式家具打包的一個訂單中板件個數(shù)較多，二進制編碼方式難以滿足異形板式家具碼垛問題需求，因此采用實數(shù)編碼方式。本文算法采用長度為板件個數(shù)的2倍的十進制編碼。先對訂單中的板件按訂單中的順序編號，這些編號組成的整數(shù)串為順序編碼，表示板件的碼垛順序。板件的碼垛方向由2個部分組合確定： 根據(jù)板件的順序編碼符號確定板件是否先旋轉(zhuǎn)90°，負號表示板件先旋轉(zhuǎn)90°，正號含義相反； 根據(jù)旋轉(zhuǎn)編碼1、 0判斷板件是否再旋轉(zhuǎn)180°，1表示板件再旋轉(zhuǎn)180°，0的含義相反。根據(jù)該編碼方式可以有效確定訂單中所有板式家具的碼垛順序與旋轉(zhuǎn)方向。板件旋轉(zhuǎn)角度與編碼的關系如表1所示。

禁忌搜索的解編碼如圖2所示。假設在一個訂單中有6塊板件，編碼為（5，4，-1，3，2，-6，0，1，1，0，0，0）。前6位表示板件5最優(yōu)先、 板件4次優(yōu)先、 ……、 板件6最后的碼垛順序，其中板件1、6的順序編碼符號為負號，表示板件1、 6先旋轉(zhuǎn)90°。后6位中板件4、 1的旋轉(zhuǎn)編碼為1，表示板件4再旋轉(zhuǎn)180°，板件1再旋轉(zhuǎn)180°即共旋轉(zhuǎn)270°。

2.2 初始解生成方法

禁忌搜索屬于單點類搜索算法，對初始解的依賴性較大，以完全隨機的方式生成的初始解可能很差，經(jīng)過多次搜索后效果可能較差，因此本文中利用啟發(fā)式算法生成初始解，步驟如下：

步驟1 在未碼垛板件中選擇面積最大的板件作為底板開始碼垛。生成與底板的包絡矩形尺寸相同的可碼垛空間，生成水平線集合，此時空間的底邊即為可碼垛最低水平線。

步驟2 選取一段最低水平線，在利用最低水平線碼垛板件時，板件的尺寸表述為寬度、高度和厚度。在未碼垛板件中按照寬度減小的順序選擇1個寬度小于或等于最低水平線寬度、 板件碼垛后高度不超過碼垛空間高度且包裹質(zhì)量最大的板件，記錄該板件寬度； 如果不存在寬度小于或者等于最低水平線寬度的板件，則板件寬度記為0。在未碼垛板件中按照高度減小的順序選擇1個高度小于最低水平線寬度、 板件碼垛后高度不超過碼垛空間高度且包裹質(zhì)量最大的板件，記錄該板件高度； 如果不存在高度小于最低水平線寬度的板件，則板件高度記為0。選擇所記錄寬度、 高度中的較大值，此時有2種情況： 1）如果記錄的數(shù)據(jù)為寬度，則在未碼垛板件中選擇寬度等于記錄數(shù)據(jù)的1個板件碼垛在最低水平線上，更新水平線集合；如果記錄的數(shù)據(jù)為高度，則在未碼垛板件中選擇高度等于記錄數(shù)據(jù)的1個板件旋轉(zhuǎn)后碼垛在最低水平線上，更新水平線集合。所有板件碼垛完成后，碼垛結束。2）如果記錄的數(shù)據(jù)為0，則所有未碼垛板件不可碼垛在最低水平線上，此時須將最低水平線的高度提升為最低水平線左、右鄰居中水平線高度的較小值。更新水平線集合。

步驟3 重復步驟2，直至最低水平線不能再提升，表示當前層已無法碼垛任何板件。包裹未滿時換層，即重新生成尺寸大小與底板相同的可碼垛空間以及水平線集合，直至達到包裹的最大層數(shù)，表示包裹已滿，須更換底板，碼垛下一個包裹，即執(zhí)行步驟1。

在初始解生成過程中， 記錄每個碼垛板件的碼垛順序與旋轉(zhuǎn)方向， 碼垛時板件的旋轉(zhuǎn)角度未發(fā)生改變， 則板件的順序編碼符號為正， 否則符號為負。 在所有板件碼垛完成后， 即可得到一串帶符號的十進制順序編碼， 旋轉(zhuǎn)編碼部分均為0， 可以利用解碼方法將兩者組合成的編碼轉(zhuǎn)化為一個碼垛方案。

2.3 鄰域結構設計

鄰域結構是由當前解通過鄰域移動生成候選解的途徑，不同的鄰域結構會影響算法的搜索空間與算法的搜索質(zhì)量、 效率。本文中采用交換2個板件的碼垛順序與旋轉(zhuǎn)方向的方式作為鄰域結構，同時交換2個板件的碼垛順序及對應的旋轉(zhuǎn)編碼，并將2個板件的旋轉(zhuǎn)角度增加90°。在搜索過程中，采用隨機選擇方式選取板件，生成多個候選解，根據(jù)適配值函數(shù)，保留候選解的前半部分適配值函數(shù)值較大的較好的候選解。以其中某個候選解的生成過程為例，當前解的候選解生成過程如圖3所示，其中交換板件4、 2的碼垛順序，并且改變板件4、 2的碼垛方向，板件4由原本旋轉(zhuǎn)270°變?yōu)椴恍D(zhuǎn)后直接碼垛，板件2由不旋轉(zhuǎn)變?yōu)樾D(zhuǎn)90°后再碼垛。

2.4 NFP的計算

生成NFP的方法很多，本文中使用移動碰撞法^［16］生成NFP。假設有多邊形A、 B，求解多邊形B相對于A生成的NFP。多邊形點的存儲形式為逆時針方向有序存儲，多邊形A、 B按照逆時針依次連接形成有向環(huán)。多邊形A、 B有向環(huán)的形成方式如圖4所示。

多邊形A、 B的NFP生成步驟如下：

步驟1 尋找多邊形A的最低點，如果有多個最低點，則選擇最右邊的； 尋找多邊形B的最高點，如果有多個最高點，則選擇最左邊的。移動B，使A的最低點與B的最高點相接觸。

步驟2 尋找平移向量。多邊形A、 B有多種接觸方式，如圖5所示。A、 B的不同接觸方式生成不同的平移向量： 1）在點對點的接觸方式下，以接觸點為起點，以A、 B內(nèi)的下一個點為終點生成向量a、 b。根據(jù)b與a的叉乘積判斷2個向量的夾角大?。?如果b與a的叉乘積在z軸的正方向，則說明2個向量的夾角小于180°，平移向量為-b；如果b與a的叉乘積在z軸的負方向，則說明2個向量的夾角大于180°，平移向量為a。2）當A的頂點在B的邊上時，平移向量為-b。3）當B的頂點在A的邊上時，平移向量為a。

步驟3 刪除不可行平移向量。2個多邊形在移動過程中存在多處接觸的情況，在每個接觸處均生成平移向量，最終生成多個平移向量。這些平移向量不一定指向同一方向，有的平移向量會導致2個多邊形相撞。為了避免這種情況，須刪除此類平移向量。不可行平移向量的判斷方法如下： 1）在點對點的接觸方式下，當向量a、 b夾角大于180°時，同時滿足與a、 b夾角小于180°的向量為不可行平移向量； 當a、 b夾角小于或等于180°時，同時滿足與a、 b夾角大于180°的向量為不可行平移向量。2）當A的頂點在B的邊上時，與向量b夾角大于180°的向量為不可行平移向量。3）當B的頂點在A的邊上時，與向量a的夾角小于180°的向量為不可行平移向量。用圓弧表示不可行的弧度區(qū)間，不可行平移向量的弧度區(qū)間如圖6所示。

步驟4 修剪可行的平移向量。按照生成的平移向量方向移動后也會出現(xiàn)2個多邊形相撞的情況，須修剪平移向量至合適的長度，方法如下： 1）根據(jù)未修剪的向量平移B的頂點，然后將平移前、后各頂點相連，形成連線，判斷該連線是否與A的各邊相交。如果相交，則求交點的位置。平移向量修剪為將B的頂點移至交點所需的向量， 并記錄修剪后的平移向量。 2）向平移向量的負方向平移A， 判斷多邊形A的頂點與平移后位置的連線是否與B的線段相交。 如果相交， 則求交點的位置。 平移向量修剪為交點移動至多邊形A頂點的向量， 并記錄修剪后的平移向量。 3）判斷B的頂點與根據(jù)未修剪向量平移后位置的連線內(nèi)是否含有A的頂點。 如果有， 則平移向量修剪為將該頂點移至A的頂點所需的向量， 并記錄修剪后的平移向量。 4）判斷B的頂點平移后是否越過起點。 如果越過， 則平移向量修剪為B的該頂點到起點所需的向量， 并記錄修剪后的平移向量。 5）根據(jù)所記錄的最短平移向量移動B。

步驟5 重復步驟2、 3、 4，直至回到初始位置。選擇B的任一頂點為參考點，對參考點每次移動后的位置連線，形成的封閉圖形即為B環(huán)繞A生成的NFP。

圖7所示為多邊形A、 B計算生成的NFP。

2.5 基于NFP的板件位置調(diào)整

在碼垛前計算所有板件相互之間可能生成的NFP并存儲，從而避免因在碼垛過程中重復計算NFP而浪費大量時間。在板件碼垛過程中，根據(jù)當前板件與已碼垛板件生成的NFP，判斷當前板件在最低水平線上碼垛后是否可以向下或向左移動。判斷當前板件是否可以向下移動的步驟如下：

步驟1 利用NFP判斷當前層內(nèi)所有已碼垛板件，將已生成的對應NFP移動到相應的位置。

步驟2 從生成臨界多邊形的參考點處向下發(fā)出1條射線。

步驟3 記錄射線穿過NFP的次數(shù)，若相交次數(shù)大于0，計算射線起點與交點的距離，并記錄最小距離。根據(jù)最小距離移動板件。

判斷當前板件是否可以左移的步驟大致相同，不同之處在于必須將從參考點發(fā)出射線的方向改為向左，即x軸負方向，移動后根據(jù)當前板件的位置更新最低水平線。

多邊形B根據(jù)NFP的移動過程如圖8所示。

2.6 解碼方法和適配值函數(shù)設計

解碼的目的是翻譯和解釋初始解和候選解所代表的碼垛方案， 即每個板件的碼垛順序、 旋轉(zhuǎn)方向、 碼垛位置。解碼是算法實現(xiàn)的核心， 包括最低水平線查找、 板件位置確定和水平線更新。 解碼過程如下：

步驟1 按照編碼順序選擇未碼垛矩形板件為底板，根據(jù)底板的尺寸生成可碼垛空間和水平線集合，此時空間底邊為可碼垛最低水平線。

步驟2 選取最低水平線，按照當前解的編碼順序選擇未碼垛板件。如果選中的板件順序編碼符號為負號，則板件先旋轉(zhuǎn)90°； 如果板件的旋轉(zhuǎn)編碼為1，則板件再旋轉(zhuǎn)180°。根據(jù)板件尺寸以及碼垛后包裹質(zhì)量是否達到最大， 判斷該板件是否可以在最低水平線上碼垛。 在最低水平線上碼垛時可能出現(xiàn)的2種情況如下： 1）當前板件可以碼垛在此處， 即板件最小包絡矩形的寬度小于最低水平線的寬度， 并且碼垛后板件的高度和質(zhì)量不超出可碼垛空間的高度及包裹質(zhì)量的最大值。 當碼垛板件時， 根據(jù)當前板件與已碼垛板件的NFP判斷是否可以向下或向左移動， 計算可移動距離， 根據(jù)移動后板件的位置更新最低水平線， 直至所有板件碼垛完畢。 2）當前板件不可以碼垛在此處。 此時須將最低水平線位置的高度提升為左、 右鄰居中水平線高度的較小值， 從而更新水平線集合。

步驟3 重復步驟2，直至最低水平線不能再提升，表明當前板件無法碼垛在該層。包裹未滿時換層，即重新生成一個尺寸與底板相同的可碼垛空間與水平線集合。當包裹高度達到最大時，表示包裹已滿，須更換底板，碼垛下一個包裹，即執(zhí)行步驟1。

適配值函數(shù)是評價候選解的數(shù)學函數(shù)，通常與問題的目標函數(shù)有很強的關聯(lián)性。本文中以所用包裹的最少個數(shù)為目標函數(shù)，根據(jù)候選解解碼后碼垛方案所形成的包裹個數(shù)以及每個包裹的利用率，計算候選解的適配值，適配值函數(shù)為

f=∑ni=1U2in ，（3）

Ui=∑mik=1u2kmi ，（4）

式中： n為當前候選解經(jīng)過解碼后的碼垛方案形成的包裹個數(shù)； Ui為第i個包裹的空間利用率； mi為第i個包裹中板件的層數(shù)； uk為第i個包裹中第k層的空間利用率。根據(jù)式（3），碼垛方案形成的包裹個數(shù)越少，包裹利用率越高，則f值越大。根據(jù)式（4），碼垛方案形成的包裹每層的空間利用率越高，則包裹的空間利用率越高。

2.7 禁忌表設計

禁忌表使禁忌搜索具有記憶功能。禁忌表中2個主要指標是禁忌對象和禁忌長度，分別表示禁忌搜索的記憶對象和記憶強度。

禁忌對象為禁忌表中的變化元素。禁忌搜索有精準記憶、 屬性記憶2種記憶方式。在求解板式家具碼垛問題時，精準記憶每個板件的碼垛順序、 旋轉(zhuǎn)方向會消耗大量的內(nèi)存和時間，因此本文中采用屬性記憶的記憶方式，選取每次交換的板件序號為禁忌對象。

禁忌長度為禁忌表的記憶強度，通常用數(shù)字表示，表示一個禁忌對象在禁忌表中的最大任期。每次搜索、迭代時禁忌表中所有禁忌對象的任期發(fā)生變化。禁忌對象的任期為0表示忘記該禁忌對象。禁忌長度太大導致計算量和存儲量增加，禁忌長度太小可能導致循環(huán)搜索。禁忌長度l與問題規(guī)模p的關系為

l=p（p-1）/2 。（5）

禁忌表可以表示算法的記憶結構，記錄每次迭代生成的禁忌對象。禁忌表設計為p階方陣，如果在一次迭代過程中交換板件1、 2的碼垛順序得到的碼垛方案最優(yōu)且不滿足藐視準則，則在禁忌表的第1行、 第2列記錄數(shù)據(jù)為0，此時選取該候選解作為當前解，更新禁忌表。如果在搜索過程中出現(xiàn)優(yōu)于所記錄的最優(yōu)狀態(tài)的解，則解禁此禁忌對象，更新禁忌表。

3 算例測試

為了驗證本文算法的可行性，采用MATLAB 2020b軟件編程實現(xiàn)算法復現(xiàn)，并在中央處理器型號為英特爾酷睿^TM i7-10700、 運行頻率為2.90 GHz、內(nèi)存為16 GiB的計算機上，選取ESICUP提供的測試算例，算例來源于網(wǎng)站https：//www.euro-online.org/websites/esicup/data-sets/。

由于ESICUP無法提供按照底板約束用于板件打包的測試算例，因此本文中板件厚度、 密度以及包裹質(zhì)量最大值、 高度等參數(shù)均為自行設計。結合實際，設定板件厚度為標準板厚度18 mm，板件密度為木板密度，約為0.7 g/cm3，包裹質(zhì)量最大值分別為該訂單中所有板件總質(zhì)量的1/3、 1/4、 1/5，包裹高度最大值為140 mm。由于算例dagli、 daghe2中某些板件質(zhì)量大于設定的包裹質(zhì)量，因此dagli、 daghe2僅在包裹質(zhì)量最大值為板件總質(zhì)量的1/3的條件下測試。

由于文獻［6］中板件智能分包方法的研究對象為矩形板式家具，因此采用矩形包絡法將所有異形板件轉(zhuǎn)化為矩形板件。分別利用文獻［6］中的方法、 2.2節(jié)中初始解生成方法及本文算法生成板件打包的包裹個數(shù)。在禁忌搜索中通過鄰域結構生成的候選解個數(shù)為30，迭代次數(shù)為2 000。記錄每次生成的包裹個數(shù)，經(jīng)過10次測試，測試結果如表2所示。由表可知，相對于文獻［6］中的方法，利用初始解生成方法、 本文算法生成的板件打包的包裹個數(shù)分別減少35.69%、 38.46%，本文算法能有效地減少板件打包的包裹個數(shù)。

4 結語

本文中針對異形板式家具的碼垛問題，提出基于禁忌搜索的異形板式家具碼垛優(yōu)化算法，設計了表示訂單中所有板式家具碼垛順序與旋轉(zhuǎn)方向的編碼方法，以及實時監(jiān)測包裹質(zhì)量的初始解生成方法和結合NFP、最低水平線法的解碼方式。算例測試結果表明，本文算法能順利完成含異形板件的板式家具的打包任務，并有效減少包裹個數(shù)。

參考文獻：

［1］ 熊先青， 吳智慧. 大規(guī)模定制家具的發(fā)展現(xiàn)狀及應用技術［J］. 南京林業(yè)大學學報（自然科學版）， 2013， 37（4）： 156.

［2］ 李榮榮， 姚倩. 面向智能制造的板式定制家具柔性生產(chǎn)線設備配置［J］. 木材科學與技術， 202 35（2）： 23.

［3］ 熊先青， 袁瑩瑩， 潘雨婷， 等. 基于揉單生產(chǎn)的定制家居自動識別與智能分揀技術［J］. 林業(yè)工程學報， 2020， 5（6）： 162.

［4］ 陳炫銳， 陳慶新， 毛寧.板式家具企業(yè)的訂單組批問題研究［J］.工業(yè)工程， 2019， 22（2）： 96.

［5］ 汪金朋. 家具板材包裝算法的研究與應用［D］. 廣州： 廣東工業(yè)大學， 2019.

［6］ 羅斌， 關立俊. 板件智能分包的方法和裝置： 109795751B［P］. 2021-04-16.

［7］ AGRAWAL P K. Minimising trim loss in cutting rectangular blanks of a single size from a rectangular sheet using orthogonal guillotine cuts［J］. European Journal of Operational Research， 1993， 64（3）： 410.

［8］ JAKOBS S. On genetic algorithms for the packing of polygons［J］. European Journal of Operational Research， 1996， 88（1）： 165.

［9］ ADAMOWICZ M， ALBANO A. Nesting two-dimensional shapes inrectangularmodules［J］.Computer-AidedDesign，1976，8（1）：27.

［10］ BENNELLJA，DOWSLANDKA，DOWSLANDWB.The irregularcutting-stockproblem：anewprocedureforderiving the no-fit polygon［J］. Computers amp; Operations Research， 200 28（3）： 271.

［11］ 劉胡瑤， 何援軍. 基于重心NFP的二維不規(guī)則形狀排樣算法［J］. 中國機械工程， 2007， 18（6）： 723.

［12］ 梁利東， 鐘相強. 粒子群算法在不規(guī)則件排樣優(yōu)化中的應用［J］. 中國機械工程， 2010， 21（17）： 2050.

［13］ 韓偉， 張子成. 基于模擬退火的貫通約束不規(guī)則排樣［J］. 中國機械工程， 2016， 27（24）： 3326.

［14］ 閆嘉， 李林峰， 林毓培， 等. 基于改進免疫遺傳算法的汽車零件排樣［J］. 西南大學學報（自然科學版）， 2023， 45（5）： 204.

［15］ GLOVER F. Future paths for integer programming and links to artificial intelligence［J］. Computers amp; Operations Research， 1986， 13（5）： 533.

［16］ 毛良獻， 王品. 板材排樣中非擬合多邊形的構造實現(xiàn)方法［J］. 計算機系統(tǒng)應用， 2019， 28（9）： 168.

（責任編輯：李 娜）