二維下料問題的啟發(fā)式算法

摘要對于二維下料問題，平均利用率最大化為目標(biāo)，建立數(shù)學(xué)模型，并在充分滿足切斷式切割方式的基礎(chǔ)上，定義了隨機(jī)決策方法和最適面積決策方法對下料方案進(jìn)行決策，基于優(yōu)先級和下料方案的不同組合，構(gòu)造了四種結(jié)構(gòu)相同的啟發(fā)式算法。數(shù)據(jù)測試結(jié)果表明，四種啟發(fā)式算法均可有效求解該問題，且采用面積優(yōu)先級規(guī)則和最適面積決策方法實現(xiàn)的啟發(fā)式算法效果最佳。

關(guān)鍵詞二維下料數(shù)學(xué)模型啟發(fā)式

中圖分類號:TB11文獻(xiàn)標(biāo)識碼:A

1 引言

實際生產(chǎn)中經(jīng)常需要對標(biāo)準(zhǔn)尺寸原材料進(jìn)行切割，以滿足加工需要，稱為下料問題(Cutting Stock Problem)。典型的二維下料問題可表述如下:將若干相同規(guī)格的矩形原材料切割成若干種規(guī)格的矩形零件，下料時零件的邊必須分別和原材料的邊平行，所有零件的厚度均與原材料一致。特別當(dāng)所有零件的寬度均與原材料相等，則問題稱為一維下料問題。目前通常主要涉及一些板材等的下料問題和紙張、布料等的排樣問題。相關(guān)數(shù)據(jù)統(tǒng)計，原材料成本占總生產(chǎn)成本的45%～60%，而下料方案的優(yōu)劣直接影響原材料的利用率，進(jìn)而影響原材料成本。

本文以原材料平均利用率最大化為目標(biāo)，有針對性的對二維下料問題展開研究。為方便說明，將原材料定義為母板，切割后材料定義為子板，該問題的幾何約束可概括為以下四個方面:其一，母板的長邊長度不可小于子板的長邊長度，同時，其短邊長度不可小于子板的短邊長度;其二，當(dāng)對母板進(jìn)行切割設(shè)計時，排布于同一塊母板上的所有子板，其平行于母板的長度方向的邊長之和不可超過母板長度方向的邊長，同時，其平行于母板的寬度方向的邊長之和不可超過母板寬度方向的邊長;其三，每塊母板下料得到的所有子板面積之和不得超過其自身面積，并且，排布于同一塊母板上的子板之間不允許存在面積上的交疊或覆蓋。在該問題研究過程中，不考慮邊緣切損量。

如果不考慮子板在母板上排列的幾何約束，把母板看成背包，把子板看成待裝包的物品，將母板面積作為背包容量，那么，該下料問題則可被歸結(jié)為一類特殊的多背包問題，在運(yùn)籌學(xué)和優(yōu)化領(lǐng)域，其為經(jīng)典的NP-hard問題。本文將探討采用啟發(fā)式算法和智能優(yōu)化算法對其進(jìn)行求解。

2 問題的數(shù)學(xué)模型描述

下面將對本文所研究的二維下料問題的特點進(jìn)行詳細(xì)的說明。

2.1切斷式切割(Guillotine Cutting)

切斷式切割，即指在母板上每次切割的軌跡均為一條邊到邊的連通直線，又稱為“Edge to Edge”切割，如圖1所示，(a)、(b)分別為非切斷式切割和切斷式切割的示意圖，圖中畫有斜線的部分表示切損廢板。切斷式切割

為本文所研究的情況。

2.2 母板和子板規(guī)格多樣化

根據(jù)實際情況，下料的母板規(guī)格可能不盡相同，生產(chǎn)中對于子板的需求也是如此。母板和子板的規(guī)格多樣性無疑增加了問題求解的難度。

2.3同時涉及一維下料和二維下料

為了增加原材料利用率，實際操作時通常會首先下料與母板寬度(或長度)相同的子板，也就是一維下料，在此基礎(chǔ)上，再針對剩余的母板進(jìn)行二維下料。事實上，一維下料問題可以說是二維下料問題的一個特例。

2.4不限定子板在母板上的排布方式

下料時要考慮子板在母板上的排布方式，鑒于母板和子板均為矩形，本文定義了如下兩種排布方式:若排布在母板上的子板的長(或?qū)?與母板自身的長度方向(或?qū)挾确较?平行，則稱子板為平行排布方式，如圖1中的1#和4#子板;若排布在母板上的子板的長(或?qū)?與母板自身的長度方向(或?qū)挾确较?垂直，則稱子板為垂直排布方式，如圖1 (a)中的2#和3#子板。本文所研究的下料問題僅涉及以上兩種排布方式。

