基于復(fù)雜約束的多個(gè)集裝箱配載優(yōu)化問題研究

陸 華 趙 琨

(北京物資學(xué)院物流學(xué)院 北京 101149)

基于復(fù)雜約束的多個(gè)集裝箱配載優(yōu)化問題研究

陸 華 趙 琨

(北京物資學(xué)院物流學(xué)院 北京 101149)

根據(jù)集裝箱配載問題中現(xiàn)實(shí)存在的多個(gè)制約因素，構(gòu)建了多個(gè)集裝箱配載優(yōu)化模型.為尋求最優(yōu)解，設(shè)計(jì)了以預(yù)分配策略為原則的遺傳算法和啟發(fā)式算法交互進(jìn)行的混合算法.通過算例驗(yàn)證和比較得出，該模型算法在滿足集裝箱重心要求、下層貨物額定承重能力，以及貨物混裝限制等約束條件下，可得到較高集裝箱容積利用率的配載方案.

多個(gè)集裝箱配載；遺傳算法；啟發(fā)式算法；復(fù)雜約束

0 引 言

集裝箱配載效率是集裝箱多式聯(lián)運(yùn)運(yùn)行的一個(gè)重要指標(biāo)，是指將典型形狀的貨物(通常為長(zhǎng)方體或立方體，例如，各種紙箱)如何在集裝箱內(nèi)部擺列實(shí)現(xiàn)空間利用優(yōu)化的問題，也就是探尋如何優(yōu)化立體貨物在集裝箱內(nèi)部的擺放布置，實(shí)現(xiàn)將所有貨物配載完畢后，所使用的集裝箱數(shù)量最少.

配載問題根據(jù)需配裝的集裝箱數(shù)目的多少可以劃分為單個(gè)集裝箱和多個(gè)集裝箱配載問題.單箱布局優(yōu)化方法有啟發(fā)式方法、數(shù)學(xué)規(guī)劃、圖論法、遺傳算法、模擬退火法等方法.George 等[1]利用構(gòu)造型啟發(fā)式算法來研究集裝箱配載問題，首次提出“層”的概念.Pisinger[2]也根據(jù)“層”的概念提出了一種啟發(fā)式算法，將集裝箱內(nèi)部空間劃分成幾個(gè)垂直的列，然后將列分成幾個(gè)水平的層，合適的列寬和層深利用分支定界法得到，這種設(shè)計(jì)的配裝方式可以獲得較高的集裝箱利用率，然而貨物穩(wěn)定性卻較低，往往上層貨物得不到下層貨物的全面支撐.Loe等[3]對(duì)裝載的貨物以“層”的狀態(tài)出現(xiàn)，也就是從下至上實(shí)現(xiàn)裝箱工作，為了達(dá)到平坦的“層”面，該算法根據(jù)適箱貨物的高度設(shè)立裝載的優(yōu)先級(jí)別.姜義東等[4]采用三叉樹的數(shù)據(jù)結(jié)構(gòu)來構(gòu)思集裝箱內(nèi)部空間布局的優(yōu)化算法，其將體積大的貨物給予優(yōu)先級(jí)，依次放入集裝箱，這樣處理空間導(dǎo)致產(chǎn)生較為零碎的狹長(zhǎng)部分，降低空間利用率，但算法較為簡(jiǎn)單減少?gòu)?fù)雜性.

針對(duì)集裝箱多箱配裝問題，Bortfeklt[5]論述了多種形狀貨物組合的連續(xù)性配裝設(shè)計(jì)，但采用該設(shè)計(jì)常常導(dǎo)致體積大的物品留在最后放置，因而集裝箱內(nèi)部空間利用率較低.Eley[6]設(shè)計(jì)了多個(gè)集裝箱同時(shí)裝載方案，利用單箱裝載方案解決多箱裝載問題，該算法在強(qiáng)異類貨物的裝載問題得到較大改善，得到較高的集裝箱內(nèi)部空間利用率，在貨物裝載穩(wěn)定性上不錯(cuò).Terno等[7]采用預(yù)分配原則，在分支定界概念和啟發(fā)式方法的基礎(chǔ)上進(jìn)行優(yōu)化，首先采用貪婪算法得到初始解，之后逐步迭代優(yōu)化.

文中將啟發(fā)式算法和預(yù)分配原則的遺傳算法相結(jié)合，設(shè)計(jì)一種2種算法交互進(jìn)行的算法，該算法加入了現(xiàn)實(shí)裝載中應(yīng)考慮的下層貨物承載能力、集裝箱重心配置和不同貨物混裝問題.根據(jù)數(shù)值測(cè)試表明，該算法較好的解決了實(shí)際中問題，獲得較好的集裝箱內(nèi)部空間利用率.

