求解裝箱問(wèn)題的啟發(fā)式算法研究.pdf

1、裝箱問(wèn)題是個(gè)在工業(yè)生產(chǎn)中經(jīng)常碰到的問(wèn)題，如集裝箱的裝載、板材的切割、集成電路的設(shè)計(jì)、報(bào)紙的排版等等。該問(wèn)題又是NP完全問(wèn)題，因此對(duì)該問(wèn)題的研究有著重要的應(yīng)用價(jià)值和理論意義。如果用精確算法求解裝箱問(wèn)題，勢(shì)必帶來(lái)計(jì)算量的組合爆炸，因此學(xué)者提出了很多求解該問(wèn)題的啟發(fā)式算法。 本文首先研究了二維裝箱問(wèn)題，在總結(jié)前人工作的基礎(chǔ)上，提出了解決二維矩形條裝箱(2SP)的二分搜索啟發(fā)式(BSHA)算法。首先，通過(guò)引入二分搜索把2SP問(wèn)題轉(zhuǎn)化成二

2、維背包裝箱問(wèn)題(2KP)來(lái)求解。然后，針對(duì)2KP，本文提出了最小浪費(fèi)優(yōu)先策略，該策略通過(guò)記錄點(diǎn)的方法來(lái)記錄裝填位置，并引入浪費(fèi)面積、平整度等評(píng)價(jià)機(jī)制來(lái)評(píng)價(jià)某個(gè)物品放入某個(gè)位置的好壞程度。最后，利用隨機(jī)局部搜索算法進(jìn)一步改進(jìn)計(jì)算的結(jié)果。本文對(duì)BSHA算法進(jìn)行了大量的實(shí)例測(cè)試，結(jié)果表明，BSHA的求解質(zhì)量?jī)?yōu)于目前優(yōu)秀的算法，如GRASP、SPGAL、HRBB等，而且對(duì)于很多實(shí)例，BSHA都能在短時(shí)間內(nèi)找到最優(yōu)解。 對(duì)于三維裝箱問(wèn)題，