基于蟻群算法的矩形件優(yōu)化排樣問題研究.pdf

1、計算機輔助排樣，又稱為CAN(Computer Aided Nesting)，是廣泛應(yīng)用的計算機輔助技術(shù)之一，用于指導(dǎo)各行業(yè)處理各種下料問題，以達(dá)到節(jié)約材料、降低產(chǎn)品成本的目的。
　　 下料問題存在于國民經(jīng)濟的許多行業(yè)中，其中二維下料應(yīng)用廣泛，而矩形件下料是二維下料的基礎(chǔ)，因此，對矩形件的優(yōu)化下料進行研究是一個具有重大意義的課題。所謂的矩形件下料問題是利用矩形原材料，尋找最優(yōu)的排樣布局下料出所需的全部矩形毛坯，使得原材料的浪費最

2、少的問題。矩形件排樣問題按原材料的不同分為兩種：原材料矩形板材具有確定的尺寸，需要用最少的板材下料出所需的矩形毛坯的裝箱問題(Rectangular Bin Packing Problem)和原材料板材只有確定的寬度而長度無限，需要用最短的板材下料出所需矩形毛坯的矩形件帶排樣問題(Rectangular Strip Packing Problem)。國內(nèi)外學(xué)者對該問題進行了深入和廣泛的研究，并提出了很多算法，如：線性規(guī)劃方法、遺傳算法、

3、模擬退火算法等。
　　 近年來，由于蟻群算法的正反饋并行自催化機制，和具有較強的魯棒性等優(yōu)點，使其逐漸成為一種應(yīng)用廣泛的元啟發(fā)式算法。本文針對矩形件排樣中的帶排樣問題這個NP難問題，提出采用蟻群算法進行求解。主要研究包括以下內(nèi)容：
　　 (1)針對該問題提出一種新的排樣方案生成算法-基于長度方向最小浪費準(zhǔn)則法。該方法可以有效的提高該類問題的利用率。
　　 (2)建立該問題的蟻群算法求解模型，給出合適的構(gòu)建圖定義，

4、信息素和啟發(fā)式信息以及路徑構(gòu)建和信息素更新規(guī)則，設(shè)計出合適的算法流程。
　　 (3)分析蟻群算法中不同的參數(shù)取值對問題求解的影響，得出合適的參數(shù)來求解該問題。
　　 (4)在采用蟻群算法對矩形件帶排樣問題的處理基礎(chǔ)上，對算法進行補充，使其能夠處理矩形件裝箱問題。
　　 (5)最后，設(shè)計開發(fā)矩形件下料系統(tǒng)。通過對大量的實驗進行測試，并將實驗結(jié)果與其它中文文獻(xiàn)以及商業(yè)軟件的計算結(jié)果進行比較和分析，結(jié)果表明，本文算法具