1 集裝箱配載模型及求解算法

1.1 研究對(duì)象及約束條件

文中的研究對(duì)象是多箱配裝問題，以國(guó)際標(biāo)準(zhǔn)集裝箱為配裝箱型，將已經(jīng)界定的不同種類和不同大小的貨物裝入多個(gè)集裝箱，通過算法設(shè)計(jì)貨物的配載優(yōu)化布局，使得在滿足多項(xiàng)約束條件的前提下，使用最少的集裝箱數(shù)量.

在實(shí)際的集裝箱配載中，需要考慮約束條件如下：(1)在實(shí)際的裝箱操作中，很多貨物不能倒置，本算法要求貨物不能倒置；(2)單件貨物的體積不能超過集裝箱的界限限制；(3)裝入貨物的總重量小于或等于集裝箱的額定載重量；(4)貨物裝載必須有足夠的支撐，不能懸空，必須放在其他貨物的上方；(5)為了確保裝卸過程的穩(wěn)定性，要求配裝完畢后的集裝箱重心在合理的范圍內(nèi)；(6)考慮不同貨物不能混裝的問題，本算法設(shè)計(jì)了配裝隔離約束，也就是限制貨物的混裝，例如，不同化學(xué)用品不能混裝；(7)每件貨物都有一定的承重能力，因此，需要考慮貨物承重能力的約束，也就是上層貨物的總質(zhì)量不能超過下層貨物的承重能力.

1.2 假設(shè)條件

由于實(shí)際問題非常復(fù)雜，為了避免不必要的復(fù)雜性，文中做出以下假設(shè)：(1)所裝貨物都是長(zhǎng)方體或立方體；(2)貨物的重心和其他幾個(gè)中心一致；(3)貨物中途不會(huì)出現(xiàn)掏箱問題；(4)貨物裝載過程中不會(huì)出現(xiàn)變形.

2 構(gòu)建模型

2.1 符號(hào)說明

將貨物和集裝箱放置于笛卡爾三維坐標(biāo)系中，坐標(biāo)系中X軸正向方向?yàn)榧b箱的長(zhǎng)度方向，Y軸正向方向?yàn)榧b箱的寬度方向，Z軸正向方向?yàn)榧b箱的高度方向，集裝箱左后角位于坐標(biāo)系的原點(diǎn)上(0,0,0)見圖1.

圖1 集裝箱坐標(biāo)示意圖

2.2 目標(biāo)函數(shù)與現(xiàn)實(shí)約束條件

優(yōu)化目標(biāo)為最小化集裝箱的使用數(shù)量，則目標(biāo)函數(shù)可以表示為

(1)

約束條件：

?i=1,2,…,n

(2)

(3)

式中：

spj=[(xbj-xaj+xbp-xap)-

(max{xbp,xaj}-min{xap,xaj})]×

[(ybj-yaj+ybp-yap)-(max{ybp,ybj}-

min{yap,yaj})]

(4)

xlp≤xlj,xbp≥xbj,yap≤yaj,

max{xbp,xbj}-min{xap,xaj}<

xbj-xaj+xbp-xap,

max{ybp,ybj}-min{yap,ybj}<

ybj-yaj+ybp-yap}

(5)

i=1,2,…,N}

(6)

[(xbj-xaj)-lj][(ybj-yaj)-wj]=0,

?j∈{Xij=1,i=1,2,…,N}

(7)

minxaj≥0;minyaj≥0;minzaj≥0,

(8)

maxxbj≥0;maxybj≥0;maxzbj≥0,

(9)

(10)

XjkXik(1-rij)=0,

?k∈1,2,…,N;?j∈1,2,…,n

(11)

?i∈1,2,…,N

(12)

?i∈1,2,…,N

(13)

?i∈1,2,…,N

(14)

?j=1,2,…,n

(15)

式中：

yai≥ya2,xbi≤xbj,ybi≤ybj}

(16)

min{xaq,xaj}

max{ybq,ybj}-min{yaq,yaj}

ybq-yaq},?k∈1,2,…,N

(17)

