單一貨物擺放無約束三維裝箱簡便快速優(yōu)化裝箱方法

蒲榮雪 吳鈴 李國柳

摘 要：裝箱問題傳統(tǒng)解法計(jì)算工作量大、不易掌握且裝箱效率低，為了克服問題提出新的優(yōu)化解法，該方法把裝箱作業(yè)分為3大類18種具體類別，為了簡化求解方法、提高求解速度和裝箱效率，對最低層的2種組合不做線性規(guī)劃求解，只是選擇其中好的方案，以此作為基礎(chǔ)數(shù)據(jù)，再對貨箱3個(gè)維度分別規(guī)劃求解，求出優(yōu)化組合，給出簡便快速優(yōu)化裝箱方法。該方法雖然優(yōu)化程度略低，但方法更為簡單、求解和裝箱效率更高，優(yōu)化程度較為理想。

關(guān)鍵詞：單一貨物；三維裝箱問題；簡便快速優(yōu)化裝箱方法；線性規(guī)劃法

中圖分類號(hào)：TP 391.72 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7312（2017）02-0132-04

Abstract：The traditional solution of packing problem is large，difficult to master and low packing efficiency，in order to overcome the problem，a new optimization solution is proposed，which divides the packing operation into three categories of 18 specific categories.In order to simplify the solution，improve the speed and packing efficiency，the two combinations of LOWEST STATION are not linear programming，only the good scheme，as the basic data，and three dimensions of the box are solved respectively，the optimization combination，and simple and fast packing method.Although the degree of optimization is slightly lower，but the method is simpler，the solution and packing efficiency is higher，and the optimization degree is more ideal.

Key words：single goods；three dimensional packing problem；simple and rapid packing method；linear programming method

0 引 言

貨物三維擺放無約束裝箱問題是NP難問題（3DBPP），如何解決這一難題，一直是人們關(guān)注的問題。自從1960年以來，許多專家、學(xué)者和實(shí)際工作者做了大量研究，解決的方法主要是搜索法[1]、啟發(fā)式算法[2]和數(shù)學(xué)規(guī)劃法[3]等。雖然解法很多，但具有實(shí)際應(yīng)用價(jià)值的成果較少，有些方法復(fù)雜、高深、裝箱效率低，不易被實(shí)際工作者掌握和運(yùn)用。研究成果多數(shù)是針對多種不同貨物裝箱問題，單一貨物裝箱問題研究成果相對很少[4-11]，國內(nèi)只查到10篇文獻(xiàn)。已有線性規(guī)劃解法，通常只針對一維裝箱問題[12]，三維裝箱問題，國內(nèi)很少有文獻(xiàn)論述，國際上雖然有些論述[13]，但三維裝箱問題可供參考的文獻(xiàn)不多。為了豐富裝箱優(yōu)化方法、提高裝箱效率，提出簡便快速優(yōu)化裝箱方法。

1 理論探討

1.1 裝箱問題特點(diǎn)與規(guī)律分析

雖然3DBPP是NP難問題，組合方案數(shù)量眾多，但是因貨箱以及貨物各只有長、寬和高3個(gè)維度，因此，可計(jì)算出貨物裝箱組合種類數(shù)，一共只有18種。一方面，盡管是三維裝箱問題，但貨箱或貨物某一維度被選用后，就只剩下其余2個(gè)維度，以此類推，根據(jù)這一規(guī)律，可把三維裝箱問題轉(zhuǎn)化成二維，二維轉(zhuǎn)化為一維。另一方面，盡管組合方案數(shù)量眾多、但是可利用線性規(guī)劃求最優(yōu)解，把復(fù)雜問題簡單化、程序化。

裝箱過程可分為3個(gè)階段。第一階段，裝箱時(shí)首先面臨選擇貨箱長（JC）、寬（JK）和高（JG）3個(gè)維度中哪個(gè)維度擺放貨物，形成3大類，第一大類選擇貨箱的長，第二大類選擇貨箱的寬，第三大類選擇貨箱的高；第二階段，在選定貨箱某一維度后，需要選擇把貨物長（C）、寬（K）和高（G）3個(gè)維度中哪個(gè)維度與選定貨箱維度平行擺放，形成3小類，第一小類選擇貨物的長，第二小類選擇貨物的寬，第二大類選擇貨物的高；第三階段，在完成前2個(gè)階段后，貨箱只剩下沒被優(yōu)化的2個(gè)維度，貨物只剩下沒被選用的2個(gè)維度（假設(shè)剩余k和h維度），還可分別按貨箱剩余的2個(gè)維度（假設(shè)剩余M和N維度）優(yōu)化擺放貨物，形成3小類下2種最底層組合種類。如果目標(biāo)只是提高優(yōu)化程度，還可在此運(yùn)用規(guī)劃求解，求出優(yōu)化組合，然后再按貨箱3個(gè)維度優(yōu)化組合，求出優(yōu)化程度極高的優(yōu)化方案。這里，既想提高優(yōu)化程度，又要兼顧方法簡單、求解速度快、裝箱效率高，因此，對這2種最底層組合種類不進(jìn)行規(guī)劃求解，只是選擇2種擺放方案中擺放2種數(shù)量多的方案（方案1，貨物k對應(yīng)貨箱M、貨物h對應(yīng)貨箱N；方案2，貨物k對應(yīng)貨箱N、貨物h對應(yīng)貨箱M），在此基礎(chǔ)上，再按貨箱3個(gè)維度優(yōu)化組合，求出優(yōu)化程度較好的優(yōu)化方案。因此，3個(gè)階段一共組合種類數(shù)（N）為：N=3×3×2=18個(gè)。

