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

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

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