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

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

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

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

1 引言

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

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

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

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

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

2.1切斷式切割(Guillotine Cutting)

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

為本文所研究的情況。

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

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

2.3同時(shí)涉及一維下料和二維下料

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

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

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

本文所研究的二維下料問(wèn)題的數(shù)學(xué)模型及符號(hào)說(shuō)明如下。

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

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

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

3.1下料方案

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

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

3.2母板具有方向繼承性

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

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

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

Step 1:初始化解的集合;

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

Step 3:LOOP1(母板序列)

LOOP2(子板序列)

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

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

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

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

輸出問(wèn)題的解;

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

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

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

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

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

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

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

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

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

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

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

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

4 算法性能測(cè)試

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

本文利用計(jì)算機(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)行測(cè)試，利用其平均結(jié)果對(duì)算法性能進(jìn)行評(píng)價(jià)。母板長(zhǎng)度在4000mm到25000mm之間，寬度在1300mm到4800mm之間;子板長(zhǎng)度在3000mm到25000mm之間，寬度在900mm到4800mm之間;全部為均勻分布。

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

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