求解矩形件下料問題的順序啟發(fā)式算法.pdf

1、計(jì)算機(jī)輔助排樣，又稱為CAN(Computer Aided Nesting)，是廣泛應(yīng)用的計(jì)算機(jī)輔助技術(shù)之一，用于指導(dǎo)各行業(yè)處理各種下料問題，以達(dá)到節(jié)約材料、降低產(chǎn)品成本的目的。下料問題存在于國(guó)民經(jīng)濟(jì)許多行業(yè)中，其中二維下料的應(yīng)用面較廣，而矩形件下料是二維下料的基礎(chǔ)，因此，對(duì)矩形件的優(yōu)化下料進(jìn)行研究是一個(gè)具有重大意義的課題。矩形件下料問題是指在板材足夠的情況下，確定一個(gè)排樣方案，用盡可能少的板材排出所需全部矩形毛坯。國(guó)內(nèi)外學(xué)者對(duì)該問題進(jìn)

2、行了深入和廣泛的研究，并提出了多種算法，如：線性規(guī)劃算法、模擬退火算法、遺傳算法等。本文采用一種啟發(fā)式算法對(duì)下料問題進(jìn)行求解。下料問題的解是一個(gè)排樣方案，該方案由一個(gè)或多個(gè)排樣方式組成，并指明每一個(gè)排樣方式對(duì)應(yīng)的原材料的使用次數(shù)。排樣方式必須是可行的，即排入板材的毛坯互不重疊且不超出板材邊界，使用合適的矩形排樣算法生成排樣方式對(duì)獲得好的排樣方案至關(guān)重要。排樣方式生成算法的主要功能是確定一個(gè)毛坯的集合以及該集合中的毛坯在板材中的排列方式。

3、排樣算法按毛坯在板材中出現(xiàn)的次數(shù)是否有限制分為有約束排樣算法和無約束排樣算法，無約束算法對(duì)毛坯的數(shù)量無約束，而有約束算法要求排入板材的各毛坯的數(shù)量不超過它允許出現(xiàn)的上限值。另外，按是否允許在同一張板材中排入多種尺寸的毛坯，把相應(yīng)的排樣方式稱為單一排樣方式和套裁排樣方式，二者相比較，套裁下料雖然切割工藝較為復(fù)雜，但能明顯的提高材料利用率。本文主要研究采用有約束排樣算法生成套裁排樣方式。本文采用一種改進(jìn)的順序啟發(fā)式算法確定一個(gè)最優(yōu)排樣方案，

4、主要工作是把求解排樣方式的擬人算法與基于價(jià)值修正的順序啟發(fā)式算法相結(jié)合，具體包括以下幾個(gè)方面：首先，基于最優(yōu)排樣方式模型，采用擬人算法按單位面積價(jià)值最大生成排樣方式。擬人算法在排入矩形毛坯時(shí)，總是使它占據(jù)一個(gè)角，并且盡量占穴。擬人算法由貪心算法和回溯算法組成，貪心算法每次都做穴度最大的占角動(dòng)作；在貪心算法的基礎(chǔ)上使用回溯的策略，板材中每排入一塊矩形，都運(yùn)用回溯法確定一個(gè)分值最高的占角動(dòng)作并做這個(gè)占角動(dòng)作。在擬人算法的基礎(chǔ)上，通過減少角的

5、個(gè)數(shù)以及增加占角動(dòng)作選擇策略對(duì)算法進(jìn)行改進(jìn)。其次，將用于一維排樣的順序價(jià)值修正法中的價(jià)值修正公式加以擴(kuò)展，運(yùn)用到矩形件下料問題中。排樣方案中的排樣方式順序生成，每調(diào)用擬人算法生成一個(gè)排樣方式，對(duì)方式中各毛坯在板材中排布情況進(jìn)行一次評(píng)價(jià)，根據(jù)評(píng)價(jià)結(jié)果再結(jié)合毛坯先前的信息來修改毛坯的價(jià)值，重復(fù)該過程多次，使得毛坯的價(jià)值不斷趨于合理。傳統(tǒng)的順序啟發(fā)式法生成排樣方案容易導(dǎo)致局部最優(yōu)的情況，將價(jià)值修正法融入其中，可有效地避免這種情況，使其達(dá)到全局