游偉，雷定猷，朱向

中南大學交通運輸工程學院，長沙 410075

三維裝箱問題的偏隨機密鑰混合遺傳算法

游偉，雷定猷，朱向

中南大學交通運輸工程學院，長沙 410075

1 引言

三維裝箱問題（three-Dimensional Container Loading Problem，3DCLP）是指從多件貨物中選擇若干件貨物經(jīng)過適當?shù)慕M合并按照一定的順序裝入某個集裝箱中，以達到箱子容積和載重量最大化利用的目的。貨物是具有一定的尺寸和質(zhì)量的矩形、勻質(zhì)類物品，箱子為具有矩形空間容積及一定承載能力的矩形容器。貨物以正交的形式放入集裝箱，擺放方向任意，最多包含6種旋轉方向。由于物品和容器存在不同規(guī)格，不同貨物組合及其擺放位置都將對裝載效果帶來不同影響，同時還要求滿足裝載穩(wěn)定性、貨物表面承載能力及重心平衡等約束條件，因而裝箱問題屬于復雜組合優(yōu)化問題，具有NP難問題的特點[1]。

實現(xiàn)貨物的高效裝載及合理布局，在空運、海運及鐵路等裝運領域具有重要的意義，已吸引了一批學者對此優(yōu)化問題進行研究，并總結出一整套求解方法，主要包括確定性方法、隨機搜索和混合方法等三類方法。

確定性方法中，Chen[2]的整數(shù)規(guī)劃、Hifi[3]的分支定界法是其中典型的代表，這些方法主要適合規(guī)模較小的裝載問題。對于規(guī)模較大的問題，可采用隨機搜索方法并結合啟發(fā)式規(guī)則進行求解，包括使用遺傳算法[4-5]、模擬退火算法[6]、禁忌算法[7-8]、貪婪隨機自適應搜索[9]等隨機搜索機制尋優(yōu)，以實現(xiàn)在相對較大的空間范圍內(nèi)對解的搜索。

除上述典型的優(yōu)化方法外，更多的研究是將啟發(fā)式方法與隨機搜索結合起來形成的混合優(yōu)化方法。Gehring和Bortfeldt先利用“塔”集生成算法構造出各種塔型貨物單元，再按照遺傳算法搜索出的裝載序列及BL（Best fit decreasing）規(guī)則進行裝載[4]；Davies和Elye[10-11]基于貨物層布局單元形成初始布局，再利用遺傳算法實現(xiàn)層的旋轉與貨物重心位置的調(diào)整。

一般而言，以構造法為代表的啟發(fā)式方法能根據(jù)問題的特點快速搭建起求解的框架，并以此作為問題求解的方向，但它一般只能達到局部最優(yōu)，由于三維裝載問題的復雜性，過多地依賴構造法來布局將使求出的解的質(zhì)量受到影響；而隨機優(yōu)化算法能實現(xiàn)在相對較大的空間范圍內(nèi)的尋優(yōu)，對獲得全局優(yōu)化解起到一定的保障，但搜索的時間長，效率一般，不及構造法。將構造法與隨機算法有效結合起來形成的混合優(yōu)化方法，能將兩者的優(yōu)點結合到一起同時彌補各自的不足，因而被廣泛運用于裝載布局優(yōu)化問題的求解。本文采用啟發(fā)式方法與遺傳算法相結合的混合算法對鐵路集裝箱裝載問題進行研究。

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

2.1 問題描述

對不同運輸領域中的集裝箱進行裝載，要求實現(xiàn)的目標及需考慮的實踐約束條件有所不同，本文主要針對鐵路集裝箱的裝載布局進行研究。它是指從多件貨物中選擇若干件進行組合，以正交的形式裝入一個集裝箱，要求在滿足有關實踐約束的條件下，實現(xiàn)裝載空間與負載能力利用最大化。集裝箱在鐵路上的裝運經(jīng)常需要考慮的約束中，除了集裝箱空間容積與載重量約束以外，主要包括貨物的集重與重心平衡等約束[12]。裝載集重主要出現(xiàn)在裝運重量較大、體積較小的集重類貨物的條件下，本文研究一般類型貨物的裝運，不涉及該因素的討論。進一步，對問題論述的前提作以下規(guī)定：

（1）裝載的貨物為長方體，質(zhì)量均勻，擺放方向任意。

