基于混合模擬退火算法的多約束裝箱問題研究

胡智瑩，周翔，李建伶，劉峻良

摘 要：文章針對現(xiàn)實中在實際多種約束條件下存在的三維裝箱問題，考慮在多種現(xiàn)實約束條件下，建立一個裝箱模型。該模型通過啟發(fā)式算法得到一個初始解，再根據(jù)模擬退火法得到最優(yōu)解，利用標(biāo)準(zhǔn)抽樣對最優(yōu)解進(jìn)行多次測試，得到符合實際情況的最優(yōu)解，提高空間利用率，從而實現(xiàn)利潤最大化。最后，以一個具體的例子進(jìn)行測試，計算結(jié)果表明在約束條件下裝箱問題的解決方案可行性較強(qiáng)。

關(guān)鍵詞：多約束裝箱問題;啟發(fā)式算法;模擬退火算法

1 新型的混合模擬退火法

在多種約束條件下，為了解決最優(yōu)化裝箱問題，本文運(yùn)用了改進(jìn)后的模擬退火法[1]與啟發(fā)式算法[2]相結(jié)合的方式產(chǎn)生了一種新型的混合模擬退火法。該方法利用啟發(fā)式算法對最優(yōu)解進(jìn)行搜索，同時在搜索最優(yōu)解的過程中引入記憶功能，保證了利用本方案搜索解的不重復(fù)性和全面性，確保搜索到的解為最合適的解。

2 現(xiàn)實約束

實際情況的不一樣，導(dǎo)致受到的約束也不一樣，本文考慮了如下幾種約束條件[3]：

（1）方向約束。規(guī)則的箱體有6個面，所以裝箱時，每一種貨物都有6種擺放方式。本文考慮的方向約束條件中包含了6種擺放方式，即認(rèn)為6個面的擺放方式會產(chǎn)生6種不同的結(jié)果。

（2）各貨物堆放時，沒有出現(xiàn)形變、重疊的情況。

（3）各貨物嚴(yán)格與裝載的箱體平行，沒有斜放的情況出現(xiàn)。

（4）容積約束。各箱體裝載時只在有效容積以內(nèi)，即裝載的貨物都包含在將要裝載的箱體以內(nèi)。

（5）重量約束。貨物有一定的堆放層數(shù)的約束，并且裝載的貨物不能超過箱體的最大承重量。

（6）裝載順序約束。由于實際生活的需要，貨物在裝載和卸貨中，遵循“先上后下”的原則。

3 理想模型的假設(shè)

本文研究多約束的裝箱問題，同時結(jié)合現(xiàn)實生活中方向、容積、重量、裝載順序等多方面的條件約束做出如下模型假設(shè)：集裝箱為標(biāo)準(zhǔn)的長方體;集裝箱外部尺寸與內(nèi)部尺寸相同;貨物重量分布均勻且為標(biāo)準(zhǔn)的長方體;貨物不會產(chǎn)生形變。

4 模型的建立

設(shè)在每一溫度下抽樣次數(shù)的最大值為Max，在不改變當(dāng)前溫度狀態(tài)的抽樣次數(shù)的最大值表示為z，接受該狀態(tài)的次數(shù)表示為a，則利用混合模擬退火法解決多種約束條件下三維裝箱問題的具體方法如下。

4.1 運(yùn)用啟發(fā)式算法得初始解

（1）在給定的n種貨物中，根據(jù)其實際的下載順序，逆序生成上載順序，從而生成不同的批次，在每一批次，根據(jù)各貨物體積的大小生成一個集合B[4]。

（2）初始化條件：設(shè)現(xiàn)階段已經(jīng)完成裝箱任務(wù)的貨物種類數(shù)量為i，且i的初始值為0。

（3）將i加1得到預(yù)比值，并將預(yù)比值與n進(jìn)行比較，如果預(yù)比值小于或者等于n，則繼續(xù)進(jìn)行下一步，如果大于則跳轉(zhuǎn)到第（5）步。

（4）對于將要裝箱的第i種貨物按照體積進(jìn)行分塊，得到集合Si，對每一個塊即Si的元素按照前述方法進(jìn)行裝載，Si每個元素裝載完畢即認(rèn)為第i種貨物裝載完畢，轉(zhuǎn)第（3）步。

（5）結(jié)束。

4.2 改進(jìn)模擬退火算法

（1）設(shè)在每一溫度下抽樣次數(shù)的最大值為Max，在不改變當(dāng)前溫度所在狀態(tài)的抽樣次數(shù)的最大值表示為z，接受該狀態(tài)的次數(shù)表示為a。

（2）對啟始溫度ts和結(jié)束溫度tf等參數(shù)進(jìn)行初始化處理。

（3）運(yùn)行啟發(fā)式算法程序，得到初始解s，令i=0且令得到的初始解s為目前得到的最優(yōu)解，即best=s，當(dāng)前狀態(tài)，s（k+1）=s（k） ，s（i）=s。

（4）令T=t（i），以T，best以及s（i）為參數(shù)代入改進(jìn)的抽樣過程程序，運(yùn)行程序，將得到的值，更新為當(dāng)前的最優(yōu)解best，并將此結(jié)果返回到抽樣過程中，并令s（i+1）=best。

