不規(guī)則多邊形排料算法的研究與應(yīng)用.pdf

1、不規(guī)則多邊形排料問題是研究將多樣的待排物體合理排放在大區(qū)域內(nèi)的方法。研究排料的目的是最大化原材料利用率、提高經(jīng)濟(jì)效益。排料問題存在于諸多工業(yè)生產(chǎn)領(lǐng)域。由于排料問題是典型的NP完全問題，一直備受學(xué)術(shù)界和工業(yè)界關(guān)注。本文對(duì)排料算法的兩個(gè)關(guān)鍵步驟——待排多邊形定位算法和排料順序兩個(gè)方面進(jìn)行了深入研究。論文主要工作如下:
　　(1)快速掃描區(qū)間定位算法:掃描區(qū)間定位算法具有穩(wěn)定、易于實(shí)現(xiàn)等優(yōu)點(diǎn)，但存在速度慢的不足。本文算法首先通過基于最大

2、跨度比較法實(shí)現(xiàn)待排多邊形的快速定位;并進(jìn)一步改變平移矩陣表示法，將定位問題轉(zhuǎn)換為一維線性排序問題，進(jìn)一步提高效率。
　　(2)最大雙向契合度啟發(fā)式規(guī)則:針對(duì)BL、BLF定位算法采用的“最下、最左”啟發(fā)式規(guī)則會(huì)導(dǎo)致不合理排料結(jié)果的問題，提出“最大雙向契合度啟發(fā)式規(guī)則”，該啟發(fā)式規(guī)則綜合評(píng)價(jià)待排多邊形在水平、垂直兩個(gè)方向的契合度。論文給出“最大雙向契合度”的計(jì)算方法和基于該啟發(fā)式規(guī)則的定位算法。
　　(3)分組和遺傳算法相結(jié)合的