（2）貨物及其包裝良好，可支撐承重和多層裝載，不是危險品等特殊貨物。

（3）貨物是同一到達站，不考慮中間加裝或卸貨的情形。

（4）使用一個集裝箱裝載，允許留下貨物以后裝載。

把形狀和重量完全相同的貨物稱為同類貨物，本文研究的裝載布局模型可定義為：

多件N類長方體貨物（每類各有n1,n2,…,nN件）用一個集裝箱裝運到同一目的地，要求滿足下列約束條件的前提下，最大化集裝箱裝載空間與負載能力的利用。

（1）集裝箱裝載的貨物互不干涉且不超出裝載空間的邊界。

（2）所裝貨物的重量和體積之和不超過其允許載重量和有效容積。

（3）集裝箱裝載的貨物，其合重心的偏移量不超過容許的范圍。

2.2 數(shù)學模型

以集裝箱左后下角為坐標原點，底板為X-Y平面，建立空間直角坐標系：Y軸平行于箱子縱中心線，方向從左向右；X軸沿箱端，方向從后向前；Z軸垂直于底平面向上。設貨物pij裝箱后重心坐標為分別為貨物重心到YZ平面、XZ平面和XY平面的距離，貨物pij左后下角的坐標為(xij,yij,zij)。車輛底面中心坐標為(C1,C2,0)，根據(jù)上述設定，建立如下平衡裝載優(yōu)化布局數(shù)學模型：

目標函數(shù)式（1）表示實現(xiàn)容積利用率與負載利用率綜合目標最大化要求，權重系數(shù)α,β為常數(shù)，可根據(jù)裝載對象性質(zhì)等因素選取。約束條件式（2）、（3）和（4）分別表示裝載的貨物不超出箱子邊界；式（5）、（6）、（7）表示裝載貨物之間互不干涉；式（8）、（9）、（10）為使用列車裝運時對車廂重心在橫向、縱向及高度方向的要求，其容許偏移量Δi(i=1,2,3)為已知量，可由承運工具參數(shù)和載重量確定，如鐵路運輸按《鐵路裝載加固規(guī)則》計算；式（11）、（12）為集裝箱允許載重量和有效容積約束，式（13）為所裝載貨物總數(shù)量約束。

3 偏隨機密鑰遺傳算法

針對上述模型，本文采取遺傳算法與啟發(fā)式構造法相結合的方法進行求解，即由遺傳算法搜索出物品裝載序列，再結合構造法實現(xiàn)物品的裝入。通過遺傳算法搜索裝載序列的方法已獲得相應的研究，但如何加快算法收斂并防止陷入局部最優(yōu)一直是個難點。借鑒文獻[13]提出的偏密鑰隨機遺傳算法，本文將其應用于序列的優(yōu)化。

偏密鑰隨機遺傳算法基于0到1間的隨機數(shù)字構建裝載序列和實現(xiàn)遺傳操作，由這些數(shù)字組成的向量可以表示問題的一個可行解，經(jīng)過交叉操作新產(chǎn)生的向量仍將屬于可行解?；谒惴ǖ膭討B(tài)特性，系統(tǒng)可以建立隨機密鑰向量與優(yōu)化布局方案之間的有機聯(lián)系。

3.1 個體編碼

偏密鑰隨機遺傳算法的初始染色體中前M個基因，可先按物品類型序號以升序排列，再根據(jù)以升序排列的隨機密鑰進行調(diào)整，可獲得初始裝載序列的物品部分編碼（如圖1所示）。物品擺放方向編碼，可結合物品可放置方向規(guī)定以隨機方式生成。

圖1 物品裝載序列基因編碼

3.2 遺傳操作

在算法中，對個體實行的遺傳操作的過程包括復制、交叉及變異操作過程。復制過程采用精英策略，按一定比例從上一代復制優(yōu)秀進入下一代。相比于概率復制方法，精英策略能有效地確保解的質(zhì)量在進化過程不斷獲得提升。

