本文選題：裝箱問題 + 啟發(fā)式算法��； 參考：《廈門大學(xué)》2007年碩士論文

【摘要】： 裝箱問題是一個經(jīng)典的組合優(yōu)化問題。簡單地說,裝箱問題就是將若干不同尺寸的物體互不重疊地放入有一定容量的箱子中以達(dá)到某種最佳目標(biāo)。裝箱問題被廣泛應(yīng)用于計算機(jī)科學(xué)領(lǐng)域和工業(yè)領(lǐng)域,多處理器任務(wù)調(diào)度、內(nèi)存管理、貨物裝載以及原料切割等都是裝箱問題在實際應(yīng)用中的具體體現(xiàn)。因此,研究裝箱問題具有重要的理論意義和應(yīng)用價值。 從二十世紀(jì)七十年代起,學(xué)術(shù)界就對裝箱問題進(jìn)行了廣泛而深入的研究,但是由于裝箱問題是NP難的,具有高度復(fù)雜性,用一般的數(shù)學(xué)方法很難求解。因此,在最近的幾十年,啟發(fā)式算法被廣泛應(yīng)用于裝箱問題的求解中。 本文首先對裝箱問題的研究現(xiàn)狀、問題分類及求解算法進(jìn)行了綜述和分析,然后重點對二維矩形裝箱問題進(jìn)行研究。在總結(jié)和概括了當(dāng)前主要的裝箱優(yōu)化算法的基礎(chǔ)上,對已有的HR和PH算法進(jìn)行改進(jìn),提出了兩種新的算法:基于遞歸思想的模擬退火算法(SA+HR)和基于動態(tài)分層的最小浪費(fèi)優(yōu)先啟發(fā)式算法(SA+LWFBDL)。SA+HR算法主要是引進(jìn)了模擬退火算法對HR算法進(jìn)行改進(jìn),將HR算法得到的值作為評價解的標(biāo)準(zhǔn),將任意交換兩個物體位置得到的所有物體序列的集合作為鄰域解空間,從而搜索出更好的物體序列來改善解的質(zhì)量。而SA+LWFBDL算法在保留PH算法動態(tài)分層的基礎(chǔ)上,改進(jìn)了物體的放置策略,裝物體時考慮所有的可行位置,優(yōu)先選擇放置后浪費(fèi)面積最小的物體和可行位置的組合,對于浪費(fèi)面積相同的多種組合,按照適合度進(jìn)行選擇,最后我們采用模擬退火算法來改善物體的裝箱順序從而得到更好的解。 實驗結(jié)果表明,我們提出的兩種算法比原有的算法HR和PH有很大的改進(jìn)。而且SA+HR的求解質(zhì)量優(yōu)于著名的算法BF、SA+BLF和GA+BLF,而SA+LWFBDL算法經(jīng)過多次運(yùn)行對大多數(shù)實例都可以得到最優(yōu)解,可以與目前優(yōu)秀的算法SPGAL、HRBB和HRP相競爭。
[Abstract]:The packing problem is a classical combinatorial optimization problem. To put it simply, the problem of packing is to put several objects of different sizes into boxes of a certain capacity without overlapping in order to achieve a certain optimal goal. Packing problem is widely used in computer science and industry. Multiprocessor task scheduling, memory management, cargo loading and raw material cutting are the concrete embodiment of packing problem in practical application. Therefore, the study of packing problem has important theoretical significance and application value. Since the 1970s, the academic circle has carried on the extensive and thorough research to the packing problem, but because the packing problem is NP-hard, has the high complexity, it is difficult to solve with the general mathematics method. Therefore, in recent decades, heuristic algorithms have been widely used to solve packing problems. In this paper, the research status, classification and solving algorithm of the packing problem are reviewed and analyzed firstly, and then the two-dimensional rectangular packing problem is studied. On the basis of summing up and summarizing the main packing optimization algorithms, the existing HR and PH algorithms are improved. Two new algorithms are proposed: simulated annealing algorithm (SA) based on recursion and minimum waste priority heuristic algorithm (SA LWFBDL).SA HR) based on dynamic layering, which mainly introduces simulated annealing algorithm to improve HR algorithm. The values obtained by the HR algorithm are taken as the criteria for evaluating the solution, and the set of all the sequences of objects obtained by arbitrarily exchanging the positions of two objects is taken as the neighborhood solution space, thus a better sequence of objects is searched to improve the quality of the solution. On the basis of preserving the dynamic layering of PH algorithm, SA LWFBDL algorithm improves the placement strategy of objects, considers all feasible positions when loading objects, and preferentially selects the combination of the least wasted area objects and feasible positions after placement. For a variety of combinations with the same wasted area, we choose according to the degree of fitness. At last, we use simulated annealing algorithm to improve the packing order of objects and get a better solution. The experimental results show that the proposed two algorithms are much better than the original algorithms HR and PH. Moreover, the solution quality of SA HR is better than that of the famous algorithms BFS SA BLF and GA BLF, and the SA LWFBDL algorithm can obtain the optimal solution for most instances after several runs, and can compete with the current excellent algorithms SPGALHRBB and HRP.
【學(xué)位授予單位】：廈門大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2007
【分類號】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陳斢;;考慮柔性維修的job-shop調(diào)度問題及啟發(fā)式算法[J];科技創(chuàng)新導(dǎo)報;2011年18期

2 陳萍;黃厚寬;董興業(yè);;求解多車型車輛路徑問題的變鄰域搜索算法[J];系統(tǒng)仿真學(xué)報;2011年09期

3 杜立寧;張德珍;陳世峰;;蟻群算法求解復(fù)雜集裝箱裝載問題[J];計算機(jī)應(yīng)用;2011年08期

