單一規(guī)格物體二維矩形條帶裝箱問題解法研究

胡錦超，賈春玉

(寧波工程學(xué)院 經(jīng)濟(jì)與管理學(xué)院,浙江 寧波 315211)

單一規(guī)格物體二維矩形條帶裝箱問題解法研究

胡錦超，賈春玉

(寧波工程學(xué)院 經(jīng)濟(jì)與管理學(xué)院,浙江 寧波 315211)

為了克服用啟發(fā)式算法及智能搜索法解決單一規(guī)格物體二維矩形條帶裝箱問題耗時(shí)過長(zhǎng)的缺陷，提出了新的解法和思路.用線性規(guī)劃法分別在2個(gè)維度求最優(yōu)解，以最好的方案作為近似最優(yōu)解，可大幅度縮短求解時(shí)間,獲得滿意的近似最優(yōu)解.

單一規(guī)格；裝箱問題；啟發(fā)式算法；線性規(guī)劃解法；智能搜索法

三維n個(gè)不同規(guī)格矩形條帶裝箱問題是最為復(fù)雜NP難的矩形條帶裝箱問題,也是長(zhǎng)寬高3個(gè)維度均需優(yōu)化的裝箱問題.只需考慮2個(gè)維度時(shí)，它同樣也是NP難問題，只是復(fù)雜程度、計(jì)算工作量明顯少于三維而已.當(dāng)貨箱某一維度是貨物尺寸整數(shù)倍或擺放有特殊要求(如只能立著擺放)時(shí)，高度方向擺放貨物的數(shù)量固定不變，三維裝箱問題轉(zhuǎn)化為二維裝箱問題，可大幅度減少計(jì)算工作量，縮短優(yōu)化時(shí)間.裝箱問題的應(yīng)用相當(dāng)廣泛,除直接運(yùn)用于物流領(lǐng)域外,在新聞組版、布料切割、制造業(yè)的三維二維和一維下料等領(lǐng)域均可運(yùn)用.

三維或二維n個(gè)不同規(guī)格矩形條帶裝箱問題的計(jì)算復(fù)雜度隨著問題規(guī)模的增大呈指數(shù)增長(zhǎng).雖然國(guó)內(nèi)外相關(guān)學(xué)者對(duì)這類問題做了大量的研究，但仍然需要提高解法的優(yōu)化程度.國(guó)內(nèi)外有關(guān)三維或二維裝箱問題的研究廣泛采用遺傳算法[1]、模擬退火算法[2]等搜索算法與BL(bottom-left)、IBL(improved BL)、BLF(bottom-left-fill)等啟發(fā)式布局算法相結(jié)合的方式.此外，還有塊排列法[3]和分支定界方法等相關(guān)研究.這些研究關(guān)于多個(gè)不同貨物裝箱問題的成果較多，而關(guān)于單一貨物裝箱問題的成果卻很少.

楊德榮在2006 年提出了一套完善的同規(guī)格物體優(yōu)化裝箱算法[4].該算法首先沿3 個(gè)坐標(biāo)方向計(jì)算最優(yōu)高度, 得出層的分布, 將問題轉(zhuǎn)化為平面布局;再通過優(yōu)化計(jì)算和鏡像復(fù)制, 得到完整的平面優(yōu)化結(jié)果;然后比較三維空間3個(gè)坐標(biāo)方向的優(yōu)化趨勢(shì), 選擇可能裝入物體最多的方向中最好的一個(gè)平面優(yōu)化布局結(jié)果, 并依次裝入集裝箱.盡管已有一些線性規(guī)劃方法用于優(yōu)化裝箱問題，但仍有很大的改進(jìn)空間，急需對(duì)這一問題進(jìn)行深入研究，豐富完善和簡(jiǎn)化優(yōu)化方法，提高優(yōu)化程度.為此，在文獻(xiàn)[5]的基礎(chǔ)上,本研究提出了一種更為簡(jiǎn)單的數(shù)學(xué)模型和計(jì)算方法，將沿3 個(gè)坐標(biāo)方向取優(yōu)簡(jiǎn)化為僅沿高度方向取優(yōu), 計(jì)算量為該文獻(xiàn)算法的1/3，而計(jì)算相同算例得到的集裝箱容積利用率相同.新的算法在平面優(yōu)化中,采用牛玉玲等在文獻(xiàn)[6]中提出的優(yōu)化模型, 并對(duì)其進(jìn)行了改進(jìn).

