帶平衡約束三維裝箱問題的雙層混合遺傳算法

朱 向，雷定猷

（1.湖南涉外經(jīng)濟學院管理學院，長沙 410205；2.中南大學交通運輸工程學院，長沙 410075）

帶平衡約束三維裝箱問題的雙層混合遺傳算法

朱 向*1,2，雷定猷2

（1.湖南涉外經(jīng)濟學院管理學院，長沙 410205；2.中南大學交通運輸工程學院，長沙 410075）

針對帶重心平衡約束的三維裝箱問題，基于框架式布局思想，設計雙層混合遺傳算法進行求解.根據(jù)裝載物的特性定義核心貨物元素及進行核心堆的構(gòu)造，再結(jié)合極點、錨距等概念提出適合貨物平衡裝載的布局過程；在典型布局形成初始框架基礎(chǔ)上，通過雙層混合遺傳算法的內(nèi)、外層搜索分工與協(xié)作，獲得貨物最優(yōu)裝載方案.基于標準算例的實驗及對比分析，證明所提出方法在提高裝載率及實現(xiàn)重心平衡方面取得了較好效果.

物流工程；三維裝箱；平衡約束；雙層混合遺傳算法；框架式布局

1 引言

帶平衡約束三維裝箱問題是指選擇一定數(shù)量、不同規(guī)格和質(zhì)量的貨物裝入某集裝箱內(nèi)，在滿足載重量及空間關(guān)系等約束條件下，使裝入箱內(nèi)貨物和重心位于或接近于規(guī)定位置并達到裝載率最大的目的.它屬于裝載優(yōu)化研究和鐵路、航空等貨物裝運實踐中的重要問題，對于保障裝卸運輸中的貨物及設備安全、提升相關(guān)作業(yè)效率和減少運輸中能源消耗都有積極意義.

一般裝載布局問題屬于NP難問題[1]，帶平衡約束的三維裝箱問題則更具復雜組合優(yōu)化問題特點，目前已有一批學者對此進行了研究.Bischoff[2]、Gehring[3]、Davies[4]和Eley[5]等分別基于墻（wall）、塔（tower）、條帶（stripings）、層（layers）及塊（blocks）等貨物聚集方式，采用“鋪層”、“砌墻”等方法實施裝載，并以隨機方式實現(xiàn)層和塊等單元位置的變換來實現(xiàn)重心調(diào)整的目的；Egeblad針對具有平衡和慣性力矩約束的不規(guī)則物體的裝載問題，建立以重疊區(qū)域與不平衡量之和最小為目標的函數(shù)[6]；Baldi[7]將空運裝載當作三維背包問題進行處理，建立了包含平衡約束及最大化貨物價值量的模型.國內(nèi)關(guān)于平衡裝載布局方面的研究相對較少，Liu設計了混合禁忌搜索求解考慮平衡與穩(wěn)定性約束的貨物裝載問題[8]；Lim針對道路貨運關(guān)于超載方面規(guī)定，研究了包含軸重約束卡車裝箱問題[9]；雷定猷針對鐵路貨物裝載建立包含重心約束貨物裝載模型，并提出基于核心骨架布局及重心平移方法[10].

2 問題的描述及數(shù)學模型

2.1 問題描述

帶平衡約束三維裝箱問題是指從多件貨物中選擇若干件，按照一定的方式組合且以正交方式裝入一個矩形集裝箱內(nèi)，要求在貨物互不干涉與不超出箱子邊界的前提下,最大化箱子的空間及承載能力利用，同時實現(xiàn)整體裝載重心平衡.貨物屬于矩形、勻質(zhì)類物品，具有相應尺寸與質(zhì)量，擺放方向設定為可任意旋轉(zhuǎn)，可最多包含6種方向；裝載所用箱子具有相應容積與載重量限定.

2.2 數(shù)學模型

P=｛P1，P2，…，PN｝=｛pij|pij∈Pi，i=1，2，…，N，j=1，2，…，nN｝——N類貨物集合；

qij、vij、aij、bij、hij——以某方向裝載貨物 pij的重量、體積和沿三坐標軸方向長度值；

uij——若貨物 pij已裝車取1，否則取0.

以箱子左后下角為原點、底板為X-Y平面，建立空間直角坐標系：Y軸平行箱子縱中心線，方向從左向右；X軸沿箱端，方向從后向前；Z軸垂直底平面向上.

