二維一刀切裝箱問題,指在給定無限多個(gè)固定大小的二維板材（箱子）上,將不同規(guī)格的待排矩形件,在保證彼此不重疊的前提下,逐個(gè)擺放至二維箱子內(nèi),使得占用箱子的個(gè)數(shù)最少,并且在切割時(shí)滿足一刀切條件約束（此處的一刀切約束是指切割時(shí)刀口走線不能彎曲,必須從一條邊經(jīng)直線切割到對(duì)邊）。二維一刀切裝箱問題隸屬于組合優(yōu)化問題中的二維布局問題,最典型的應(yīng)用是在家具生產(chǎn)過程中玻璃切割的布局優(yōu)化。從計(jì)算復(fù)雜性理論的角度來看,該問題屬于具有最高計(jì)算復(fù)雜性的NP完全問題,并涉及到計(jì)算幾何、運(yùn)籌學(xué)等多學(xué)科知識(shí),具有較高的理論研究和實(shí)用價(jià)值。本文對(duì)二維一刀切裝箱過程中的相關(guān)問題進(jìn)行了深入研究,主要的研究工作如下:1、首次給出G-區(qū)域和GR-區(qū)域的概念,用以定量描述排樣過程中可被一刀切的區(qū)域所需要滿足的相關(guān)條件。2、提出了順時(shí)針切割線組以及逆時(shí)針切割線組等定義。在使用三叉排樣樹對(duì)布局結(jié)構(gòu)進(jìn)行描述的基礎(chǔ)上,相繼構(gòu)造了G-區(qū)域的判斷算法、GR-區(qū)域的延展算法及全局更新算法等子算法。3、在上述工作的基礎(chǔ)上,提出了二維一刀切裝箱問題的啟發(fā)式算法,并對(duì)其進(jìn)行了數(shù)值實(shí)驗(yàn)和結(jié)果分析。4、利用所提算法,編制了可被實(shí)用的排樣軟件,并在其中... 

【文章來源】：哈爾濱理工大學(xué)黑龍江省

【文章頁(yè)數(shù)】：46 頁(yè)

【學(xué)位級(jí)別】：碩士

【部分圖文】：

BLF算法路徑示意圖

哈爾濱理工大學(xué)理學(xué)碩士學(xué)位論文13題研究的相關(guān)圖形表示采用如下坐標(biāo)系統(tǒng)，如圖3-1所示，坐標(biāo)原點(diǎn)O點(diǎn)為左上角頂點(diǎn)，x軸正方向向右延伸，y軸正方向向下延伸。圖3-1坐標(biāo)系統(tǒng)Fig.3-1Thecoordinatesystem3.3概念及算法3.3.1相關(guān)概念及結(jié)論定義3.1G-區(qū)域給定二維裝箱問題中的任意矩形空白區(qū)域R，若R可經(jīng)一組有序的且滿足一刀切的切割線而獲得，則稱該區(qū)域?yàn)镚-區(qū)域。顯然，對(duì)任意一個(gè)G-區(qū)域而言，對(duì)于接下來的一些新的待排項(xiàng)，是一個(gè)可能的排放區(qū)域。這里我們約定，如果待排項(xiàng)I可以被放入至某個(gè)G-區(qū)域R內(nèi)，則該項(xiàng)總是被擺放至R的左上角，即使得I的左上角頂點(diǎn)與R的左上角頂點(diǎn)重合。不失一般性，假設(shè)RIheightheight且RIwidthwidth，則擺放I后，由R和I可獲得兩個(gè)可排空白區(qū)域1R和2R（21RR），如圖3-2所示。圖3-2R1和R2的生成示意圖Fig.3-2GenerationofR1andR2

哈爾濱理工大學(xué)理學(xué)碩士學(xué)位論文13題研究的相關(guān)圖形表示采用如下坐標(biāo)系統(tǒng)，如圖3-1所示，坐標(biāo)原點(diǎn)O點(diǎn)為左上角頂點(diǎn)，x軸正方向向右延伸，y軸正方向向下延伸。圖3-1坐標(biāo)系統(tǒng)Fig.3-1Thecoordinatesystem3.3概念及算法3.3.1相關(guān)概念及結(jié)論定義3.1G-區(qū)域給定二維裝箱問題中的任意矩形空白區(qū)域R，若R可經(jīng)一組有序的且滿足一刀切的切割線而獲得，則稱該區(qū)域?yàn)镚-區(qū)域。顯然，對(duì)任意一個(gè)G-區(qū)域而言，對(duì)于接下來的一些新的待排項(xiàng)，是一個(gè)可能的排放區(qū)域。這里我們約定，如果待排項(xiàng)I可以被放入至某個(gè)G-區(qū)域R內(nèi)，則該項(xiàng)總是被擺放至R的左上角，即使得I的左上角頂點(diǎn)與R的左上角頂點(diǎn)重合。不失一般性，假設(shè)RIheightheight且RIwidthwidth，則擺放I后，由R和I可獲得兩個(gè)可排空白區(qū)域1R和2R（21RR），如圖3-2所示。圖3-2R1和R2的生成示意圖Fig.3-2GenerationofR1andR2

【參考文獻(xiàn)】：
期刊論文
[1]基于勻質(zhì)塊排樣方式的多尺寸板材下料算法[J]. 向文欣,王宏旭,潘立武.  鍛壓技術(shù). 2019(07)
[2]矩形件簡(jiǎn)單塊占角排樣方式的動(dòng)態(tài)規(guī)劃[J]. 潘衛(wèi)平,張瑞友.  中國(guó)圖象圖形學(xué)報(bào). 2019(06)
[3]矩形件套裁排樣的一種優(yōu)化解法[J]. 扈少華,張淋江,潘立武,管衛(wèi)利.  機(jī)械設(shè)計(jì)與制造. 2018(06)
[4]基于矩形拼接的“一刀切”矩形排樣優(yōu)化設(shè)計(jì)[J]. 張子成.  現(xiàn)代制造工程. 2018(04)
[5]基于改進(jìn)離散螢火蟲算法的二維排樣問題優(yōu)化[J]. 吳堂福,楊建軍,劉志浩,姜曉瑜.  中國(guó)科技論文. 2018(02)
[6]遞歸算法在單一矩形毛坯無約束最優(yōu)排樣中的應(yīng)用[J]. 李海生.  重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)). 2017(09)
[7]約束二維排樣問題的一種求解算法[J]. 朱強(qiáng),薛峰,鄭仕勇,管衛(wèi)利.  鍛壓技術(shù). 2016(09)
[8]單規(guī)格一刀切矩形排樣問題的啟發(fā)式搜索算法[J]. 王磊,劉強(qiáng),陳新.  軟件學(xué)報(bào). 2017(07)
[9]二維剪切排樣的束搜索啟發(fā)式算法[J]. 陳秋蓮,王成棟.  計(jì)算機(jī)工程與應(yīng)用. 2017(09)
[10]基于勻質(zhì)條帶的矩形件最優(yōu)三塊布局算法[J]. 潘衛(wèi)平,陳秋蓮,崔耀東,陳怡丹.  圖學(xué)學(xué)報(bào). 2015(01)

碩士論文
[1]二維非規(guī)則帶排樣問題研究[D]. 趙曉龍.哈爾濱理工大學(xué) 2019
[2]應(yīng)用精確兩階段排樣圖的板材下料算法[D]. 王嚴(yán)欣.廣西大學(xué) 2016
[3]滿足“一刀切”約束的卷型材矩形件排樣方法研究[D]. 何霖.廣東工業(yè)大學(xué) 2014



本文編號(hào)：2990658