那日薩, 韓琪瑋, 林正奎

(1.大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116023； 2.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026)

?

三維多箱異構(gòu)貨物裝載優(yōu)化及其可視化

那日薩1, 韓琪瑋1, 林正奎2

(1.大連理工大學(xué) 系統(tǒng)工程研究所，遼寧 大連 116023； 2.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026)

針對(duì)七種現(xiàn)實(shí)約束的集裝箱三維多箱異構(gòu)貨物裝載優(yōu)化問題，提出了一種基于 “塊”和“空間”的啟發(fā)式搜索算法。算法采用樹搜索策略，根據(jù)可用空間，對(duì)每一次搜索的貨物塊進(jìn)行評(píng)估，得到最佳的貨物塊，直到無可用空間或無可裝載的貨物為止?；陂_放式標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)的計(jì)算結(jié)果表明，該算法在時(shí)間效率和體積利用率上均優(yōu)于已有的同類研究。并基于Net平臺(tái)開發(fā)了一款3D裝箱布局優(yōu)化可視化軟件，已在相關(guān)物流企業(yè)中得到推廣應(yīng)用，驗(yàn)證了算法的實(shí)用性。

三維裝箱優(yōu)化；啟發(fā)式搜索；可視化；物流管理

0 引言

物流是國民經(jīng)濟(jì)的基礎(chǔ)產(chǎn)業(yè)，隨著社會(huì)經(jīng)濟(jì)的發(fā)展，特別是電子商務(wù)、信息技術(shù)、公路交通基礎(chǔ)設(shè)施的建設(shè)，物流產(chǎn)業(yè)在得到迅猛發(fā)展的同時(shí)，也對(duì)物流管理的智能化、最優(yōu)化和實(shí)時(shí)化等方面提出了新的要求。裝箱是物流管理的重要環(huán)節(jié)，現(xiàn)在多數(shù)企業(yè)都存在裝箱效率較低，導(dǎo)致貨物運(yùn)輸成本過高的問題。因此，如何構(gòu)建高效、實(shí)用的三維裝箱布局優(yōu)化算法和軟件也成為近年來學(xué)者們關(guān)注的熱點(diǎn)。

眾所周知，三維裝箱問題是一個(gè)NP-hard問題，很難精確求解。雖然一些研究采用了精確算法，但其求解的規(guī)模有限,至多能求解90個(gè)貨物裝載問題[1]，求解時(shí)間過長，目前多停留在理論研究階段。在實(shí)際應(yīng)用中，以啟發(fā)式算法等為代表的非精確算法得到了較大發(fā)展。三維裝箱問題的啟發(fā)式算法大體可分為三種，包括傳統(tǒng)啟發(fā)式算法、元啟發(fā)式算法和啟發(fā)式搜索算法[2]。在傳統(tǒng)啟發(fā)式算法方面，George[3]等人首先提出了基于“層”或“墻”的構(gòu)造性啟發(fā)式算法；Bischoff[4～6]等人在George的基礎(chǔ)上提出了基于“完全層”的啟發(fā)式算法，將二維裝箱問題求解方法應(yīng)用到三維空間。在元啟發(fā)式算法方面，Gehring&Bortfeldt[7,8]提出了一種遺傳算法(GAs)；Bortfeldt[9]等人提出了一種禁忌搜索算法(TSs)；Mark[10]等人提出了一種模擬退火算法(SAs)；Parrefio等人提出了一種貪婪隨機(jī)自適應(yīng)搜索算法(GRASP)；張德富[12]等人提出了一種混合模擬退火算法。在啟發(fā)式搜索算法方面，Pisinger[1]等人基于“垂直層”概念提出了一種分支定界搜索的啟發(fā)式算法； Eley[13]等人提出了基于同構(gòu)塊(相同貨物相同方向組合的塊)的樹搜索的算法，該算法在利用率和穩(wěn)定性方面都取得了不錯(cuò)結(jié)果，將單型單箱優(yōu)化的算法運(yùn)用到解決單型多箱的問題；靳志宏[14]等人在Eley的基礎(chǔ)上，提出了一個(gè)基于預(yù)分配策略的遺傳算法與啟發(fā)式算法相結(jié)合的交互式混合算法，改進(jìn)了多箱異構(gòu)問題的求解效果；Fanslau[2]等人進(jìn)一步拓展了“塊”的概念，提出了“復(fù)合塊”的思想，設(shè)計(jì)了一個(gè)有效的啟發(fā)式樹狀搜索算法； 張德富[15]等人在Fanslau的基礎(chǔ)上，進(jìn)一步擴(kuò)展，提出了一個(gè)多層啟發(fā)式搜索算法，是解決單箱問題當(dāng)前較好的方法。