與一般密鑰隨機遺傳算法[14]交叉操作不同，偏密鑰隨機遺傳算法交叉操作的兩個個體，一個來自精英群體，另一個以隨機方式從全部個體中產(chǎn)生，這樣有助于加快收斂并提高解的質(zhì)量[13]。如圖2所示，染色體1代表精英個體，染色體2表示一般個體。設交叉概率為0.7，即子代以0.7的概率從精英父代中獲得基因，以0.3的概率從一般個體中獲得基因。以擲硬幣的方式?jīng)Q定從哪個染色體選擇基因，頭面朝上時選擇第一個染色體，否則選擇第二個染色體。模擬拋擲一枚偏斜的硬幣來產(chǎn)生隨機數(shù)，該硬幣有0.7的概率頭面朝上。當生成的隨機數(shù)小于等于0.7時，從第一個染色體獲得基因；當隨機數(shù)大于0.7時，選擇第二個染色體產(chǎn)生基因。這樣產(chǎn)生的子代更接近于精英個體，可起到加速收斂的作用。

圖2 交叉操作實例

一般的遺傳算法以小概率在個體基因間進行的變異操作，而隨機密鑰遺傳算法的變異操作在下一代種群中增加更多的新個體，即按照初始種群生成相同的分布，以隨機方式來選擇一些個體加入種群，從而起到防止早熟作用。全部遺傳操作及新種群產(chǎn)生的過程如圖3所示。

圖3 新種群形成過程

4 基于極點的啟發(fā)式裝載法

4.1 極點裝載法

對于搜索產(chǎn)生的物品裝載序列ps，這里借鑒文獻提出的極點法[15]（Extreme Points，EPs）并進行改進的基礎上來完成裝載，從而實現(xiàn)由裝載序列向布局方案的轉變。對于長、寬和高分別為lk、wk和hk物品k，選擇某一裝載模式并放置于箱中坐標為(xk,yk,zk)的左后下角位置時，將產(chǎn)生多個用于放置其他物品的新的極點，它們是由坐標值為(xk+lk,yk,zk)、(xk,yk+wk,zk)和(xk,yk,zk+hk)的點垂直投影到箱壁或鄰近物品上而形成（如圖4所示），這些點代表后續(xù)裝載可以選擇放置的位置。當箱子為空時，初始極點對應為箱子的兩個對稱角位置（可設左邊為左后下角，右邊為右前下角）；隨著裝載的進行，更多的極點隨之形成，可作為后續(xù)裝載可供選擇的位置。

圖4 極點產(chǎn)生過程

選擇不同的極點放置物品將形成不同的裝載模式，產(chǎn)生相應的裝載效果，可按照一定的規(guī)則，從多個極點中選擇一個作為當前物品的放置位置。不同于文獻[15]使用極點的過程，為了加速平衡布局方案的形成，這里結合有助于重心平衡的啟發(fā)式裝載規(guī)則進行布局。借鑒左后下角（Left-Down-Back Conner）規(guī)則，采取同時從箱子左右兩邊以對稱形式進行布局的方法，即左邊從左后下角開始、右邊從右前下角開始進行裝載。從箱子兩邊同時展開裝載有利于箱子四周形成相對緊湊的布局，空間碎片主要集中于中部位置，為借助中間位置物品位移實現(xiàn)整體重心調(diào)整創(chuàng)造了條件。

4.2 裝載過程

為了實現(xiàn)上述對稱裝載的思想，借鑒文獻[16]提出的錨距和錨角的方法來確定當前裝載的極點。由于裝載時貨物一般放在空間的某個角落，將裝載空間角與其對應的集裝箱箱角間的距離稱之為錨距，并使用曼哈頓距離衡量。錨距最小的角稱為錨角，極點的選擇以錨距最小為原則確定，即選擇與箱子對稱的兩個角距離較近的極點位置放置貨物。由此建立極點列表用以存儲裝載過程中新產(chǎn)生的極點，依據(jù)它們距離箱角的遠近進行排序，并隨裝載的進行不斷對極點序列進行更新。

貨物裝載是基于預先確定的貨物序列，將貨物依次放入極點序列指定的位置上。為了確保實施過程中各裝載對象放置的穩(wěn)定性，計算各物品底部支撐面積，要求確保其獲得完全支撐。裝載中若某一極點位置不能滿足完全支持條件或無法裝入當前物品時，則考慮極點列表中下一個極點，直至找到能滿足裝載條件的極點為止。若找不到適合的極點，則暫時放棄該物品裝載，考慮裝載序列中下一對象；而在后續(xù)的裝載中，將優(yōu)先考慮之前未裝入的物品。每完成一次物品裝入，按照排序規(guī)則對極點序列進行一次更新，同時記錄剩余可用物品。以此方式持續(xù)下去，直至全部物品裝入或箱子不能裝入為止?；跇O點的啟發(fā)式裝載方法的運行過程如圖5所示。

