基于遺傳和遞歸的裝箱算法研究.pdf

1、裝箱問(wèn)題就是將不同尺寸的物品擺放入有一定容量的容器中，以獲得某種最佳的效益。裝箱問(wèn)題廣泛地用于機(jī)械生產(chǎn)和交通運(yùn)輸?shù)刃袠I(yè)當(dāng)中。對(duì)該問(wèn)題求解方法的研究無(wú)論是在理論上，還是在實(shí)踐中都具有一定的意義。裝箱問(wèn)題屬于組合最優(yōu)化問(wèn)題和NP完全問(wèn)題，具有高度復(fù)雜性，用一般的數(shù)學(xué)方法很難求解，目前研究得最多的是用啟發(fā)式方法解決裝箱問(wèn)題。 本文為求解二維裝箱問(wèn)題提出了GA+HR、GA+IHR和GA+OIHR三個(gè)算法。這三個(gè)算法是在已提出的HR算法的

2、基礎(chǔ)上改進(jìn)的。GA+HR算法是HR算法結(jié)合遺傳算法的全局搜索能力，通過(guò)遺傳算法搜索到更優(yōu)的排列順序，使得解的效果進(jìn)一步提高。GA+IHR算法中，定義了參考矩形和結(jié)合層的概念，通過(guò)找出所有結(jié)合層，然后計(jì)算每個(gè)結(jié)合層數(shù)所產(chǎn)生的解，最后從這些解中找出最優(yōu)的解和最佳結(jié)合層數(shù)。GA++OIHR算法中，在HR算法中加入了窮舉的思想，即對(duì)每一層的第一塊矩形的放置都考慮水平放置和垂直放置兩種情況，然后分別計(jì)算出這兩種放置方式所帶來(lái)的空間利用率。采用利用

3、率比較大的方式作為該層的放置方式。而且在每一層子空間采用HR遞歸算法時(shí)，先搜索那些長(zhǎng)或?qū)捯春妥涌臻g的高度相同要么和子空間的寬度相同的矩形，先把這些矩形放置好，這樣放置后該子空間還是只被劃分成一個(gè)更小的子空間，可以減少子空間的個(gè)數(shù)。從而減少因?yàn)椴粩噙f歸劃分成兩個(gè)子空間，使得一些小空間因?yàn)樵僖卜胖貌幌氯魏我粔K矩形而造成的浪費(fèi)。在本文中我們還把計(jì)算二維裝箱問(wèn)題的HR算法和GA+HR算法運(yùn)用到三維裝箱問(wèn)題中。計(jì)算結(jié)果顯示HR算法運(yùn)行時(shí)間短，但