從現(xiàn)有研究來看，國內(nèi)外學(xué)者在求解單箱異構(gòu)裝箱問題和單型多箱問題上都已經(jīng)得到了比較理想的結(jié)果。就大規(guī)模裝箱實(shí)際應(yīng)用，即多箱異構(gòu)裝箱問題而言，已有的算法還存在著一些問題，如優(yōu)化計(jì)算時(shí)間過長，符合現(xiàn)實(shí)的約束條件較少等問題。

本文在上述研究的基礎(chǔ)上，針對(duì)當(dāng)前求解多箱異構(gòu)裝箱問題上存在的不足，提出了一種基于“塊”和“空間”的概念的啟發(fā)式搜索算法。論文在對(duì)多箱異構(gòu)貨物的三維裝箱優(yōu)化及其7種現(xiàn)實(shí)約束進(jìn)行問題描述基礎(chǔ)上，給出了“塊”和“空間”的基本概念和確定原則；進(jìn)而給出了啟發(fā)式算法的步驟；最后基于開放式標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)的計(jì)算結(jié)果分析比較，說明了算法在時(shí)間效率和體積利用率上均優(yōu)于同類研究；另外，論文還通過一個(gè)現(xiàn)實(shí)約束實(shí)例計(jì)算和所開發(fā)的三維裝箱布局軟件3D可視化顯示，進(jìn)一步驗(yàn)證了算法的理論有效性和重要實(shí)用價(jià)值。

1 問題描述

三維裝箱問題按照貨物種類不同可分為單構(gòu)型和異構(gòu)型裝箱問題，即單種類型貨物裝箱問題和多種類型貨物同時(shí)裝箱問題；按照使用容器數(shù)量不同可分為單箱裝箱和多箱裝箱問題，而多箱裝箱問題又根據(jù)容器的類型不同，可分為單一尺寸類型容器和多種尺寸類型容器。基于實(shí)際應(yīng)用，本文研究單一尺寸類型的多箱異構(gòu)貨物的三維裝箱問題。

本文將裝箱的要求設(shè)定為完全裝載，即不同尺寸不同數(shù)量的貨物完全裝入某一種固定尺寸的容器中，在滿足現(xiàn)實(shí)約束的條件，盡可能實(shí)現(xiàn)使用容器總數(shù)目最小且每個(gè)容器體積利用率盡可能大的目標(biāo)。

大多數(shù)解決裝箱問題的研究僅考慮了貨物方向約束(C1)和穩(wěn)定性約束(C2)[2,4,7,8,9,11,12,15]，文獻(xiàn)[14]在此基礎(chǔ)上考慮了貨物承重級(jí)別約束(C4)、重心約束(C6)以及容器最大載重量和最大容積約束(C7)。本文結(jié)合實(shí)際調(diào)查，引入了以下七種現(xiàn)實(shí)約束條件：

(1)貨物方向約束(C1)。在實(shí)際裝載中，貨物的方向約束可歸納為三種約束，即任意方向旋轉(zhuǎn)，水平旋轉(zhuǎn)，不能旋轉(zhuǎn)。

(2)穩(wěn)定性約束(C2)。貨物必須得到容器底部或其他貨物的完全支撐，不允許懸空。