圖5 啟發(fā)式裝載方法運行過程

4.3 重心優(yōu)化

基于裝載序列與啟發(fā)式裝載方法完成最優(yōu)布置方案搜索后，可通過對確定的方案中部分物品實施位移，從而達到進一步裝載重心的目的。物品的移動涉及移動的目標方向及可移動的范圍等問題，需結合具體布局方案進行分析和確定，下面簡要介紹物品移動的過程。

圖6 物品移動示例

上述是基于理想的推導，實際操作過程中可能存在相互干涉而無法移動，因此需在確定移動對象后，對其可移動范圍進行界定。如圖6所示，設虛線框所圍區(qū)域Di表示物品i的可移動范圍，實心原點表示合重心理想位置。Di確定下來后，可按以下不同情形進行操作：

當Di={?}為空集時，物品不移動；當∈Di時，移動物品i至r′以滿足平衡條件（如圖6（a））；當?Di且Di≠{?}時，可將i移至最接近于r′的中間位置r″，盡可能地接近于平衡（如圖6（b））。另外，由于物品在三維空間的移動除了滿足平衡條件外，還需考慮穩(wěn)定性要求，因此物品在垂直方向的移動應確保其處于被支撐狀態(tài)，可采取類似重力作用的情形作進一步移動，使其獲得相應支撐。

5 實例

由于目前鐵路集裝箱兩用車較少，常用敞車裝運集裝箱，本實例屬這種情況。貨物數(shù)據(jù)如表1，各件貨物重心為其幾何中心。車型為敞車C62，技術參數(shù)為：標記載重60 t，裝載一個40英尺的集裝箱，集裝箱內(nèi)部容積（1 199×233×235）cm3，允許載重量26.6 t，貨物合重心最大允許橫向偏移為10 cm，最大允許縱向偏移根據(jù)載重量計算。

表1 貨物數(shù)據(jù)表

根據(jù)上述模型及算法，運用C++語言進行編程。算法參數(shù)取值分別為：種群規(guī)模為30，交叉概率為0.7，精英個體復制比例為15%，隨機生成變異個體比例為15%，終止條件為連續(xù)運行500代。使用Intel Core2 Duo2.0 GHz處理器運行程序，可制定貨物的裝載布局方案：布局示意圖見圖7；貨物合重心的縱向、橫向偏移量、重心高、車輛利用情況見表2；貨物配裝情況及布局位置見表3。

圖7 裝載方案布局示意圖

表2 裝載方案技術指標

從裝載方案表中可以看出，待裝貨物中只有第2類和第5類各1件（編號20、34）未裝入。貨物合重心偏移及重車重心高度均在許可范圍內(nèi)，且偏移量較小，符合平衡裝載要求；同時，集裝箱的裝載利用率都較好，尤其是有效容積利用率達到較高的水平?？傮w而言，獲得的裝載方案車輛利用效果好，且布局合理，滿足各主要約束屬于優(yōu)良的布局方案。

6 結束語

針對考慮裝載重心平衡等實踐約束條件的鐵路集裝箱三維裝箱問題，本文先使用偏隨機密鑰遺傳算法進行物品裝載序列的優(yōu)化，然后基于各裝載序列，采用基于極點的啟發(fā)式方法進行裝載模式的構建，再通過最優(yōu)布置方案中部分物品位移，以實現(xiàn)布局重心優(yōu)化的目的，幾部分方法結合起來可獲得最優(yōu)裝載方案。通過采集鐵路裝運現(xiàn)場的數(shù)據(jù)進行實驗，驗證了方法具有有效性。如何在裝載模式構造過程中將重心調(diào)整結合起來考慮，以及根據(jù)貨物類別特征等因素，確立裝載算法選擇機制等方面可作為下一步研究方向。

表3 貨物配裝情況及布局位置

[1]Pisinger D.Heuristics for the container loading problem[J]. EuropeanJournalofOperationalResearch，2002，141：143-153.