設貨物 pij裝載后重心坐標為其中分別為貨物重心到Y(jié)Z平面、XZ平面和XY平面的距離，則裝載貨物合重心坐標為設箱子底板中心坐標為（C1，C2，0），橫向容許偏移量為Δ1（≥0），縱向容許偏移量為Δ2（≥0），全部貨物總重心高不超過Δ3（≥0）.根據(jù)上述設定，建立如下貨物平衡裝載模型：

式（1）為最大化箱子空間利用率、載重利用率及裝載重心平衡度三部分目標，其中為裝載重心偏離理想位置（箱子底板中心）距離，權(quán)重系數(shù)α，β，λ為常數(shù)，根據(jù)裝載對象的密度性質(zhì)選?。皇剑?）-式（4）表示裝載貨物不超出箱子邊界；式（5）-式（7）表示貨物間互不重疊；式（8）-式（10）為裝載重心約束；式（11）為箱子載重量約束；式（13）為裝載貨物總數(shù)約束.

3 算法設計

3.1 算法思想

對帶平衡約束三維裝箱這類復雜組合優(yōu)化問題，一般借助啟發(fā)式方法求解，框架式布局方法屬于這一范疇.它假設在平衡裝載效果好的布局方案中，有若干稱之為核心堆且對全局重心平衡起調(diào)控作用的貨物單元（如圖1中虛線所圍區(qū)域），裝載時若能先將這些核心堆確定下來并以此形成布局框架，將使問題簡化.該方法遵循空間內(nèi)物品平衡分布規(guī)律，即一個布局方案的平衡水平往往由部分起主導作用的貨物及其分布決定.著眼于核心物件的布局，考慮貨物與空間匹配關(guān)系，逐步添加剩余物品，可提高貨物的裝載效率.

圖1 核心堆分布示意圖Fig.1 An example of the distribution of the core stacks

采用框架式布局法需解決核心堆的貨物類別、貨物組合形式、核心堆的個數(shù)及其在箱中分布位置等問題.本文通過設計雙層混合遺傳算法（Bilevel hybrid genetic algorithm,BHGA），可實現(xiàn)上述目標并達到高效裝載目的.算法分為初始裝載序列生成與最優(yōu)解搜索兩階段：通過構(gòu)造核心堆及實施典型布局，形成問題初始求解框架；通過雙層遺傳算法的分工和協(xié)作搜索，構(gòu)建多樣化核心框架，進而獲得最佳布局方案.

3.2 初始裝載序列生成

3.2.1 核心堆構(gòu)造

Qi——第i類貨物的重量和；

Q0——核心堆重量上限值；

ε——重量控制參數(shù)；

3.2.2 構(gòu)造裝載法

BHGA基于預先確定貨物序列(ps)選擇裝載對象，再結(jié)合構(gòu)造法來完成裝載.結(jié)合極點（Extreme Points,EPs）概念[11]，設計基于啟發(fā)式規(guī)

Mc、Nc——核心堆中元素最大和最小棱長；

Lh、Wh、Hh、Ll、Wl和 Hl——分別為核心堆外接長方體三棱長的上限和下限；

γ1、γ2——長、寬尺寸調(diào)控參數(shù)；

φ0——相似度閾值.

按照下列算法構(gòu)造核心堆：則的構(gòu)造法進行布局.

極點是指裝載過程中用于表示放置貨物的位置，對處于初始待裝狀態(tài)的空箱，其底部四個角為四個初始極點.當長、寬和高分別為lk、wk和hk貨物k放置于坐標為（xk，yk，zk）的箱子左后下角位置時，將產(chǎn)生多個可用于放置貨物的新的極點，它們是由坐標為（ xk+lk，yk，zk）、（ xk，yk+wk，zk）和（xk，yk，zk+hk）的點垂直投影到箱壁或鄰近貨物上形成（圖2）.

圖2 極點示意圖Fig.2 An example of the Extreme Points

為實現(xiàn)重心平衡，本文按照錨距最小原則來選擇.裝載空間角與其對應箱角之間的距離稱為錨距，選擇最小錨距對應極點裝載貨物，將使零碎空間集中在箱子中間，并實現(xiàn)箱內(nèi)貨物均衡分布.

若裝載過程中某一極點無法放入當前貨物，則考慮極點序列中下一個極點；若找不到對應極點，則暫時放棄該貨物，選擇裝載序列中下一個對象，后續(xù)裝載優(yōu)先考慮未裝貨物.每完成一次貨物裝入，按規(guī)則對極點與貨物序列進行更新，直至貨物全部裝入或箱子不能裝入為止.構(gòu)造裝載算法如下：