本文所研究的二維下料問題的數(shù)學(xué)模型及符號說明如下。

其中，為決策變量，為1表示子板j取自母板，否則為0，、分別表示母板、子板總數(shù)，、分別表示母板、子板集合，、、分別表示母板的面積、長度、寬度，、、分別表示子板的面積、長度、寬度。數(shù)學(xué)模型中，式(1)為問題的目標(biāo)函數(shù)，即最大化母板的平均利用率;式(2)和(3)表達(dá)了下料過程的幾何約束。

3 問題的啟發(fā)式算法求解

首先對母板的下料方案和性質(zhì)作如下說明及定義:

3.1下料方案

為便于問題的求解，本文規(guī)定:子板均從母板的左下角切割得到，每次切割均為切斷式切割。如圖2所示，每從母板的左下角切割得到一塊子板，就會有兩塊新母板(包括面積為零的情況)產(chǎn)生。這里，本文要對母板切斷方式作以定義:若母板的首次切斷方向沿著其長度方向，則稱其為上下式切斷;若母板的首次切斷方向沿著其寬度方向，則稱其為左右式切斷。

下料時，子板在母板上的排布方式最多可能有平行和垂直兩種，而對于每一種排布方式，又存在兩種母板切斷方向。故從母板上切割一塊子板最多可能有四種方案。如圖3所示，本文將子板平行排布且母板左右式切斷的切割類型定義為“AI型”切割，將子板平行排布且母板上下式切斷的切割類型定義為“AII型”切割，將子板垂直排布且母板左右式切斷的切割類型定義為“BI型”切割，將子板垂直排布且母板上下式切斷的切割類型定義為“BII型”切割。

3.2母板具有方向繼承性

初始狀態(tài)下母板的長邊和短邊為其永久的長度方向和寬度方向，切割后產(chǎn)生的新母板具有繼承性，其平行于原母板長度方向和寬度方向的各邊分別為其長度方向和寬度方向。也就是說，在某些情況下，切割過程中重新產(chǎn)生的母板長度方向的邊長可能小于其寬度方向的邊長，如圖2中切割產(chǎn)生的新母板B。

前文已經(jīng)分析過無委托厚板匹配問題的特點及復(fù)雜性，其屬于NP-hard問題，即其不存在多項式時間求解算法，同時作為一類多目標(biāo)優(yōu)化的實際問題，開發(fā)指數(shù)級時間的求解算法未免顯得有些不切實際。事實上，對于這類問題通常推薦構(gòu)造快速有效的啟發(fā)式算法對其進(jìn)行求解。

根據(jù)問題的目標(biāo)及約束，并參考一些學(xué)者提出的切斷式切割問題的求解方法，本文構(gòu)造了求解該問題的啟發(fā)式算法。其基本思想為依次完成每塊母板的下料工作。基本方法為:以母板序列為基準(zhǔn)，依次掃描子板序列中的每個子板，并根據(jù)幾何約束判斷當(dāng)前子板從母板下料的合理性，若合理，則選擇一種切割方案，在當(dāng)前母板上采取切斷式切割獲得該子板，同時分別更新當(dāng)前的母板和子板序列;由初始母板切割得到的新母板，將繼續(xù)進(jìn)行下料;依上述思想及方法反復(fù)針對匹配對象序列進(jìn)行操作，直到當(dāng)前母板序列為空時，整個算法過程結(jié)束。算法具體步驟如下:

Step 1:初始化解的集合;

Step 2:按照優(yōu)先級，將母板序列和子板序列重新排序;

Step 3:LOOP1(母板序列)

LOOP2(子板序列)

判斷該子板從當(dāng)前母板下料的合理性;

直到找到可從當(dāng)前母板下料的子板或子板序列掃描結(jié)束;

若找到可從當(dāng)前母板下料的子板，則轉(zhuǎn)至Step 4，否則，轉(zhuǎn)至Step 6;

直到滿足算法的終止準(zhǔn)則;

輸出問題的解;

Step 4:將當(dāng)前合理下料的母板與子板記錄到解的節(jié)點集合中;

Step 5:決策切割方案后，對母板進(jìn)行切割;

Step 6:更新匹配對象序列，轉(zhuǎn)至Step 3。

利用啟發(fā)式求解問題過程中，存在很多關(guān)鍵的決策環(huán)節(jié)。