(3)貨物優(yōu)先級(jí)約束(C3)。異構(gòu)貨物優(yōu)先級(jí)受目的地等因素影響，如不同委托方要求發(fā)送貨物的目的地不盡相同，要保證“先到先下”的原則，先到的貨物優(yōu)先級(jí)越低越后擺放。同構(gòu)貨物優(yōu)先級(jí)受方向影響，如電器行業(yè)，考慮到運(yùn)輸?shù)陌踩?，往往要求貨物盡量先立放，如有剩余空間再考慮側(cè)放或躺放。

(4)貨物承重級(jí)別約束(C4)。承重級(jí)別是設(shè)置貨物的一個(gè)重要指標(biāo)，承重級(jí)別數(shù)值越大承重能力越高。不同貨物疊放時(shí)，應(yīng)考慮貨物的承重能力，避免出現(xiàn)過度擠壓而導(dǎo)致物品損壞的情況，如紙箱只能放在木箱的上面。

(5)貨物最大堆碼層數(shù)約束(C5)?？紤]運(yùn)輸過程中的穩(wěn)定性，要對(duì)貨物允許的最大堆碼層數(shù)限制。貨物最大堆碼層數(shù)是指貨物本身及其上方貨物允許擺放的最大堆碼層數(shù)。

(6)重心約束(C6)。裝載完后，容器重心應(yīng)在容器幾何中心附近，有利于運(yùn)輸過程的穩(wěn)定性。

(7)容器最大載重量、最大容積約束(C7)。容器本身有最大載重量和最大容積的限制，已裝載的貨物的總重量和總體積不能超過這個(gè)限制。

2 “塊”和“空間”的定義和確定原則

一個(gè)實(shí)用的啟發(fā)式搜算算法，不僅要滿足求解結(jié)果盡可能地接近最優(yōu)解，而且要保證較高的搜索速度，即以盡可能短的時(shí)間獲得盡可能優(yōu)化的結(jié)果。為此，我們首先給出“塊”和“空間”的概念，并提出貨物塊的構(gòu)造原則，以及空間的選擇、劃分、合并原則。

2.1 “塊”和“空間”的基本概念

本文采用的坐標(biāo)系為世界坐標(biāo)系，容器的長度方向?yàn)閆軸，寬度方向?yàn)閄軸，高度的方向?yàn)閅軸，容器的左后下方為坐標(biāo)原點(diǎn)。該算法是基于“塊”和“空間”的概念。

“塊”即同構(gòu)塊是指由nx×ny×nz個(gè)相同貨物按照同一個(gè)方向組合的長方體，nx是貨物在X軸方向擺放的數(shù)量，ny是貨物在Y軸方向擺放的數(shù)量，nz是貨物在Z軸方向擺放的數(shù)量?！翱臻g”包括可用空間、備用空間和不可用空間。可用空間是指可以放入至少一種貨物的空間；備用空間是指當(dāng)前不能放入任何一種貨物，但是可以通過合并空間成為可用空間；不可用空間是指下方貨物的承重級(jí)別最低或貨物最大堆碼層數(shù)達(dá)到限制，不能擺放任何貨物時(shí)，此空間為不可用空間?？紤]到上述提到的現(xiàn)實(shí)約束C4和C5，空間除了長、寬、高、左后下方坐標(biāo)的屬性外，需要新增承重級(jí)別和堆碼層數(shù)兩個(gè)屬性，此屬性值標(biāo)記了空間下方已裝載的貨物相應(yīng)屬性。

2.2 貨物塊的構(gòu)造與評(píng)估原則

(1)貨物塊的構(gòu)造原則

