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

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

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

【學位級別】：碩士

【部分圖文】：

BLF算法路徑示意圖

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

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

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

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



本文編號：2990658