三維裝箱問(wèn)題的偏隨機(jī)密鑰混合遺傳算法

游偉，雷定猷，朱向

中南大學(xué)交通運(yùn)輸工程學(xué)院，長(zhǎng)沙 410075

三維裝箱問(wèn)題的偏隨機(jī)密鑰混合遺傳算法

游偉，雷定猷，朱向

中南大學(xué)交通運(yùn)輸工程學(xué)院，長(zhǎng)沙 410075

1 引言

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

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

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

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

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

2 問(wèn)題描述及數(shù)學(xué)模型

2.1 問(wèn)題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

3 偏隨機(jī)密鑰遺傳算法

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

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

3.1 個(gè)體編碼

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

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

3.2 遺傳操作

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

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

圖2 交叉操作實(shí)例

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

圖3 新種群形成過(guò)程

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

4.1 極點(diǎn)裝載法

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

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

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

4.2 裝載過(guò)程

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

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

圖5 啟發(fā)式裝載方法運(yùn)行過(guò)程

4.3 重心優(yōu)化

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

圖6 物品移動(dòng)示例

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

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

5 實(shí)例

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

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

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

圖7 裝載方案布局示意圖

表2 裝載方案技術(shù)指標(biāo)

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

6 結(jié)束語(yǔ)

針對(duì)考慮裝載重心平衡等實(shí)踐約束條件的鐵路集裝箱三維裝箱問(wèn)題，本文先使用偏隨機(jī)密鑰遺傳算法進(jìn)行物品裝載序列的優(yōu)化，然后基于各裝載序列，采用基于極點(diǎn)的啟發(fā)式方法進(jìn)行裝載模式的構(gòu)建，再通過(guò)最優(yōu)布置方案中部分物品位移，以實(shí)現(xiàn)布局重心優(yōu)化的目的，幾部分方法結(jié)合起來(lái)可獲得最優(yōu)裝載方案。通過(guò)采集鐵路裝運(yùn)現(xiàn)場(chǎng)的數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，驗(yàn)證了方法具有有效性。如何在裝載模式構(gòu)造過(guò)程中將重心調(diào)整結(jié)合起來(lái)考慮，以及根據(jù)貨物類別特征等因素，確立裝載算法選擇機(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]張德富，彭煜，朱文興，等.求解三維裝箱問(wèn)題的混合模擬退火算法[J].計(jì)算機(jī)學(xué)報(bào)，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ùn)優(yōu)化理論與應(yīng)用研究[D].長(zhǎng)沙：中南大學(xué)，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

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

三維裝箱；混合遺傳算法；偏隨機(jī)密鑰；啟發(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.

中國(guó)鐵路總公司資助項(xiàng)目（No.2013X009-1）。

游偉（1961—），男，博士研究生，研究領(lǐng)域?yàn)榻煌ㄟ\(yùn)輸；雷定猷，教授，研究領(lǐng)域?yàn)榻煌拔锪鳎恢煜?，講師，研究領(lǐng)域?yàn)槲锪鞴こ獭-mail：1271446294@qq.com

2014-01-17

2014-06-05

1002-8331（2014）22-0265-06

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