Step 1輸入貨物序列Itemlist={序列對應的核心堆及單件貨物}，初始化極點序列EPlist={箱子四個底角}及布局方案plan=｛｝,令貨物初始編號為l=1.

Step 2計算EPlist中極點個數(shù)M，令極點初始編號為m=1.

Step 3從 Itemlist中取出第 l個貨物，從EPlist中選出第m個極點.

Step 4若貨物可放入指定空間，則按序列指定方向放入，令 plan=plan+（space，item），更新Itemlist和EPlist；否則，若m＜M，令m=m+1，考慮EPlist中下一位置.

Step 5若貨物未能裝入且Itemlist≠｛｝，令l=l+1，m=1轉(zhuǎn)Step3；否則當Itemlist≠｛｝時，令l=l+1，轉(zhuǎn)Step2.

Step 6計算裝載方案目標函數(shù)適應值value=value（plan）.

Step 7輸出裝載方案及其適應值 plan與value.

3.2.3 初始序列生成

為獲得BHGA算法運行所需初始序列，基于構(gòu)造核心堆結(jié)合平衡布局原理，將核心堆定位于箱子底部且箱角或箱子中間等典型位置，形成若干裝載方案并確定對應裝載序列.

圖3為由兩個核心堆構(gòu)成的貨物單元的幾種典型布局形式，其中，核心堆定位于箱角（圖3（a）與圖3（b）），其編碼相應處于序列中靠前的位置，核心堆位于箱子中間（圖3（c）與圖3（d）），其編碼處在序列中相對中間的位置.為實現(xiàn)平衡裝載目標，重量相等或接近的核心堆盡量布置為對稱形式，其在裝載序列中的位置相互連接或靠近.

圖3 兩個核心堆布局Fig.3 An example of the loading of two core stacks

3.3 最優(yōu)解搜索

最優(yōu)核心堆組合及其分布位置通過BHGA算法的雙層搜索機制確定（圖4）：典型布局序列加上隨機生成序列（圖4中A′1，A′2…）輸入內(nèi)層算法，搜索各核心堆組合最佳布局位置對應序列（圖4中A1，A2，A3…）；將內(nèi)層搜索部分較優(yōu)序列加上全部貨物隨機序列作為初始編碼（圖4中B1，B2，B3…）輸入外層搜索，搜索新的布局方案及其序列（圖4中B′1，B′2…）.以新解為基礎(chǔ)重構(gòu)框架，并將其輸入內(nèi)層算法作新一輪優(yōu)化，直至終止條件滿足.

圖4 雙層算法運行示意圖Fig.4 The process of the running of BHGA

3.3.1 內(nèi)層搜索

內(nèi)層搜索用遺傳算法對核心堆與單件貨物進行演化，以搜索各核心堆組合下貨物最佳布局位置.如圖5所示，其編碼對象為核心堆和單件貨物.每個染色體由一個二維數(shù)組表示：一個數(shù)組表示各階段裝載的貨物類別，其中為核心堆（數(shù)量為nt），其他為單件貨物（總類數(shù)為Kt，每類件數(shù)為Nt），總的基因數(shù)為；另一數(shù)組表示放置方向，由于每件貨物最多包含6種放置方向，數(shù)組取值范圍為[0,5].

圖5 內(nèi)層算法的基因編碼Fig.5 An example of the gene coding

偏隨機密鑰遺傳算法[12]（Biased random-key genetic algorithm,BRKGA）能在繼承優(yōu)秀基因前提下，有效避免早熟現(xiàn)象，用其進行裝載序列演化.

Setp 1輸入人工布局或外層搜索方案對應序列，設種群規(guī)模Qn，選擇比例Ps、交叉概率Pc與變異概率Pm，雙層搜索次數(shù)初值g=0，最大次數(shù)為Gn.

Setp 2隨機生成兩組密鑰值K1，K2，K1以升序排列并將其賦予各序列貨物，將K2直接賦予序列貨物，兩部分序列一起組成初始種群.

Setp 3若g=Gn,轉(zhuǎn)setp7,否則結(jié)合裝載過程算法進行解碼，并計算全部個體綜合目標函數(shù)值：F（θ）=α?VU（θ）+β?WL（θ）+λWCG（θ）.VU（θ）、WL（θ）和WCG（θ）分別為體積利用率、載荷利用率及重心偏離度，按適應值大小將種群中個體降序排列.

