基于蟻群算法的矩形件優(yōu)化排樣問題研究.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è)具有重大意義的課題。所謂的矩形件下料問題是利用矩形原材料，尋找最優(yōu)的排樣布局下料出所需的全部矩形毛坯，使得原材料的浪費(fèi)最

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

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

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