上述模型中，式(2)為貨物都務(wù)必全部裝入到集裝箱；式(4)為箱內(nèi)上下兩層相鄰貨物之間的重合面積；式(5)為箱內(nèi)上下兩層相鄰貨物重合情況由完全重合和部分重合組成；式(3)～(5)組合為貨物必須完全放在下一層貨物的上面，不存在懸空放置的情況；式(6)為所有貨物不能上下顛倒放置；式(7)為貨物的放置與集裝箱內(nèi)部長(zhǎng)度或?qū)挾确较虼怪被蚱叫?；?8)～(9)為全部貨物的體積小于或等于集裝箱內(nèi)部容積界限；式(10)為箱內(nèi)貨物總重小于或等于集裝箱額定載重量；式(11)為不能混裝的貨物不能裝載在一起，需要滿足貨物隔離限制；式(12)～(14)為裝載完畢后集裝箱的重心位置應(yīng)在要求范圍內(nèi)；式(15)為集裝箱內(nèi)上下兩層相鄰貨物的由完全重合和部分重合兩種形式構(gòu)成；式(16)～(17)為上下貨物中，上層所有貨物總重不能超過下層貨物所能承受的最大重量.

3 混合算法設(shè)計(jì)

由于該問題實(shí)際約束較為復(fù)雜，文中結(jié)合采用遺傳算法預(yù)啟發(fā)式算法相結(jié)合交互式的混合算法.首先，利用遺傳算法具有全局搜索能力做出集裝箱配載的預(yù)分配，再使用啟發(fā)式算法進(jìn)行迭代，產(chǎn)生不同的集裝箱配載方案，2個(gè)算法交替進(jìn)行優(yōu)化.算法設(shè)計(jì)流程見圖2.

圖2 遺傳算法預(yù)啟發(fā)式算法的交互設(shè)計(jì)流程圖

該算法結(jié)合了遺傳算法和啟發(fā)式算法的優(yōu)點(diǎn)，算法效率較高，可以實(shí)現(xiàn)較高的集裝箱內(nèi)部空間利用率，同時(shí)還考慮在裝卸過程中集裝箱的重心要求、避免貨物承受過重載荷造成貨損以及不同貨物不能混載的要求.算法主要參數(shù)取值如下：遺傳算法群體規(guī)模數(shù)為50，最大迭代代數(shù)為350，變異操作次數(shù)取100，交叉概率為0.95，變異概率為0.01.

4 算法評(píng)價(jià)

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

為了對(duì)設(shè)計(jì)的遺傳和啟發(fā)式結(jié)合的混合式算法進(jìn)行檢驗(yàn)，文中采用OR-LIBRARY的基準(zhǔn)測(cè)試問題來評(píng)判[8].標(biāo)準(zhǔn)算例借鑒Bischoff等[9-10]所采用的算例，共7大類，每一類有50個(gè)算例.所用集裝箱為20 ft國(guó)際標(biāo)準(zhǔn)集裝箱，尺寸為5.898 m×2.352 m×2.385 m.文中采用目前取得較好效果的Elay的2種算法，用EL1和EL2表示，文中設(shè)計(jì)算法用YQ表示.

現(xiàn)有的研究資料表明，目前對(duì)于集裝箱內(nèi)裝載優(yōu)化問題主要考慮集裝箱內(nèi)容積限制，對(duì)于集裝箱內(nèi)部貨物承重限額、集裝箱吊裝重心要求缺乏考慮.文中設(shè)計(jì)的優(yōu)化模型的優(yōu)點(diǎn)在于，不僅考慮貨物的體積，還考慮貨物在集裝箱內(nèi)的承重限額、貨物混載限制及重心穩(wěn)性要求等約束條件.

關(guān)于啟發(fā)式-變異算法的參數(shù)比較結(jié)果見表1～2.

表1 交互式混合算法與目前應(yīng)用算法的結(jié)果比較(所需集裝箱個(gè)數(shù))

算例序號(hào)EL1EL2YQSL(3)302305302SL(6)305307303SL(7)301302301SL(9)303304303算例序號(hào)EL1EL2YQSL(11)301303301SL(14)300302301SL(19)305307304合計(jì)211721302115

注釋：括號(hào)()內(nèi)的數(shù)字是該算例中貨物的種類數(shù)目

由表1的7個(gè)算例可知，文中算法YQ和算法EL2相比，使用集裝箱數(shù)量較少，YQ與算法EL1相比，不多于EL1所使用的集裝箱數(shù)量.由表2可知，YQ的前5個(gè)集裝箱容積平均利用率比EL1更加平均，并且對(duì)7個(gè)算例總體來看，YQ的集裝箱內(nèi)部容積利用率的平均值均大于算法EL1，表明文中設(shè)計(jì)算法在充分利用集裝箱內(nèi)部容積上取得較好的效果.

