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

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

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

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

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

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