1 問題描述

設(shè)有n個(gè)相同貨物需要裝箱，貨物三維尺寸分別為長(zhǎng)LH、寬WH、高HH，貨箱三維尺寸分別為長(zhǎng)Lj、寬Wj、高Hj,貨物擺放要求為只能立著擺放.問題是如何擺放才能使得貨物所需裝箱最少或占用空間最小.

2 理論探討

2.1 三維變二維

由于貨物擺放有要求，只能立著擺放，因此高度不需要優(yōu)化.

設(shè)擺放個(gè)數(shù)為：

NKh=[Wj/HH]

(1)

其中，符號(hào)“[]”為向下取整.這樣，三維裝箱問題就可簡(jiǎn)化為二維裝箱問題，即如何在一個(gè)長(zhǎng)為L(zhǎng)j、寬為Wj的平面內(nèi)擺放長(zhǎng)為L(zhǎng)H、寬為WH的貨物，達(dá)到優(yōu)化擺放目標(biāo)(如一個(gè)貨箱內(nèi)所裝貨物最多的目標(biāo)).一個(gè)貨箱內(nèi)所裝貨物最多意味著剩余不能利用的空間(這里是面積)最小.假設(shè)貨箱和貨物長(zhǎng)度分別大于等于貨箱和貨物的寬度，按長(zhǎng)度優(yōu)化組合擺放貨物后，貨箱的剩余長(zhǎng)度為△Lj，則貨箱的剩余面積為：

SL=△Lj×Wj

(2)

按寬度優(yōu)化組合擺放貨物后，貨箱的剩余寬度為△Wj，則貨箱的剩余面積為：

SW=△Wj×Lj

(3)

2.2 優(yōu)先維度優(yōu)化組合的條件

由式(2)和式(3)可知，貨箱剩余不能利用的面積等于單位長(zhǎng)度或?qū)挾瘸艘圆荒芾玫某叽?，?個(gè)因素影響.按哪個(gè)維度優(yōu)化組合剩余面積小，就優(yōu)先按哪個(gè)維度優(yōu)化組合.

優(yōu)先按長(zhǎng)度優(yōu)化組合的條件是：

(4)

若式(4)不成立，就優(yōu)先按寬度優(yōu)化組合.

因?yàn)長(zhǎng)j≥Wj，所以，設(shè)優(yōu)化組合后貨箱的可利用長(zhǎng)度增加△YLj，可利用寬度增加△YWj，則按長(zhǎng)度優(yōu)化組合后增加的貨箱可利用面積為：

YSL=△YLj×Wj

(5)

按寬度優(yōu)化組合后增加的貨箱可利用面積為：

YSW=△YWj×Lj

(6)

當(dāng)△YLj=△YWj，或接近時(shí)，通常優(yōu)先優(yōu)化組合寬度，以提高優(yōu)化程度.但嚴(yán)格條件還是式(4).為了簡(jiǎn)化，可分別按長(zhǎng)度和寬度進(jìn)行優(yōu)化組合，兩者比較后哪個(gè)優(yōu)化程度高，哪個(gè)方案就是最優(yōu)解.

2.3 數(shù)學(xué)模型

如果按貨箱長(zhǎng)度Lj優(yōu)化組合可擺放X11個(gè)長(zhǎng)度為L(zhǎng)H的貨物(第一個(gè)下標(biāo)為貨物維度代號(hào)，1代表長(zhǎng)度，2代表寬度；第二個(gè)下標(biāo)為貨箱維度代號(hào)，1代表長(zhǎng)度，2代表寬度)，可擺放X21個(gè)寬度為WH的貨物；如果按貨箱寬度Wj優(yōu)化組合可擺放X12個(gè)長(zhǎng)度為L(zhǎng)H的貨物，可擺放X22個(gè)寬度為WH的貨物.