（5）if f（best）≤f（best），則best=best。

（6）退溫：

;T=e-paT; i=i+1

（7）假設(shè)T

（8）輸出最優(yōu)解的結(jié)果best，當(dāng)前算法結(jié)束。

4.3 改進(jìn)標(biāo)準(zhǔn)抽樣過程

（1）令k=0，初始狀態(tài)s（k）=s（i），初始最優(yōu)解best=best，q=0， accept=0; k為抽樣的次數(shù)，q為連續(xù)抽樣而沒有改進(jìn)狀態(tài)的次數(shù)。

（2）通過執(zhí)行鄰域操作，由當(dāng)前的狀態(tài)s（k）產(chǎn)生一個新的狀態(tài)s*， 然后運(yùn)用評估函數(shù)計算?f=f（s（k））-f（s*）。

（3）如果條件?f<0成立，則令s（k+1）=s*，best=s*，accept=accept+1，以及q=0。

（4）當(dāng)?f≥0的條件滿足時，則程序?qū)⒁詄xp（﹣?f/T）的概率接受新得到的解s*， 假設(shè)概率方式即新解被接受后，則令s（k+1）=s*， q=0， accept=accept+1。

（5）如果條件沒有被滿足，那么對抽樣的狀態(tài)以及抽樣進(jìn)行的次數(shù)進(jìn)行更新，即令s（k+1）=s（k） ， q= q+1。

（6）令k=k+1，若k≥L或者q≥stay，則轉(zhuǎn)向步驟（5），否則，轉(zhuǎn)向步驟（2）。

（7）將得到的accept，best值輸出，并退出退火過程，此次抽樣的過程到此結(jié)束。

5 實例驗證

模型建立后，考慮到容積、方向、穩(wěn)定性、裝載順序、重量等多方面的約束在實際裝載過程中的運(yùn)用，本文采用標(biāo)準(zhǔn)的RAR集裝箱進(jìn)行裝箱的計算，其具體的長、寬、高數(shù)據(jù)和載重量屬性如表1所示。

本例采用的貨物數(shù)據(jù)源于趙雨霏的《我國快遞企業(yè)航空貨運(yùn)飛機(jī)裝載優(yōu)化研究》一文，詳情如表2所示。將以上貨物數(shù)據(jù)代入程序進(jìn)行裝箱的模擬，程序運(yùn)行結(jié)束后可以得到結(jié)果：利用兩個標(biāo)準(zhǔn)集裝箱就可以將表2的貨物全部轉(zhuǎn)載完，且其中裝載量最大的集裝箱體積利用率為96.25%，箱號為1的集裝箱長度公差、寬度公差、高度公差分別為1 cm，2 cm，1 cm，體積利用率為96.25%。本次算例最大三維裝箱如圖1所示。

6 結(jié)語

在解決多約束條件下的三維裝箱問題，本文采用啟發(fā)式算法以及模擬退火算法與標(biāo)準(zhǔn)抽樣算法相結(jié)合的方式，提出了一種新的解決方案。結(jié)合約束條件，對現(xiàn)實生活中的貨物裝載算例進(jìn)行了測試，得到了一種理想條件下的裝箱解決方案，證明了本文算法的高效性和可行性。在利用啟發(fā)式算法過程中，模擬了人工進(jìn)行裝箱的過程，通過標(biāo)準(zhǔn)抽樣與模擬退火法的集成，大大提高了集裝箱體積利用率，為多約束裝箱問題的求解提供了一種解決方案。

作者簡介：胡智瑩（1999— ），女，湖北武漢人，本科生;研究方向：電氣工程及其自動化。

[參考文獻(xiàn)]

[1]張鈞，賀可太.求解三維裝箱問題的混合遺傳模擬退火算法[J].計算機(jī)工程與應(yīng)用，2019（14）：32-39，47.

[2]張德富，彭煜，張麗麗.求解三維裝箱問題的多層啟發(fā)式搜索算法[J].計算機(jī)學(xué)報，2012（12）：2553-2361.

[3]曹玲芝.求解三維裝箱問題的混合模擬退火算法研究[D].廣州：華南理工大學(xué)，2013.

[4]陳麗.基于三維裝箱問題的混合遺傳模擬退火算法的改進(jìn)[D].鄭州：鄭州大學(xué)，2013.

Research on multi-constraint packing problem based on?hybrid simulated annealing algorithm

Hu Zhiying， Zhou Xiang， Li Jianling， Liu Junliang

（College Of Electrical Engineering&New Energy， Three Gorges University， Yichang 443002， China）

Abstract：In view of the three-dimensional packing problem existing in real variety of constraints in the reality， this paper takes into consideration the establishment of a packing model under various practical constraints. In this model， an initial solution is obtained by a heuristic algorithm， and the optimal solution is obtained according to the simulated annealing method， and the optimal solution is tested for many times by the standard sampling， the optimal solution of the actual situation is obtained， and the space utilization ratio is improved， and the profit maximization is realized. Finally， the test is carried out in a specific example， and the calculation result shows that the solution of the packing problem is strong under the constraint condition.

Key words：multi-constraint packing problem; heuristic algorithm; simulated annealing algorithm