設(shè)目標(biāo)容器裝載貨物后的剩余最大載重量為W，目標(biāo)空間在對(duì)應(yīng)坐標(biāo)系上的長度為sx,sy,sz，允許的最大堆碼層數(shù)為l，待裝載貨物i的重量和剩余數(shù)量分別為wi和qi，對(duì)應(yīng)在三維坐標(biāo)方向的尺寸為xi,yi,zi，貨物i的第j種貨物塊在對(duì)應(yīng)坐標(biāo)方向擺放貨物的數(shù)量為nxij,nyij,nzij。貨物塊構(gòu)造時(shí)優(yōu)先考慮y方向，再考慮x方向，最后考慮z方向。這樣組塊的規(guī)則可以避免貨物平鋪，也可以保證貨物按照優(yōu)先級(jí)從高到低的順序從里到外擺放。貨物i的第j種貨物塊在三維坐標(biāo)方向的數(shù)量求解公式如下：

nyij=min{?W/wi」,?sy/yi」,qi,l}

(1)

nxij=min{?W/wi·nyij」,?sx/xi」,?qi/nyij」}

(2)

nzij=min{?W/wi·nyij·nxij」,?sz/zi」,?qi/nyij·nxij」}

(3)

{1≤i≤T,1≤j≤qi}

(4)

則待裝貨物i的第j種貨物塊中貨物的數(shù)量Qij=nyij·nxij·nzij，此貨物塊在對(duì)應(yīng)三維坐標(biāo)系方向的長度為lyij=nyij·yi，lxij=nxij·xi,lzij=nzij·zi,此貨物塊的數(shù)量為bQij=?qi/Qij」，重量為bWij=wi·Qij，如果待裝貨物i仍有剩余，則將剩余數(shù)量的貨物代入上述公式得到新的貨物塊，依次類推待裝貨物i的貨物塊種類大于等于1小于等于貨物的總數(shù)量(1≤j≤qi)。注：符號(hào)“?」”表示為向下取整。

(2)最佳貨物塊評(píng)估原則

啟發(fā)式搜索的原則，就是在可用空間內(nèi)搜索每一個(gè)貨物塊試擺放，制定一種評(píng)估原則，保留效果最佳的貨物塊種類和方向的組合。為了使貨物按照優(yōu)先級(jí)順序從里到外的擺放，以及空間利用率較高的目標(biāo)，優(yōu)先選擇占目標(biāo)空間體積利用率最大的貨物塊擺放，如果貨物塊占目標(biāo)空間體積利用率相同，則優(yōu)先選擇選擇貨物塊在X軸方向尺寸最大的貨物塊擺放，如果貨物塊在X軸方向尺寸相同，則優(yōu)先選擇XZ面的面積利用率較大的貨物塊擺放。

2.3 空間的選擇、劃分與合并的原則

三維裝箱問題是在立體空間內(nèi)裝載貨物的問題，這就必然涉及到如何才能夠有效地利用空間。本文基于空間概念，提出了選擇空間、空間的填充與切割以及合并空間的原則。參照世界坐標(biāo)系，空間的屬性由左后下方的點(diǎn)作為基準(zhǔn)點(diǎn)、各坐標(biāo)軸方向的長度、承重級(jí)別和堆碼層數(shù)組成，表示為Space(sx,sy,sz,slx,sly,slz,sbearlevel,slayer)。

(1)選擇目標(biāo)空間原則

受日常裝箱經(jīng)驗(yàn)的啟發(fā)，貨物擺放依照是從底向上、從里到外、從左到右的擺放原則。因此在選擇目標(biāo)空間時(shí)也應(yīng)遵循實(shí)際裝箱習(xí)慣。在可用空間列表中搜索，優(yōu)先選擇空間位置較高的，即Y軸方向參考點(diǎn)坐標(biāo)sy最大的；如果sy坐標(biāo)相同則優(yōu)先選擇空間位置靠近XY平面的，即Z軸方向參考點(diǎn)sz坐標(biāo)最小的，如果sz坐標(biāo)相同則優(yōu)先選擇在X軸方向參考點(diǎn)sx坐標(biāo)最小的。

(2)空間填充與切割的原則