在這種情況下，在貨箱寬度方向可擺放寬度為WH的貨物kX22個(gè).其計(jì)算式為：

kX22=[Wj/WH]

(7)

在貨箱寬度方向可擺放長(zhǎng)度為L(zhǎng)H的貨物kX12個(gè).其計(jì)算式為：

kX12=[Wj/LH]

(8)

設(shè)目標(biāo)函數(shù)是每個(gè)貨箱所裝貨物數(shù)量最多(maxZL)，則按貨箱長(zhǎng)度優(yōu)化組合的數(shù)學(xué)模型為：

maxZL=X11×kX22+X21×kX12

其約束條件為：

X11+X21≤Lj

1.1一般資料2012年1月至2014年10月對(duì)我院的1800份細(xì)菌樣本進(jìn)行了分析,有350份血液樣本,占總數(shù)的19.44%,有312份尿液樣本,占總數(shù)的17.33%,有268份痰液樣本,占總數(shù)的14.89%;有287份糞便樣本占總數(shù)的15.94%;有348份創(chuàng)傷組織樣本,占總數(shù)的19.33%;有235份生殖道分泌物樣本,占總數(shù)的13.06%。

Lj-(X11+X21)≤min(WL，WH)

Xi j≥0，且為整數(shù)(i=1,2,…；j=1,2,…).

同理，按貨箱寬度優(yōu)化組合時(shí)，每個(gè)貨箱所裝貨物數(shù)量最多(maxZW)的數(shù)學(xué)模型為：

maxZW=X12×kX21+X22×kX11

其約束條件為：

X12+X22≤Wj

Wj-(X12+X22)≤min(WL，WH)

Xi j≥0，且為整數(shù)(i=1,2,…；j=1,2,…).

3 解法實(shí)例

3.1 實(shí)例1

這里參考文獻(xiàn)[5]中例題討論線性規(guī)劃法在裝箱問題中的運(yùn)用.貨箱長(zhǎng)度為5 000cm，寬度為3 000cm，貨物長(zhǎng)度為400cm，寬度為235cm.

首先計(jì)算kX22、kX12、kX21和kX11.

因?yàn)閗X22=[3 000/235]=12,kX12=[3 000/400]=7,kX21=[5 000/235]=21,kX11=[5 000/400]=12

所以按貨箱長(zhǎng)度優(yōu)化組合的單層數(shù)學(xué)模型為：

maxZL=X11×12+X21×7

其約束條件為：

X11+X21≤5 000

5 000-(X11+X21)≤min(WL，WH)=235

Xi j≥0，且為整數(shù)(i=1,2,…；j=1,2,…)

用Excel軟件解得：X11=6，X21=11，maxZL=6×12+11×7=149.

按貨箱寬度優(yōu)化組合的單層數(shù)學(xué)模型為：

maxZW=X12×21+X22×12

其約束條件為：

X12+X22≤3 000

3 000-(X12+X22)≤min(WL，WH)=235

Xi j≥0，且為整數(shù)(i=1,2,…；j=1,2,…).

用Excel軟件解得：X12=1，X22=11，maxZW=1×21+11×12=153

可見，該方法更為簡(jiǎn)單，省去了計(jì)算各種組合的工作量,只要改變貨箱和貨物長(zhǎng)與寬4個(gè)變量，用Excel軟件即可自動(dòng)完成優(yōu)化計(jì)算.實(shí)例1按貨箱寬度優(yōu)化組合，單層最多可裝貨物153個(gè)，而按貨箱長(zhǎng)度優(yōu)化組合時(shí)單層最多可裝貨物149個(gè).

3.2 實(shí)例2

把實(shí)例1中貨物的長(zhǎng)、寬尺寸分別改為430cm和230cm，貨箱尺寸不變，即貨箱長(zhǎng)度為5 000cm，寬度為3 000cm.