[2]Chen C S，Lee S M，Shen Q S.An analytical model for the container loading problem[J].European Journal of Operational Research 1995，80：68-76.

[3]Hifi M.Exact algorithms for the guillotine strip cutting/ packing problem[J].Computers Operations Research，1998，25（11）：925-940.

[4]Gehring H，Bortfeldt A.A genetic algorithm for solving the container loading problem[J].International Transactions on Operational Research，1997：401-418.

[5]Gehring H，Bortfeldt A.A parallel genetic algorithm for solvingthecontainerloadingproblem[J].International Transactions in Operational Research，2002，9：497-511.

[6]張德富，彭煜，朱文興，等.求解三維裝箱問題的混合模擬退火算法[J].計算機學報，2009，32（11）：2147-2156.

[7]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.

[8]Liu J，Yue Y.A novel hybrid tabu search approach to container loading[J].Computers&Operations Research，2011，38：797-807.

[9]Moura A，Oliveira J F.A GRASP approach to the container-loading problem[J].IEEE Intelligent Systems，2005，20（4）：50-57.

[10]Davies A P，Bischoff E E.Weight distribution considerations in container loading[J].European Journal of Operational Research 1999，114（3）：509-527.

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

[12]雷定猷.貨物裝運優(yōu)化理論與應用研究[D].長沙：中南大學，2004.

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

[14]Bean J C.Genetics and random keys for sequencing and optimization[J].ORSA Journal on Computing，1994，6：154-160.

[15]Crainic T，Perboli G.Extreme point-based heuristics for three-dimensionalbinpacking[J].InformsJournalon Computing，2008，20.

[16]Zhu W B，Lim A.A new iterative-doubling greedy-lookahead algorithm for the single container loading problem[J]. European Journal of Operational Research，2012，222：408-417.

[17]Zhu W B，Huang W L.A prototype column generation strategy for the multiple container loading problem[J]. European Journal of Operational Research，2011，223（2012）：27-39.

YOU Wei,LEI Dingyou,ZHU Xiang

School of Traffic&Transport Engineering,Central South University,Changsha 410075,China

The three-Dimensional Container Loading Problem（3DCLP）with practice constrains is a complex combinatorial optimization problem and has the typical characters of NP-hard.As to the tendency of convergence into local optimization of the basic Genetic Algorithm（GA）,the paper puts forward a method to optimize the loading sequence based on the biased random-key GA.Then the optimal layout to the boxes can be determined using a heuristic based on extreme-points approach.And the balance of the whole loading gravity center can be improved by the moving of parts of items lastly.The instance demonstrates that the algorithm can generate the optimizing packing plan quickly,in which the available capacity of the vehicle is utilized well and the requirements for the transportation safely are met.

three-Dimensional Container Loading Problem（3DCLP）;hybrid genetic algorithm;biased random-key;heuristic algorithm;balancing constraints

考慮實踐約束的三維裝箱問題屬于復雜的組合優(yōu)化問題，具有典型NP難問題的特點。針對一般遺傳算法求解裝箱問題易陷入局部最優(yōu)的缺點，提出使用偏隨機密鑰遺傳算法進行裝載序列搜索，結合基于極點的啟發(fā)式方法實現(xiàn)貨物的優(yōu)化布置，進而通過部分裝載物品的位移來改善整體重心分布。經(jīng)過實例運算和分析，證明提出的方法能快速制定貨物優(yōu)化布置方案，達到裝載工具高效利用及貨物安全運輸?shù)囊蟆?/p>

三維裝箱；混合遺傳算法；偏隨機密鑰；啟發(fā)式算法；重心平衡

A

U294

10.3778/j.issn.1002-8331.1401-0284

YOU Wei,LEI Dingyou,ZHU Xiang.Biased random-key hybrid genetic algorithm for three-dimensional loading problem.Computer Engineering and Applications,2014,50（22）：265-270.

中國鐵路總公司資助項目（No.2013X009-1）。

游偉（1961—），男，博士研究生，研究領域為交通運輸；雷定猷，教授，研究領域為交通及物流；朱向，講師，研究領域為物流工程。E-mail：1271446294@qq.com

2014-01-17

2014-06-05

1002-8331（2014）22-0265-06

CNKI網(wǎng)絡優(yōu)先出版：2014-07-02,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1401-0284.html