Setp 4按選擇比例Ps，復制精英個體進入下一代.

Setp 5隨機生成新一組密鑰值K3，將被復制的精英個體作為一方，隨機選擇其他非精英個體與其交叉操作，當密鑰值小于Pc時，從精英個體中選取基因位，否則從隨機個體中選擇基因位，組成Qn?Pc個新的交叉?zhèn)€體.

Setp 6從非精英個體中隨機選擇Qn?Pm個體作為變異體，與復制及交叉?zhèn)€體一起構(gòu)成新一代種群，轉(zhuǎn)Setp3.

Setp 7輸出各核心堆組合的優(yōu)化布局方案及目標函數(shù)值.

3.3.2 外層搜索

外層搜索以單件貨物為編碼對象，以空間利用率最大化為目標，借助BRKGA算法實現(xiàn)全局搜索.對內(nèi)層搜索提供初始序列，將其中包含的核心堆還原為單件貨物形式，再進行編碼.核心堆的構(gòu)造類似于對一個小型空間的裝載，即以一定的方向聚集貨物，可由貨物裝載參考角與核心堆裝載極點間距離和其聚集方向確定編碼（圖6）.

圖6 基因編碼還原Fig.6 An example of the gene reduction

外層搜索的解結(jié)合構(gòu)造法進行解碼，以確定是否存在裝載率更優(yōu)的組合形式.若存在這樣的解，從中選取若干個，結(jié)合之前確定的核心元素，考慮與之關(guān)聯(lián)的貨物間匹配狀況（利用相似度指標φ0），從對應裝載模式中提取外形規(guī)整且包含核心元素的單元，以此作為新的核心堆構(gòu)造布局框架.為適應后續(xù)內(nèi)層搜索編碼要求，按圖6相反的過程進行基因合并，使多個貨物基因合并為核心堆一個基因，其方向編碼參照單件貨物放置方向規(guī)定.新產(chǎn)生的序列結(jié)合隨機生成序列輸入內(nèi)層算法，以搜索出新的平衡布局方案.

按上述過程運行雙層算法，直至終止條件（雙層算法最大循環(huán)次數(shù)Gt）滿足，將最終優(yōu)化結(jié)果輸出.

4 實例分析

裝載物品取自裝箱研究中標準算例[2,4]，由包含不同類型與數(shù)量的物品的裝載例集BF1-BF15組成.使用長587 cm、寬233 cm和高220 cm的ISO-20 ft標準集裝箱作為裝載容器，規(guī)定其最大載重量為22 t.確定內(nèi)外層算法與核心堆構(gòu)造的參數(shù)如表1所示.

表1 實驗參數(shù)Table 1 Configuration in computational experiments

由于目前對平衡裝載問題的研究還不充分，相關(guān)實驗對比的基礎(chǔ)仍較缺乏，選取裝箱研究中涉及重心平衡因素的五種主要方法與BHGA算法作對比，分別是文獻[2]-文獻[5]、文獻[8]中的H_BR、GA_GB、C_DB、TRS_E、HTS_L算法.在對標準算例的實驗中，除文獻[4]方法提供考慮重心平衡時空間利用率外，其他四種方法只有不考慮重心因素時的結(jié)果.按照文獻[4]規(guī)定：物品分輕與重兩類，從密度值為0.01-0.05 g/cm3和0.96-1.00 g/cm3區(qū)間以均勻一致抽樣生成；重心偏離條件為Δ1=35cm，Δ2=11cm，Δ3=0；權(quán)重α=0.6，β=0，λ=0.4.用BHGA算法計算各算例在考慮重心平衡時平均最優(yōu)裝載率，幾種方法在考慮和不考慮重心平衡時的平均裝載率分別如表2所示.

表2 幾種方法平均裝載率對比Table 2 Comparison of the average volume utilizations for several approaches (%)

在考慮重心平衡時，BHGA的裝載率明顯高于文獻[4]方法的結(jié)果；而與其他幾種未包含重心平衡因素考慮的方法相比，該結(jié)果也處于較好水平.另外，從BHGA算法與C_DB算法分別針對強、弱兩組算例的實驗結(jié)果看，BHGA算法在求解強差異型物品裝載問題時的效果更為明顯.