1.2 裝箱問題描述及相關(guān)基礎(chǔ)數(shù)據(jù)Excel計(jì)算公式

設(shè)某單一貨物需要裝入一種規(guī)格矩形貨箱，Xij為貨物維度為i，按貨箱維度j能擺放個(gè)數(shù)，i從1到3，分別代表貨物長、寬和高；j從1到3，分別代表貨箱長、寬和高；其他符號(hào)參見表1.Nmax為貨箱最多能裝貨物的個(gè)數(shù)。

某個(gè)維度能擺放的個(gè)數(shù)計(jì)算公式為：D3=int（$C3/D$2），復(fù)制區(qū)域D3：F5，貨箱最多能裝貨物的個(gè)數(shù)Nmax對應(yīng)的單元格D6=int（（C3*C4*C5）/（D2*E2*F2））。

1.3 求解步驟與數(shù)學(xué)模型

1.3.1 求解步驟

第一步，分別求出3大類中的6種最低層組合方案中每組較好的擺放方案，然后再求該大類最終優(yōu)化組合方案。

第二步，求裝箱問題最終近似最優(yōu)解，3大類中最終組合方案最大者為近似最優(yōu)解方案。

第三步，給出裝箱方案。根據(jù)近似最優(yōu)解方案逆向?qū)ふ揖唧w詳細(xì)裝箱方案。因篇幅所限，這里只給出最終近似最優(yōu)解方案，具體詳細(xì)裝箱方案從略。

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

最終近似最優(yōu)解方案Z=max（ZJC，ZJK，ZJG）=max（2 784，2 767，2 784）=2 784，按貨箱長度或按貨箱高度優(yōu)化均可，以按貨箱長度優(yōu)化為例，裝箱方案為：貨物長度按貨箱長度平行擺放10個(gè)，且貨物的寬對應(yīng)貨箱的寬平行擺放、貨物的高對應(yīng)貨箱的高平行擺放；貨物高度按貨箱長度平行擺放3個(gè)，因此是2種擺放方法數(shù)量相等，所以貨物的長對應(yīng)貨箱的寬平行擺放、貨物的寬對應(yīng)貨箱的高平行擺放，或貨物的長對應(yīng)貨箱的高平行擺放、貨物的寬對應(yīng)貨箱的寬平行擺放均可以。

裝箱優(yōu)化程度≥（2 784/2 819）×100%=98.75%，優(yōu)化程度較為理想。

最終優(yōu)化解法為Z=max（ZJC，ZJK，ZJG）=max（2 794，2 794，2 784）=2 794，優(yōu)化程度99.1%.與最低層規(guī)劃求解方法優(yōu)化程度只相差0.36%，裝箱優(yōu)化程度比較理想，方法更為簡單、裝箱效率更高。

3 結(jié) 論

由于貨物和貨箱只具有3個(gè)維度，因裝箱時(shí)某一區(qū)域擺放方式是相同的，所以裝箱組合數(shù)是固定，根據(jù)裝箱18種組合，運(yùn)用線性規(guī)劃進(jìn)行組合優(yōu)化，借助Excel軟件能在幾分鐘內(nèi)給出易于裝箱優(yōu)化方案。該方法優(yōu)化程度高、裝箱效率高、耗時(shí)少、求解成本低。

參考文獻(xiàn)：

[1]Jose Fernando Goncaves，Mauricio G C，Resende.A biased random key genetic algorithm for 2D and 3D bin packing problems[J].Int J Production Economics，2013，145（2）：500-510.

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

[3]Hifi M，Kacem L，Negre S，et al.A linear programming approach for the threedimensional bin packing problem[J].Electronic Notes in Discrete Mathematics，2010，36：993-1 000.

[4]農(nóng)健恒，崔耀東.同尺寸物品裝箱的動(dòng)態(tài)規(guī)劃算法[J].計(jì)算機(jī)應(yīng)用與軟件，2014，31（7）：249-251.

[5]隋樹林，邵巍，高自友.同一尺寸貨物三維裝箱問題的一種啟發(fā)式算法[J].信息與控制，2006，34（4）：490-494.

[6]王 巖，潘衛(wèi)平，陳秋蓮，等.單一尺寸長方體三維裝箱問題的一種求解算法[J].包裝工程，2015，36（11）：96-99.

[7]姚 怡，崔耀東.一種高效的同尺寸長方體的裝箱算法[J].計(jì)算機(jī)工程與科學(xué)，2012，34（10）：192-194.

[8]廖元秀，崔耀東.對Agrawal 單一矩形排樣算法的改進(jìn)與擴(kuò)展[J].廣西師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2004，22（3）：49-53.

[9]徐麗麗，季 忠，夏繼梅.同規(guī)格貨物裝箱問題的優(yōu)化計(jì)算[J]. 山東大學(xué)學(xué)報(bào)，2008，38（3）：14-17.

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

[11]孫洪禮，王周敬.同類貨物集裝箱裝載問題的啟發(fā)式算法[J].計(jì)算機(jī)應(yīng)用與軟件2011，28（4）：93-95.

[12]王桂強(qiáng).運(yùn)籌學(xué)上級指南原理導(dǎo)航用Excel工具[M].北京：格致出版社，2010.

[13]

Hifi M，Negre S，Wu L.Hybrid greedy heuristics based on linear programming for the threedimensional single binsize bin packing problem[J].International Transactions in Operational Research，2014，21（1）：59-79.

（責(zé)任編輯：許建禮）