包絡(luò)體算法求解三維矩形布局問題

《包絡(luò)體算法求解三維矩形布局問題》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學術(shù)論文-天天文庫。

1、包絡(luò)體算法求解三維矩形布局問題　　摘要：對于三維布局問題，本文提出了一種體積遞減的定序規(guī)則與包絡(luò)體相結(jié)合的算法，并對此進行了研究。最后通過對實驗數(shù)據(jù)的分析，得出包絡(luò)體算法在取得相對好的利用率的同時大大提高了計算效率?！　￡P(guān)鍵詞：三維布局；包絡(luò)體算法；體積遞減　　中圖分類號：G712文獻標識碼：B文章編號：1002-7661（2015）23-046-01　　三維布局問題，布局規(guī)模較大求解更復(fù)雜，傳統(tǒng)的確定性優(yōu)化方法求解起來較困難，因而很多學者采用啟發(fā)式算法。啟發(fā)式算法在布局問題中主要涉及三個方面：待布矩形塊布局的優(yōu)先順序、擺放位置以及放置方向?！　埖赂坏萚1]提出了

2、擬人啟發(fā)式算法與模擬退火算法相結(jié)合的組合啟發(fā)式算法。他們[2]還提出了一種高效求解三維裝箱問題的多層啟發(fā)式搜索算法。何琨等[3]提出了穴度計算公式，并根據(jù)最大穴度優(yōu)先放入為原則對矩形塊進行布局，使裝入容器的矩形塊盡量緊湊，從而提高容器利用率。YaohuaHe等[4]提出了一種全局搜索的包絡(luò)體法，利用兩個評價指標來實現(xiàn)待布局矩形塊的定位與定序，并采用遺傳算法對矩形塊的布局次序進行優(yōu)化?！　”疚慕梃b了YaohuaHe[4]提出的包絡(luò)體概念，提出了一種將體積遞減定序規(guī)則與包絡(luò)體相結(jié)合的算法，并對此進行了研究?！　∫?、相關(guān)定義4　　包絡(luò)體是指包含所有已布入的矩形塊和正在布局

3、的矩形塊的最小矩形?！　∈Ｓ囿w積是指包絡(luò)體體積與已布入容器中所有矩形塊體積之和的差?！　】刹贾命c是指可以放置待布局矩形塊的點。本文以原點為起始布置點，布入一個矩形塊后，可布置點變?yōu)?個，在空間坐標系中分別沿X、Y、Z軸方向，對應(yīng)矩形塊的左下前角點，右下后角點，左上后角點。當容器布入n個矩形塊時，可布置點的個數(shù)為，但是這些可布置點能否全部進行下一次布局還需進一步討論，下文將詳細說明。　　放置方向是指待布局矩形塊完成一次布局后，在布局空間的實際擺放方向，對一個長度、寬度、高度都不相等的矩形塊來說，其在布局空間有六種放置方向?！　《⒓s束條件　　約束條件是對布局約束中的目

4、標約束和位置約束進行說明?！　”疚牡哪繕思s束就是滿足一定約束條件下，使得布局間隙控制在能夠允許的范圍之內(nèi)，放入容器中的矩形塊的體積之和最大，以提高容器的利用率。位置約束是指待布局矩形塊與容器和已布局矩形塊的位置約束。即待布局矩形塊在布局過程中首先需滿足該矩形塊不得超出布局容器的邊界，并且待布局矩形塊布入容器后不得與已布入的矩形塊之間發(fā)生重疊?！　∪?、體積遞減定序的包絡(luò)體法4　　本文采用了包絡(luò)體規(guī)則的定位規(guī)則結(jié)合待布局矩形塊體積遞減的靜態(tài)定序進行研究。將待布局矩形塊按體積大小遞減的順序排列，選擇包絡(luò)體體積最小的位置作為待布局矩形塊的放置位置，這樣可以使得已布入容器的矩

5、形塊相互之間擺布地比較緊湊，容器的剩余體積較大，有利于下一次布局?！　∷摹嶒灁?shù)據(jù)分析　　本文采用編程軟件VC++6.0實現(xiàn)上述算法，采用的算例為OR-Library算例中的OR9算例。OR-Library算例庫是由Beasley[5]在1990年提出的，而OR9算例是其中一組無約束的算例，有47個例子。　　OR9算例的特點是，待布局矩形塊的個數(shù)和種類數(shù)都是不固定的，個數(shù)在47～118之間，種類在2～4。最終本文的計算結(jié)果可以獲得100%利用率的算例有6個，利用率低于80%的只有7個，平均利用率達到88.88%；改進后的算法獲得100%利用率的有7個，且低于80%的

6、結(jié)果只有2個，平均利用率達到了90.49%，比改進前提高了1.61%?！　”疚挠嬎愕臅r間與文獻[6]的MFB算法的計算時間相比，都比MFB算法在k取1-3時的平均利用率高。該文獻在k=7時取得最好解91.00%，用時205秒，本算法與之相比平均利用率低了0.51%，但是本文算法只用了1.97秒，大大減少了計算時間，提高了計算效率?！　∥濉⒔Y(jié)論　　本文提出了體積遞減定序與包絡(luò)體結(jié)合的算法。通過對算例計算的結(jié)果并與文獻所得結(jié)果相比較可以看出，本算法的最大特點是計算效率較高。本算法所得結(jié)果與當前文獻中最好結(jié)果相比，還存在著一定的差距，說明本文算法還有待進一步改善?！　⒖?/p>

7、文獻：　　[1]張德富，魏麗軍，陳青山，陳火旺.4三維裝箱問題的組合啟發(fā)式算法[J].軟件學報，2007，18（9）：2083-2089.　　[2]張德富彭煜張麗麗.求解三維裝箱問題的多層啟發(fā)式搜索算法[J].計算機學報，2012，35（12）：2553-2561.　　[3]何琨，黃文奇.求解三維矩形布局的最大穴度算法[J].華中科技大學學報（自然科學版），2008，36（3）：92-94.　　[4]YaohuaHe，YongWu，RobertdeSouza.Aglobalsearchframeworkforpracticalthree-dimensionalp