空間填充在實(shí)際問題中受到C4、C5、C7約束的影響，貨物根據(jù)已選的目標(biāo)空間的容積、承重級(jí)別、堆碼層數(shù)及目前容器的最大載重量的約束限制，生成可填充空間的貨物列表。已裝載貨物的空間沿平行于XY方向的貨物面和平行于YZ方向的貨物面切割成兩部分：“上空間”和“旁空間”，有時(shí)“旁空間”由于貨物塊與目標(biāo)空間的尺寸被切割為“前空間”和“后空間”。根據(jù)空間在XZ面投影面積最大原則，比較Sa1,Sa2,Sb1,Sb2在XZ面的投影面積，選擇面積最大的，并按照其所在方案的切割方法劃分空間，如圖1所示。

圖1 空間切割圖

(3)空間合并的原則

遍歷備用空間列表，找到與待合并空間相鄰的空間，且滿足在Y軸方向坐標(biāo)sy相同，具有共同的邊，合并后的空間至少能放入一種貨物且合并后的空間體積大于待合并的空間，則合并空間。

基于上述貨物塊的構(gòu)造，以及空間的選擇、劃分、合并原則為核心，結(jié)合單一尺寸類型的多箱異構(gòu)貨物的三維裝箱問題，我們給出該問題的啟發(fā)式算法的步驟。

3 啟發(fā)式算法的步驟

基于“塊”和“空間”概念的啟發(fā)式算法主要有以下七步：

Step 1 確定初始待裝貨物清單，選擇容器，選定整個(gè)容器為初始空間，加入可用空間列表，初始空間的基準(zhǔn)點(diǎn)為(0,0,0)，初始允許的堆碼層數(shù)和承重級(jí)別默認(rèn)值為10000。

Step 3 選定第j個(gè)分支，對(duì)第j個(gè)分支的貨物首先生成“垂直條”，再生成“水平帶”，在目標(biāo)空間擺放盡可能多的“水平帶”，保留初始貨物的優(yōu)先級(jí)，記為Priority，更新貨物清單、貨物位置清單等。

Step 4 切割空間，篩選空間，生成可用空間列表和備用空間列表。

Step 5 根據(jù)貨物優(yōu)先級(jí)Priority，貨物的重量、容器剩余最大載重量篩選可裝載貨物清單。如果可用空間列表不為空，仍有可裝載貨物且容器剩余最大載重量大于0，重復(fù)迭代Step 5.1，Step 5.2。否則轉(zhuǎn)到Step 6。

Step 5.1 選擇目標(biāo)空間，并在可裝載的貨物清單中，選擇優(yōu)先級(jí)最高、承重級(jí)別小于目標(biāo)空間的承重級(jí)別且級(jí)別最高的貨物，生成T′個(gè)分支。

Step 5.2 對(duì)T′個(gè)分支按照構(gòu)造貨物塊的原則生成貨物塊，利用貨物塊選擇原則評(píng)估，保留最佳的貨物塊組合和方向。

Step 6 令j=j+1，轉(zhuǎn)到Step 3重復(fù)迭代此過程直至j=T，結(jié)束迭代，保留最佳的重心為最優(yōu)方案，更新待裝貨物清單。

Step 7 如果仍有待裝貨物，且貨物種類及相應(yīng)的數(shù)量是已保留最優(yōu)方案結(jié)果的整數(shù)N倍，則生成與最優(yōu)方案相同的N個(gè)配載結(jié)果，否則轉(zhuǎn)到Step 1重新計(jì)算，直至所有待裝貨物完全裝載為止。

4 實(shí)驗(yàn)與結(jié)果

4.1 與現(xiàn)行研究的比較

本文基于Net Framework 4.0開發(fā)平臺(tái)，在Microsoft Visual Studio 2010環(huán)境下采用C#編程語言實(shí)現(xiàn)了該算法，實(shí)驗(yàn)程序運(yùn)行在處理器為Intel(R) Core(TM)2 Duo CPU E7500 @2.93Ghz的PC機(jī)上，運(yùn)行環(huán)境為Windows 7。我們選取了文獻(xiàn)[1]中的測(cè)試數(shù)據(jù)，共有7大類，每一類選取前50個(gè)算例，共350個(gè)算例，所用集裝箱為國際標(biāo)準(zhǔn)尺寸為587cm×233cm×220cm。許多研究者對(duì)上述算例做過測(cè)試，用來比較的算法包括Elay[13]的兩種算法和靳志宏[14]的混合遺傳算法，分別簡寫為MA1、MA2和HMA，本文基于“塊”的啟發(fā)式搜索算法簡寫為BHSA。比較結(jié)果如表1和表2所示。