在裝載重心平衡方面，C_DB通過實驗說明了貨物位置變換對重心分布改進的效果，但未列舉重心偏移的具體數(shù)值，只說明了全部算例縱向偏離距離(DCG)在35 cm以內(nèi)，橫向DCG最好結(jié)果為2.5 cm；BHGA和C_DB的對比結(jié)果如表3所示，全部算例縱向DCG小于25 cm，橫向最好DCG為1.2 cm，各算例組平均重心偏離理想位置距離小于20 cm，說明算法在平衡布局方面取得較好效果.

表3 重心偏離情況對比Table 3 Comparison of the DCGs for two approaches

5 研究結(jié)論

針對帶重心平衡約束三維裝箱問題，基于框架式布局思想，設計了雙層混合遺傳算法進行優(yōu)化布局.根據(jù)裝載對象特征，進行核心堆構(gòu)造及初始布局；結(jié)合極點法、錨距等概念提出貨物平衡裝載的啟發(fā)構(gòu)造法；對內(nèi)、外層搜索算法在初始解構(gòu)造、裝載序列編碼、遺傳操作等方面進行設計；通過標準算例證明算法在提高裝載率與實現(xiàn)重心均衡等方面可取得較好的效果.

［1］ Pisinger D.Heuristics for the container loading problem［J］.European Journal of Operational Research，2002，141（2）：143-153.

［2］ Bischoff E E，Ratcliff M S W.Issues in the development of approaches to container loading［J］.International Journal of Management Science，1995，23（3）：377-390.

［3］ Gehring H，Bortfeldt A.A genetic algorithm for solving the container loading problem［J］. International Transactions in Operational Research，1997，4（5-6）：401-418.

［4］ DaviesA P，BischoffE E.Weightdistribution considerations in container loading［J］. European Journal of Operational Research，1999，114（3）：509-527.

［5］ Eley M.Solving container loading problems by block arrangement［J］. European Journal of Operational Research，2002，141（2）：393-409.

［6］ Egeblad J.Placement of two-and three-dimensional irregular shapes for inertia moment and balance［J］. International Transactions in Operational Research，2009，16（6）：789-807.

［7］ Baldi M M，Peroli G.The three-dimensional knapsack problem with balancing constraints［J］. Applied Mathematics and Computation，2012，218（19）：9802-9818.

［8］ Liu J M，Yue Y.A novel hybrid tabu search approach to container loading［J］.Computers&Operations Research，2011，38（4）：797-807.

［9］ Lim A，Ma H.The single container loading problem with axle weight constraints［J］. Int. J. Production Economics，2013，144（6）：358-369.

［10］雷定猷，湯波.一車多件貨物裝載布局優(yōu)化模型與算法［J］.鐵道學報，2011，33（9）：1-9.［LEI D Y，TANG B. Optimizing modeland algorithmsofloadingand packing multi-piece freights into one car［J］.Journal of The China Railway Society，2011，33（9）：1-9.］

［11］Crainic T，Perboli G.Extreme point-based heuristics for three-dimensional bin packing［J］.Informs Journal on Computing，2008，20（3）：368-338.

［12］Gongalves J F，Resende M G C.Biased random-key genetic algorithms for combinatorial optimization［J］. Journal of Heuristics，2010，17：487-525.

Bi-level Hybrid Genetic Algorithm for Three-dimensional Container Loading Problem with Balancing Constrains

ZHU Xiang1,2，LEI Ding-you2
(1.School of Management,Hunan International Economics University,Changsha 410205,China;2.School of Traffic& Transport Engineering,Central South University,Changsha 410075,China)

Based on a framed-layout concept,a bi-level hybrid genetic algorithm(BHGA)is presented for the three-dimensional container loading problem(3DCLP)with balancing constraints.Firstly,the concept of core block and its generation tactics are proposed according to the freight characters.Then a construction process adapt to the balance loading is introduced combined with the concepts of extreme-point and anchordistance.Based on the initial frame and the co-evolution of internal and external searches of BHGA,the optimal placement for the freights can be determined.Lastly,the approach is tested on standard benchmark test data and is compared with the existed researches involving balance constrains.The results demonstrate that it is effective in improving the space use rate and balance level of the center gravity.

logistics engineering;3DCLP;balancing constraints;BHGA;framed layout

1009-6744（2015）02-0203-07

U294.5

A

2014-11-27

2015-01-26 錄用日期：2015-02-05

國家自然科學基金研究項目（71371193）.

朱向（1976-），男，湖南長沙人，博士，講師. *通信作者：cszhuxiang@163.com