建立與實(shí)例1類似的數(shù)學(xué)模型，只需改變貨物的長(zhǎng)、寬尺寸，變量清除后直接求解即可.求解的結(jié)果為：kX22=[3 000/230]=13,kX12=[3 000/430]=6,kX21=[5 000/230]=21,kX11=[5 000/430]=11.

按貨箱長(zhǎng)度優(yōu)化組合的最優(yōu)解為：X11=11，X21=1，maxZL=149；按貨箱寬度優(yōu)化組合的最優(yōu)解為：X21=0，X22=13，maxZW=143.顯然，按貨箱長(zhǎng)度優(yōu)化組合的優(yōu)化程度高，單層最多可裝149個(gè)貨物，而按貨箱寬度優(yōu)化組合的最優(yōu)解是單層最多只能裝143個(gè)貨物.可見，不一定維度尺寸小的方向優(yōu)化組合效果就好.

4 結(jié)束語(yǔ)

傳統(tǒng)上優(yōu)化組合時(shí)優(yōu)先考慮維度尺寸短的然后考慮尺寸長(zhǎng)的，是一種比較好的啟發(fā)式算法，但不能保證最優(yōu)解.優(yōu)化程度改善量受2個(gè)因素影響(以二維為例受2個(gè)因素影響，三維時(shí)受3個(gè)因素影響)：一個(gè)是貨箱一維度優(yōu)化后可增加的長(zhǎng)度；另一個(gè)是貨箱另一維度的長(zhǎng)度.這二者的乘積決定了優(yōu)化程度的改善量.雖然維度尺寸短的對(duì)應(yīng)的另一維度尺寸長(zhǎng)，但不能保證二者乘積一定大.因此，應(yīng)按二維列出線性規(guī)劃模型，求出最佳組合.哪個(gè)維度的最佳組合更好，哪個(gè)就是最優(yōu)解.這是一種非常有效的單一規(guī)格物體裝箱問題求解方法.

[1] 李大可，楊花娥.利用遺傳算法求解裝箱問題[J].延安大學(xué)學(xué)報(bào)，2005，24(4)：32-34.

[2] 張德富，彭 煜，朱文興，等.求解三維裝箱問題的混合模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào)，2009，32(11)：2147-2156.

[3]EleyM.Solvingcontainerloadingproblemsbyblockarrangement[J].EuropeanJournalofOperationalResearch, 2002,141(2):393-409.

[4] 楊德榮.一類集裝箱布局問題的優(yōu)化計(jì)算[J].物流科技,2006,29(8):43-45.

[5] 楊德榮.集裝箱單一規(guī)格物體裝箱的優(yōu)化算法[J].交通運(yùn)輸工程與信息學(xué)報(bào),2007,5(2):17-23.

[6] 牛玉玲, 范玉妹, 徐 爾.條式配裝集裝箱的方法初探[J].物流技術(shù),2004(5)：47-49.

Research on the Solution of Two-dimensional Rectangular Strip Packing Problem in Single Specification Goods

HU Jin-chao,JIA Chun-yu

(School of Economics & Management, Ningbo University of Technology, Ningbo 315211,China)

The packing problem of two-dimensional rectangular strip is a big problem of NP. Although the two-dimensional bin packing can adopt the heuristic algorithm and intelligent search method, the time it takes usually very long. There have been some research results, but it still needs improvement. To solve these problems, new solutions are put forward. The linear programming method is used to find the best solution among two dimensions and to use the best solution as the approximate optimal solution. In this way, the resolving time can be greatly reduced and the satisfied approximate optimal solution can be obtained. This method is relatively simple with high efficiency.

single specification goods; packing problem; heuristic algorithm; linear programming solution; intelligent search method

2016-11-14

寧波市自然科學(xué)基金資助項(xiàng)目(2015A610174)

胡錦超(1995-)，男，浙江金華人，本科生，研究方向?yàn)槲锪鞴芾?

1006-3269(2017)02-0006-03

TP391

A

10.3969/j.issn.1006-3269.2017.02.002