表2 文中設(shè)計(jì)算法(YQ)與算法EL1的集裝箱配載容積利用率比較

4.2 2種分配原則的比較

由于根據(jù)目前研究資料缺乏對(duì)貨物承載限額、貨物混裝限制及集裝箱重心位置要求的研究，因此無法做出這方面的比較.目前較為常用的連續(xù)性分配策略，而文中采用遺傳算法進(jìn)行貨物裝載的預(yù)分配策略，因此，對(duì)不同分配策略進(jìn)行比較，結(jié)果見表3.由表3可知，預(yù)分配策略的集裝箱內(nèi)容容積利用率(91.60%)略高于連續(xù)性策略取得結(jié)果(91.00%).主要原因在于，采用遺傳算法進(jìn)行預(yù)分配，而遺傳算法具有全局搜索優(yōu)化能力；其次是啟發(fā)式算法與遺傳式算法的交互進(jìn)行，也就是將單個(gè)集裝箱配載的結(jié)果與多個(gè)集裝箱配載的結(jié)果進(jìn)行再次平衡優(yōu)化.

表3 連續(xù)分配原則與預(yù)分配原則的集裝箱利用率 %

5 結(jié) 束 語

研究了在實(shí)際復(fù)雜的約束限制下，多個(gè)集裝箱內(nèi)部配載優(yōu)化問題，對(duì)集裝箱重心要求、下層貨物承重能力、不同貨物混載限制等多個(gè)實(shí)際因素進(jìn)行考慮，構(gòu)建了多個(gè)集裝箱配載的混合整數(shù)規(guī)劃模型，在模型算法上設(shè)計(jì)了預(yù)分配原則，將遺傳算法和啟發(fā)式算法相結(jié)合進(jìn)行交互式計(jì)算的混合算法.通過算例測(cè)試，與目前流行算法相比，文中算法取得了較好的集裝箱配載效果，使的集裝箱容積平均利用率較高，使用集裝箱數(shù)量較少.不足之處，在于沒有考慮其他典型形狀的貨物，例如卷盤狀，桶裝貨物和托盤等貨物，以及中途掏箱的情況也未考慮.

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

[2]PISINGER D. Heuristics for the container loading problem[J]. European Journal of Operational Research,2002,141:382-92.

[3]lOE T H, NEE A Y C. A packing algorithm for hexahedral boxes[C]. Proceeding of the Conference of Industrial Automation, Singapore,1992:115-126.

[4]姜義東，查建中，何大勇.集裝箱裝載矩形貨物的布局研究[J].鐵道學(xué)報(bào)，2000,22(6):13-18.

[5]BORTFELDT A. Heuristik fuer multiple container lade probleme[J]. Or Spektrum,2000,22(2):239-262.

[6]ELEY M. Solving container loading problems by block arrangement[J]. European Journal of Operational Research,2002,141:393-409.

[7]TERNO J, SCHEITHAUER G, SOMMERWEIU U, et al. An efficient approach for the multi-pallet loading problem[J]. European Journal of Operational Research,2000,123:372-381

[8]BEASLEY J E. OR-library: distributing test problems by electronic mail[J]. Journal of Operation Research Society,1990,41(11):1069-1072.

[9]BISCHOFF E E, RATCLI M S W. Issues in the development of approaches to container loading[J]. Omega,1995,23(4):377-390.

[10]JIN Z H, ITO T, OHNO K. The threo-dimensional bin packing problem and its practical algorithm[J]. International Journal of Japan Society of Mechanical Engineers,2003,46(1):60-66.

Optimization of the Multi-containers Loading Problems Based on Complex Constraints

LU Hua ZHAO Kun

(LogisticsSchool,BeijingWuziUniversity,Beijing101149,China)

According to the multiple constraints existing in the actual container loading problem, the paper establishes multiple containers loading optimization of mixed integer programming model. In order to obtain the optimal solution, the paper designs a hybrid algorithm based on genetic algorithm and heuristic algorithm, which is based on the principle of pre-allocation strategy. Through the example verification and comparison, the model algorithm satisfies the constraints, the focus of container goods and mixed goods bearing capacity constraints, can obtain higher utilization ratio of the volume of container stowage solution.

multiple containers loading; genetic algorithm; heuristic algorithm; complex constraints

2016-11-03

U169

10.3963/j.issn.2095-3844.2016.06.023

陸華(1977—):女，博士，主要研究領(lǐng)域?yàn)檫\(yùn)輸與物流