4 肖平;徐成;楊志邦;劉彥;;基于改進(jìn)模擬退火算法的軟硬件劃分[J];計算機(jī)應(yīng)用;2011年07期

5 李剛;劉景發(fā);;基于禁忌搜索的啟發(fā)式算法求解帶平衡約束的圓形裝填問題[J];中國科學(xué):信息科學(xué);2011年09期

6 周桂清;嚴(yán)偉;;基于雙40英尺集裝箱裝卸系統(tǒng)的自動化碼頭堆場計劃[J];上海海事大學(xué)學(xué)報;2011年03期

7 桂云苗;龔本剛;程幼明;;一種求解航空貨代拼箱問題的啟發(fā)式算法[J];計算機(jī)應(yīng)用研究;2011年07期

8 陳冬宇;王磊;張漢鵬;;基于信息流的產(chǎn)品開發(fā)項目流程優(yōu)化研究[J];計算機(jī)應(yīng)用研究;2011年07期

9 楊杰;;MF-TDMA體制下載波信道管理[J];通信技術(shù);2011年07期

10 李俊亭;王潤孝;楊云濤;;關(guān)鍵鏈多項目整體進(jìn)度優(yōu)化[J];計算機(jī)集成制造系統(tǒng);2011年08期

相關(guān)會議論文 前10條

1 段雪超;李方偉;;IP網(wǎng)絡(luò)服務(wù)質(zhì)量路由算法研究[A];現(xiàn)代通信理論與信號處理進(jìn)展——2003年通信理論與信號處理年會論文集[C];2003年

2 葛華;;交通分流的一種啟發(fā)式平衡算法[A];第一屆中國智能交通年會論文集[C];2005年

3 王秀英;鄭秉霖;;煉鋼—連鑄生產(chǎn)調(diào)度的啟發(fā)式算法[A];1998中國控制與決策學(xué)術(shù)年會論文集[C];1998年

4 陳鋒;邢文訓(xùn);;在線塔狀裝箱問題(英文)[A];中國運(yùn)籌學(xué)會第六屆學(xué)術(shù)交流會論文集（上卷）[C];2000年

5 高麟;王成堯;汪定偉;殷秩松;王書寧;;某電器生產(chǎn)廠的平行機(jī)臺生產(chǎn)調(diào)度系統(tǒng)[A];1998中國控制與決策學(xué)術(shù)年會論文集[C];1998年

6 李華雄;周獻(xiàn)中;;基于0-1分辨矩陣的啟發(fā)式屬性約簡[A];2009年中國智能自動化會議論文集（第六分冊）[中南大學(xué)學(xué)報（增刊）][C];2009年

7 張廣躍;汪澤焱;張申如;;滿足延遲約束的鏈路分離路徑算法[A];2007北京地區(qū)高校研究生學(xué)術(shù)交流會通信與信息技術(shù)會議論文集（下冊）[C];2008年

8 劉長有;薛原;;雙伺服機(jī)分層旋轉(zhuǎn)貨架揀選路徑優(yōu)化的改進(jìn)算法[A];2003中國控制與決策學(xué)術(shù)年會論文集[C];2003年

9 劉長有;薛原;石青輝;;固定貨架中大規(guī)模揀選任務(wù)的揀選路徑優(yōu)化[A];2003中國控制與決策學(xué)術(shù)年會論文集[C];2003年

10 施寒瀟;;基于改進(jìn)型蟻群算法求解0／1背包問題[A];2005中國控制與決策學(xué)術(shù)年會論文集（上）[C];2005年

相關(guān)重要報紙文章 前9條

1 清華大學(xué)計算機(jī)科學(xué)與技術(shù)系 經(jīng)彤 洪先龍 許靜宇;IC布線理論與關(guān)鍵技術(shù)[N];計算機(jī)世界;2005年

2 費(fèi)宗蓮;UTM引領(lǐng)安全潮流[N];計算機(jī)世界;2005年

3 記者　 李含;在科學(xué)的殿堂中追求完美[N];新清華;2006年

4 易明;供應(yīng)鏈運(yùn)營和績效診斷[N];現(xiàn)代物流報;2006年

5 李剛;不能犧牲性能[N];中國計算機(jī)報;2004年

6 謝德華;物流：第三利潤源泉[N];中華讀書報;2001年

7 本報記者 黃智軍;Web應(yīng)用呼喚新型安全系統(tǒng)[N];計算機(jī)世界;2009年

8 ;網(wǎng)絡(luò)世界2009年度Web安全創(chuàng)新產(chǎn)品獎[N];網(wǎng)絡(luò)世界;2009年

9 王小龍;進(jìn)化算法可解決風(fēng)電機(jī)選址問題[N];科技日報;2011年

相關(guān)博士學(xué)位論文 前10條

1 賴向京;原子團(tuán)簇結(jié)構(gòu)預(yù)測的現(xiàn)實途徑—高性能啟發(fā)式算法[D];華中科技大學(xué);2012年

2 余國松;與裝箱相關(guān)的幾類問題[D];浙江大學(xué);2009年

3 鄧冠龍;基于元啟發(fā)式算法的調(diào)度問題若干研究[D];華東理工大學(xué);2012年

4 宋繼偉;軋輥熱處理過程中若干調(diào)度問題的啟發(fā)式算法研究[D];東北大學(xué);2010年

5 沈灝;與Due Date相關(guān)的排序問題研究[D];浙江大學(xué);2002年

6 衛(wèi)家駿;集裝箱船智能配載研究[D];大連海事大學(xué);2012年

7 馬云峰;網(wǎng)絡(luò)選址中基于時間滿意的覆蓋問題研究[D];華中科技大學(xué);2005年

8 楊s，

本文編號：1976538