(1)優(yōu)先級。很明顯，序列的順序直接反映了母板以及子板在算法執(zhí)行過程中的優(yōu)先級，也嚴(yán)重影響解的質(zhì)量。若算法對母板和子板序列的掃描起始于首單元而終止于尾單元，則越是靠近首單元的母板或子板，其優(yōu)先級也就越高。對于一塊母板來說，其優(yōu)先級越高，也就意味著其選擇子板的優(yōu)先權(quán)越高，同時其備選子板集合也越大。實際人工下料中，往往優(yōu)先考慮一維下料。據(jù)此，本文設(shè)計了兩種優(yōu)先級:一是面積優(yōu)先級，即將母板序列和子板序列按照面積非減和非增的順序進(jìn)行排序;二是寬度優(yōu)先級，即將母板序列和子板序列按照寬度非減和非增的順序進(jìn)行排序。

(2)下料合理性判斷方法。根據(jù)幾何約束，主要從寬度和長度兩方面來判斷母板與子板匹配的合理性，即子板必須能夠從母板上切割得到，也就是說，子板的長邊長度不得超過母板的長邊長度，同時子板的短邊長度不得超過母板的短邊長度。

(3)下料方案決策方法。如圖3所示，下料包括“AI型”、“AII型”、“BI型”和“BII型”四種方案。本文定義了兩種決策方法:隨機(jī)決策方法和最適面積決策方法。

隨機(jī)決策方法。決策下料方案時，隨機(jī)地從四種方案中選擇一種。這種方法不僅可以擴(kuò)大解的搜索空間，而且比較便于實現(xiàn)。

最適面積決策方法。首先，以每種母板下料方案中產(chǎn)生的兩塊新母板(包括面積為零的母板)為基準(zhǔn)，分別從子板序列中挑選可從其上下料的最大面積子板，選中的子板的面積則記為該新母板的最適面積，當(dāng)然，兩塊新母板不能重復(fù)選擇同一塊子板，如果新母板的面積為零，則將其最適面積記為零;然后，分別計算每種母板下料方案中兩塊新母板的最適面積之和;最后，按新母板的最適面積之和最大的下料方案進(jìn)行決策。

(4)序列更新方法。對當(dāng)前子板序列進(jìn)行掃描的過程中，若找到適合下料的子板，則依據(jù)下料方案進(jìn)行切割，并更新當(dāng)前的母板和子板序列。更新過程主要是將已下料母板和子板信息分別從序列中刪除，同時將下料后獲得的新母板(面積不為零的)按優(yōu)先級插入到序列中。

若對現(xiàn)有的全部子板掃描過后，仍未找到適合當(dāng)前母板下料的子板，此時更新操作即是將當(dāng)前母板信息從序列中刪除。

(5)算法終止準(zhǔn)則。本文將母板序列或子板序列為空作為整個啟發(fā)式算法結(jié)束的充分必要條件。

4 算法性能測試

如前所述，啟發(fā)式算法求解二維下料問題的關(guān)鍵在于優(yōu)先級的確定和下料方案的決策，本文分別設(shè)計了兩種優(yōu)先級規(guī)則和兩種下料方案，兩兩組合后形成了四個結(jié)構(gòu)相同的啟發(fā)式算法。下面將對四種啟發(fā)式算法進(jìn)行實驗并對比其性能。

本文利用計算機(jī)隨機(jī)產(chǎn)生了涉及8種規(guī)模的模擬數(shù)據(jù)，即母板數(shù)分別為10、20、50、80、100、200、300、500的情況，每種規(guī)模產(chǎn)生6組數(shù)據(jù)進(jìn)行測試，利用其平均結(jié)果對算法性能進(jìn)行評價。母板長度在4000mm到25000mm之間，寬度在1300mm到4800mm之間;子板長度在3000mm到25000mm之間，寬度在900mm到4800mm之間;全部為均勻分布。

算法均在Visual C++ 6.0環(huán)境下采用C++語言編程實現(xiàn)，并在具有3.0G主頻的Pentium(R)4系列CPU、1G物理內(nèi)存、Windows XP操作系統(tǒng)的計算機(jī)上進(jìn)行了性能測試。

表1為算法平均測試結(jié)果，其中，H1表示采用寬度優(yōu)先級規(guī)則和隨機(jī)決策方法實現(xiàn)的啟發(fā)式算法，H2表示采用寬度優(yōu)先級規(guī)則和最適面積決策方法實現(xiàn)的啟發(fā)式算法，H3表示采用面積優(yōu)先級規(guī)則和隨機(jī)決策方法實現(xiàn)的啟發(fā)式算法，H4表示采用面積優(yōu)先級規(guī)則和最適面積決策方法實現(xiàn)的啟發(fā)式算法。