求解二維矩形packing問題的高效算法設(shè)計(jì).pdf

1、研究了二維矩形packing這一類NP難度問題。在黃文奇等人提出的擬人型穴度算法的基礎(chǔ)之上,提出了基于動(dòng)作空間的擬人型穴度算法,通過定義動(dòng)作空間來簡化對不同放入動(dòng)作的評價(jià),使穴度的計(jì)算時(shí)間明顯縮短,從而使算法既繼承了原有穴度算法的優(yōu)勢,又能夠快速地得到面積利用率較高的布局圖案。
　　重點(diǎn)研究了二維矩形裝填問題,給出了格局、動(dòng)作空間、占角動(dòng)作、平整度、評價(jià)標(biāo)準(zhǔn)和比較策略的定義。基于動(dòng)作空間,簡化了對不同放入動(dòng)作的評價(jià),明顯縮短了計(jì)算

2、時(shí)間。在算法的設(shè)計(jì)中,著重考慮了如何分割矩形框內(nèi)的剩余空間使放入塊與周圍的已放入塊更緊密、采用哪種數(shù)據(jù)結(jié)構(gòu)使得剩余空間的更新更快捷、如何選取一個(gè)唯一的占角動(dòng)作使之遵循“可持續(xù)發(fā)展的路線”、選取哪種搜索策略可以使結(jié)果不斷趨近全局最優(yōu)解而不至于陷入局部最小值的陷阱。
　　進(jìn)一步地,將此算法適當(dāng)調(diào)整以求解二維strip packing問題和二維矩形packing價(jià)值優(yōu)化問題。針對二維strip packing問題的特點(diǎn),結(jié)合了加1法和二

3、分法以求解已知矩形敞口框的最優(yōu)高度和未知矩形敞口框的最優(yōu)高度的兩類子問題。針對二維矩形packing價(jià)值優(yōu)化問題的特點(diǎn),修改了占角動(dòng)作的比較策略,加入了放入塊的單位價(jià)值作為比較因子,并將目標(biāo)函數(shù)調(diào)整為所有放入塊的總價(jià)值。
　　對二維矩形裝填問題、二維strip packing問題和二維矩形packing價(jià)值優(yōu)化問題,試算了國際上著名的相關(guān)算例。所提出的算法均能在較短的時(shí)間內(nèi)得到較優(yōu)的結(jié)果。對二維矩形裝填問題,在Hopper和Tur