【摘 要】裝箱問題是計算機科學(xué)領(lǐng)域最原始的基礎(chǔ)問題之一，在多個研究領(lǐng)域內(nèi)盛行，諸如組合優(yōu)化。裝箱問題的研究使得近似度分析和對手分析策略得到發(fā)展，對計算機科學(xué)的發(fā)展有巨大的推動作用。在計算機領(lǐng)域的多處理器調(diào)度，內(nèi)存分配和工業(yè)領(lǐng)域的任務(wù)調(diào)度，切割存儲及其裝載卡車問題上都有著廣泛的應(yīng)用。本文提出了求解大型二維裝箱問題的禁忌算法。算法基于自然數(shù)編碼并根據(jù)鄰域的不同，構(gòu)造了兩種禁忌表，設(shè)計了貨物的擺放規(guī)則和序列生成方式。算法采用懲罰函數(shù)處理空間利用率約束，最后給出了具有代表性算例試驗結(jié)果并且進行了分析。

【關(guān)鍵詞】裝箱 禁忌算法 問題研究

一、引言

裝箱問題作為最原始的NP難問題之一，其研究始于20世紀(jì)70年代，影響至今。裝箱問題還有著極為廣泛的實際應(yīng)用研究背景，涉及到工業(yè)領(lǐng)域，計算機應(yīng)用科學(xué)領(lǐng)域，物流行業(yè)及其日常生活領(lǐng)域等多方面。

二、裝箱問題定義及描述

大型2BP問題的實際應(yīng)用中，一般含有多種尺寸型號，而每種尺寸型號又含有多個同尺寸的物體.故本文大型2BP問題可描述如下：公司現(xiàn)有N 個尺寸型號的矩形物體（以后簡稱貨物） ， 每個型號貨物的寬、高分別為wi ， hi （wi ≤hi ） ，每個型號貨物數(shù)量分別為ni個. 要把這些物體放入寬、高分別為W， H （W ≤H） 的矩形箱，且單個矩形箱的空間利用率要大于D %. 求選用最小的矩形箱個數(shù)的裝載方案.

三、求解禁忌算法設(shè)計

（一）貨物擺放方位及解的編碼設(shè)計

2BP問題涉及到貨物寬、高兩個方向，因此每一貨物有2種擺放方式，對應(yīng)矩形箱的寬高W， H，貨物擺放方位分別為：wi、hi ， hi、wi ， 可用編碼0、1表示.

本文解的結(jié)構(gòu)由以下兩部分組成：編號和方位.

1.貨物的編號：用自然數(shù)表示，不同編號的物體可能是同種型號（尺寸） ；

2.貨物的方位：即放置的貨物方位，用0、1表示.

（二）貨物擺放規(guī)則

把矩形箱左下點定義為基點，貨物從基點開始按一定次序放置. 貨物與矩形箱、貨物與貨物之間邊線的左下相交點稱為潛在放置點.A 點為基點， B、C、D為潛在放置點.對于解（ i1 ， i2 ，… ， in ， - j1 ， j2 ， …， jn ），貨物的擺放規(guī)則為：

1. 置k： = 0；

2. k： = k + 1，如果k > n，轉(zhuǎn)6；

3. 對于物體ik，判斷當(dāng)前矩形箱是否還能按方位jk放置該貨物，能則轉(zhuǎn)5，否則繼續(xù)；

4. 增加一新矩形箱，確定新基點；

5. 把ik 按方位jk 放入所有潛在放置點，比較ik 與貨物或者矩形箱的接觸線aj與 bj的大小，選擇該值最大的潛在放置點擺放ik ， 轉(zhuǎn)2；

6. 結(jié)束

（三）初始化

產(chǎn)生初始解步驟為：

1. 隨機在區(qū)間（0， 0. 5）之間取隨機數(shù)a，將所有貨物按值a*wi + （1 - a）*wihi降序排列，得到序列SH ；初始化i = 0； j = 0；

2.判斷SH 是否為空，是則轉(zhuǎn)10；否則繼續(xù)；

3.j： = j + 1；