從表1可以看出BHSA的算法在使用集裝箱總數(shù)量上比MA2少4個(gè)，比MA1和HMA少1個(gè)，說明BHSA的算法在完全裝載貨物使用總集裝箱數(shù)目更少。由于第6個(gè)容器并未完全裝載，本文選取前5個(gè)集裝箱的平均體積利用率和其他算法比較，如表2所示。從表2中我們不難發(fā)現(xiàn)，BHSA算法在計(jì)算BR1～BR7的算例平均體積利用率均高于MA2和HMA，1號(hào)、2號(hào)、3號(hào)集裝箱的平均利用率均高于MA2和HMA，說明BHSA的算法在集裝箱的體積利用率也優(yōu)于其他算法。除此之外，我們還發(fā)現(xiàn)隨著貨物種類的不斷增多，集裝箱的平均體積利用率也在增大。

表1 本文算法(BHSA)與現(xiàn)行研究(MA1,MA2,HMA)所用集裝箱數(shù)量比較

表2 比較前五個(gè)容器的平均體積利用率(%)

在實(shí)際應(yīng)用中，除了滿足空間利用率最大和使用容器數(shù)目最小的優(yōu)化目標(biāo)外，還要保證優(yōu)化時(shí)間在用戶可接受的范圍，優(yōu)秀的產(chǎn)品必須有良好的用戶體驗(yàn)。比較MA1和MA2算法所用的時(shí)間，此時(shí)間是貨物完全裝載完所需的時(shí)間。如表3所示。從表中數(shù)據(jù)，我們可以看出BHSA算法平均計(jì)算時(shí)間上遠(yuǎn)低于其他算法，最長的平均計(jì)算時(shí)間為202.3s，最短的平均計(jì)算時(shí)間為5.88s。從表1數(shù)據(jù)可以看出，每個(gè)算例至少需要6個(gè)容器，則本算法每個(gè)容器優(yōu)化最長的平均時(shí)間為33s，最短的平均時(shí)間不足1s，在用戶可接受的范圍內(nèi)，有良好的時(shí)間效率和用戶體驗(yàn)。

表3 比較算法MA1、MA2、BHSA計(jì)算BR1～BR7算例的平均時(shí)間(s)

4.2 考慮實(shí)際約束的算例

以考慮實(shí)際約束的算例為例，使用國際標(biāo)準(zhǔn)尺寸為587cm×233cm×220cm的集裝箱，此集裝箱最大載重量為1000kg，完全裝載8種不同尺寸的貨物，共使用4個(gè)容器。貨物的基礎(chǔ)數(shù)據(jù)信息如表4所示。計(jì)算結(jié)果如表5所示，前三個(gè)容器的平均體積利用率為95.41%，由此可以看出該算法不僅滿足了實(shí)際約束條件還保證了較高的容器利用率，該算例4個(gè)容器的裝載結(jié)果如圖2所示。

表4 貨物的基礎(chǔ)數(shù)據(jù)信息

表5 計(jì)算結(jié)果

圖2 算例4個(gè)容器的裝載結(jié)果顯示

5 結(jié)語

針對(duì)七種現(xiàn)實(shí)約束的集裝箱三維多箱異構(gòu)貨物裝載優(yōu)化問題，本文提出了一種基于 “塊”和“空間”的啟發(fā)式搜索算法?；陂_放式標(biāo)準(zhǔn)測(cè)試數(shù)據(jù)的計(jì)算結(jié)果表明，該算法在時(shí)間效率和體積利用率上均優(yōu)于已有同類研究。以該算法為核心，基于Net平臺(tái)和C#開發(fā)了相應(yīng)的3D裝箱布局優(yōu)化可視化軟件，已在大連物流科技有限公司得到推廣應(yīng)用，取得了較好的效果，驗(yàn)證了算法的實(shí)用性。

下一步我們將尋求將算法推廣到異構(gòu)型容器裝載優(yōu)化問題，以及考慮使用容器總費(fèi)用最少等應(yīng)用問題研究中。

[1] Pisinger D. Heuristics for the container loading problem[J]. European Journal of Operational Research, 2002, 141(2): 143-153.

[2] Fanslau T, Bortfeldt A. A tree search algorithm for solving the container loading problem[J]. INFORMS Journal on Computing, 2010, 22(2): 222-235

[3] George J A, Robison D F. A heuristic for packing boxes into a container[J]. Computer and Operational Research, 1980, (7): 147-156

[4] Bischoff E E, Ratcliff B S W. Lssues in the development of approaches to container loading[J]. Omega, 1995, 23(4): 377-390

[5] Bischoff E E, Janetz F, Ratcliff B S W. Loading pallets with non-identical items[J]. European Journal of Operational Research, 1995, 84(3): 681- 692

[6] Bischoff E E. Three-dimensional packing of items with limited load bearing strength[J]. European Journal of Operational Research, 2004, 168(3): 952-966

[7] Gehring H, Bortfeldt A. A genetic algorithm for solving the container loading problem[J]. International Transactions in Operational Research, 1997, 4(4-5): 401- 418

[8] Gehring H, Bortfeldt A. A parallel genetic algorithm for solving the container loading problem[J]. International Transactions in Operational Research, 2002, 9(4): 497-511

[9] Bortfeldt A, Gehring H, Mack D. A parallel tabu search algorithm for solving the container loading problem[J]. Parallel Computing, 2003, 29(5): 641- 662

[10] Mack D, Bortfeldt A, Gehring H. A parallel hybrid local search algorithm for the container loading problem[J]. International Transactions in Operational Research, 2004, 11(5): 511-533

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

[13] Eley Michael. Solving container loading problems by block arrangements[J]. European Journal Operational Research, 2002, 141(2): 393- 409

[14] 靳志宏，蘭輝，郭貝貝.基于現(xiàn)實(shí)約束的集裝箱配載優(yōu)化及可視化[J].系統(tǒng)工程理論與實(shí)踐,2010,30(9):1722-1728

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

Optimization and Visualization of Multiple 3D Container Loading Problem with Non-identical Items

ZHAO Narisa1, HAN Qi-wei1, LIN Zheng-kui2

(1.InstituteofSystemsEngineering,DalianUniversityofTechnology,Dalian116023,China; 2.InformationScienceandTechnologyCollege,DalianMaritimeUniversity,Dalian116026,China)

In order to solve the three-dimensional heterogeneous multiple container loading problems with seven realistic constraints, we propose a heuristic search algorithm based on “block” and “space”. The algorithm uses a tree search strategy, according to the available space, evaluating each cargo block to assess the best one, until no free space or cargo is loaded. The open standards-based test data results show that the algorithm is superior to existing similar studies in time and volume utilization. Furthermore, we develop a 3D visualization loading software, and it has been applied to the logistics business to verify the practicability of the algorithm.

3D container loading problem; heuristic search algorithm; visualization; logistics management

2014- 01-23

國家自然科學(xué)基金資助項(xiàng)目(61072128)和大連市科技計(jì)劃基金資助項(xiàng)目(2013A13GX027)

那日薩(1970-)，男，內(nèi)蒙古烏蘭浩特人，博士，教授，博士生導(dǎo)師，研究方向：電子商務(wù)與物流管理，三維布局優(yōu)化；韓琪瑋(1989-)，女，黑龍江省佳木斯人，碩士研究生，研究方向：電子商務(wù)與物流管理；林正奎(1971-)，男，教授，博士生導(dǎo)師，研究方向：商務(wù)智能。

U169

A

1007-3221(2015)04- 0076- 07