4. 取新矩形箱j；

5.i： = i + 1；

6. 如果SH 中i已經(jīng)移出，轉(zhuǎn)5；

7. 按0方位在j箱放置貨物i，如果j箱空間不足，不能按0方位放置i，繼續(xù)；否則將i從SH 中移去，轉(zhuǎn)5；

8.按1方位在j箱放置貨物i，將i從SH 中移去，轉(zhuǎn)5；否則繼續(xù)；

9.在SH 中i后面的貨物分別按0、1方位放置，如果找到能放入當(dāng)前層的貨物k，則按既定方位放置，將k從SH 中移去， i： = k， 轉(zhuǎn)5 ；否則轉(zhuǎn)3；

10.結(jié)束算法.

（四）利用率最小的矩形箱貨物移入、移出操作

每經(jīng)過一次貨物序列更新鄰域或者貨物擺放方位變化鄰域操作，選用的矩形箱會出現(xiàn)剩余空間或者剩余貨物. 出現(xiàn)剩余空間是因為經(jīng)過鄰域操作得到了更好的擺放序列或者擺放方位，反之會出現(xiàn)剩余貨物.

（五）禁忌表的設(shè)計和終止準(zhǔn)則

本文設(shè)計的兩種鄰域是針對不同對象（貨物序列和單個貨物）進行的操作，故構(gòu)造了與之相對應(yīng)的兩個禁忌表，分別為貨物序列禁忌表和貨物方位禁忌表.貨物序列禁忌表. 即對序列調(diào)整系數(shù)a按步長ξ進行操作，如果當(dāng)前代對a進行了增加ξ的操作，那么在接下來的ηx 代內(nèi)，不允許對a進行減小ξ的操作； 貨物方位禁忌表. 即如果當(dāng)前代對貨物i進行了方位取反操作，那么在接下來的ηH 代內(nèi)，不允許再對貨物i進行方位取反操作.終止準(zhǔn)則. 如果連續(xù)迭代ND 代最優(yōu)解沒有變化，則算法終止.

四、禁忌算法優(yōu)化大型二維裝箱問題關(guān)鍵步驟

禁忌算法優(yōu)化多箱型二維裝箱問題詳細(xì)步驟為：

1.初始化各參數(shù)，產(chǎn)生初始解，搜索循環(huán)次數(shù)i = 0；

2.i： = i + 1；

3.貨物擺放方位變化鄰域，貨物序列更新鄰域操作；

4.禁忌表及特赦準(zhǔn)則處理；

5.滿足終止條件，轉(zhuǎn)6；否則轉(zhuǎn)2；

6.結(jié)束.

五、算例分析

把Martello算例產(chǎn)生程序稍加修改，增加wi ≤ hi 限制，產(chǎn)生一組數(shù)據(jù). 貨物型號分為25種，每種型號寬度wi在區(qū)間（0. 5， 5）中隨機產(chǎn)生，高度hi在區(qū)間（2， 10） 中隨機產(chǎn)生，且wi ≤ hi ，每種貨物型號的數(shù)量在區(qū)間（50， 150） 之間產(chǎn)生，總共產(chǎn)生2239個貨物. W = 50， H = 70， D% = 85%.用C語言實現(xiàn)大型二維裝箱問題的禁忌算法， 取禁忌算法參數(shù)ξ = 0. 02，ηX = 30，ηH = 4，ND = 200， NX = 20. 在PⅣ2. 0機型上計算20次，以100%概率收斂到本算法所能得到的最優(yōu)解值為13 （各解的貨物排列序列不完全相同） ，總空間利用率達到93. 7% ，平均收斂時間僅為1分26秒. 從算法的計算效率方面分析是有效的.

六、結(jié)論

本文對大型二維裝箱問題進行了描述，提出了求解該問題的禁忌算法，介紹了算法的原理，并通過算例結(jié)果及其分析證明了此算法的有效性. 用本文提出的禁忌算法能優(yōu)化規(guī)模較大的二維裝箱問題，速度較快，運算過程及結(jié)果穩(wěn)定，具有較強的實際應(yīng)用價值。