高 鵬，張德珍，張秀國

1.大連大學(xué) 經(jīng)濟(jì)管理學(xué)院（旅游學(xué)院），遼寧 大連 116622

2.大連海事大學(xué) 信息科學(xué)技術(shù)學(xué)院，遼寧 大連 116026

“一帶一路”建設(shè)極大促進(jìn)了沿線各國間的貿(mào)易往來，跨境貨物運(yùn)輸量大為提高。由于集裝箱在多式聯(lián)運(yùn)中可以有效減少貨物轉(zhuǎn)運(yùn)時(shí)間，節(jié)省成本，提高運(yùn)輸效率，因此，使用集裝箱裝載貨物成為海運(yùn)和鐵路運(yùn)輸?shù)氖走x方式。然而近年來國際經(jīng)濟(jì)形勢復(fù)雜多變，加之受新冠疫情影響，集裝箱運(yùn)費(fèi)不斷攀升。單個(gè)集裝箱使用效率成為企業(yè)降低物流成本的關(guān)鍵。然而，實(shí)際應(yīng)用中，貨物生產(chǎn)企業(yè)在將客戶所訂購的多種規(guī)格、不同數(shù)量貨物裝入集裝箱，往往因?yàn)樨浳飻[放位置和次序不恰當(dāng)，而裝不下或浪費(fèi)空間，導(dǎo)致多次“倒箱”操作，從而浪費(fèi)大量人力、物力，甚至延誤離岸時(shí)間，造成經(jīng)濟(jì)損失。該問題實(shí)際上是復(fù)雜現(xiàn)實(shí)約束條件下的集裝箱布局優(yōu)化問題。根據(jù)待裝載貨物種類多少以及每種貨物數(shù)量多少，可以分為弱異類和強(qiáng)異類問題[1]、單集裝箱和多集裝箱問題[2]。本文研究的是單一集裝箱強(qiáng)異類問題。該問題主要目標(biāo)是提高填充率，在采用相同測試數(shù)據(jù)的前提下，Gongalves 等[3]在2012 年提出的解決方案的填充率比Bischoff 等[4]在1995 年提出的解決方案平均高出11%；但2017年，Araya等[5]提出BSG_VCS算法，填充率已達(dá)到94.6%，僅提高了約0.68%。在保證填充率的前提下，如何用更短時(shí)間來求解是值得深入考慮的另一個(gè)問題。

集裝箱裝載問題（CLP）理論上屬于NP-Hard 問題，隨著問題的規(guī)模的增加，采用數(shù)學(xué)規(guī)劃的方法會(huì)消耗大量的內(nèi)存和運(yùn)行時(shí)間[6]，目前常用啟發(fā)式算法進(jìn)行求解[7]。對(duì)CLP問題，可以分為單一啟發(fā)式算法和融合啟發(fā)式算法。其中，單一啟發(fā)式算法又可分為單一傳統(tǒng)啟發(fā)式算法與單一現(xiàn)代啟發(fā)式算法。單一傳統(tǒng)啟發(fā)式算法較為實(shí)用，借助于人的主觀經(jīng)驗(yàn)進(jìn)行設(shè)計(jì)，計(jì)算效率較高，而且能夠?qū)τ?jì)算過程進(jìn)行詳細(xì)描述。如Bischoff等[4]提出了一種將貨物均勻分布與多點(diǎn)負(fù)載相結(jié)合的元啟發(fā)式算法，并為三維裝箱問題提供了公共測試數(shù)據(jù)集。但傳統(tǒng)啟發(fā)式算法設(shè)計(jì)過于依賴人的主觀經(jīng)驗(yàn)，缺乏嚴(yán)格的數(shù)學(xué)理論證明，導(dǎo)致算法設(shè)計(jì)具有一定的隨意性?，F(xiàn)代啟發(fā)式算法以仿自然體算法為主，主要有蟻群算法[8]、遺傳算法[9]等，能夠有效求解組合優(yōu)化等問題，但若僅采用單一現(xiàn)代啟發(fā)式算法，在運(yùn)算初期其收斂速度較慢，貨物選擇具有較大隨機(jī)性，所以求解效率往往較差。

考慮到融合啟發(fā)式算法在處理超大規(guī)模問題時(shí)表現(xiàn)出更好的時(shí)間性能和優(yōu)化性能，能在很大程度上彌補(bǔ)單一啟發(fā)式算法的不足。部分學(xué)者提出可采用兩階段的分步求解策略，將求解過程進(jìn)行嚴(yán)格劃分，兩個(gè)階段求解過程相對(duì)獨(dú)立。如Toffolo 等[10]將裝箱過程劃分為建立貨物堆垛和將堆垛裝箱兩個(gè)階段，將三維裝箱問題轉(zhuǎn)化為二維裝箱問題；Paquay等[11]第一階段采用自定義打包算法，為給定貨物及ULD類型提供裝載模式，第二階段考慮可用容器的多樣性，并設(shè)計(jì)算法進(jìn)行打包；Saraiva等[12]第一階段生成構(gòu)造塊，第二階段構(gòu)造元啟發(fā)式算法。以上這些嚴(yán)格意義上的兩階段求解策略，在初期采用一種算法A以快速求解，在后期完全采用另一種算法B 進(jìn)行求解。這類算法在初期有可能局限于某種算法而降低了整體隨機(jī)性，并且在后期，由于完全采用B 算法而又丟棄了第一階段采用A 算法的優(yōu)越性。相對(duì)上述明確的兩階段劃分求解策略，也存在未對(duì)求解過程進(jìn)行明確劃分的情況。如張煜等[13]提出了一種粒子群算法和鄰域搜索算法融合的基于PSO 的模因算法；Goncalves 等[14]基于隨機(jī)密鑰提出了一種偏向隨機(jī)密鑰遺傳算法（BRKGA）；Jamrus 等[15]基于擴(kuò)展優(yōu)先級(jí)策略，提出了一種混合遺傳算法（EP-HGA）；張長勇等[16]基于一種由在線極值點(diǎn)算法與模擬退火算法相融合的算法；Moura等[17]基于墻體構(gòu)造策略，提出一種貪婪隨機(jī)自適應(yīng)搜索算法（GRASP）；于明正等[18]將啟發(fā)式算法和遺傳算法的同時(shí)增加了一層提高搜索廣度的遺傳迭代層，從而構(gòu)成了二層規(guī)劃算法。這類算法主要以嵌套混合為主增加了算法的復(fù)雜性和計(jì)算負(fù)擔(dān)。

蟻群算法的優(yōu)勢是在時(shí)間和空間上的尋優(yōu)性能，但是蟻群算法前期信息素積累慢，導(dǎo)致算法收斂較慢，而貪心算法具有收斂快、計(jì)算量小的優(yōu)勢[19]。本文提出了一種基于概率的融合策略，來控制三空間貪心層疊法（GSM）與三空間蟻群層疊法（ASM）在選貨方式上的參與程度，從而在保證解的多樣性前提下，更好地發(fā)揮貪心算法的收斂優(yōu)勢和蟻群算法的尋優(yōu)優(yōu)勢。在該策略下，初始階段以GSM為主獲得局部最優(yōu)解，避免在算法執(zhí)行初期因螞蟻的信息素濃度偏低導(dǎo)致容易陷入局部最優(yōu)解及運(yùn)算時(shí)間過長的問題；逐步地以ASM為主，對(duì)各種不同局部最優(yōu)裝載鏈進(jìn)行優(yōu)化求解，獲得全局解；通過調(diào)整分布函數(shù)，可以實(shí)現(xiàn)前后兩個(gè)階段中兩種選貨方式的參與程度可控，也有一定的概率產(chǎn)生隨機(jī)解以保證解的多樣性，最終實(shí)現(xiàn)算法的動(dòng)態(tài)融合以提升求解效率。同時(shí)，在蟻群算法求解過程中，通過構(gòu)造狀態(tài)值和剪枝矩陣，對(duì)裝載過程中的每個(gè)狀態(tài)值，擇優(yōu)存儲(chǔ)并更新剪枝矩陣。在剪枝矩陣中，每一個(gè)狀態(tài)值只對(duì)應(yīng)一條裝載鏈，縮減了問題的可行解空間，從而有效縮短了程序運(yùn)算時(shí)間。最后，基于本文提出的算法，采用Bischoff和Ratcliff[4]提出的BR1-BR10公共測試數(shù)據(jù)進(jìn)行測試和對(duì)比分析。實(shí)驗(yàn)結(jié)果表明，本文所提出的算法對(duì)快速求解單箱強(qiáng)異類集裝箱布局優(yōu)化問題具有有效性和可行性。

1 問題分析與建模

1.1 問題描述

單一集裝箱強(qiáng)異類裝載問題，可描述為在滿足一定約束條件下，將若干種類（通常大于10 種）且規(guī)格尺寸不同的長方體貨物（每一種待裝貨物數(shù)量較多）裝入一個(gè)尺寸固定的集裝箱中，要求裝載完成后剩余空間最小，即空間利用率最大化。

實(shí)際裝箱問題因?yàn)闂l件復(fù)雜程度各異，制約了建模和求解過程，但現(xiàn)實(shí)條件如果過于簡化，則無法滿足實(shí)際裝箱需要。本文根據(jù)所面向的實(shí)際工程問題，做如下假設(shè)：

（1）將集裝箱和貨物均看作是長方體，且貨物的尺寸均小于集裝箱尺寸；

（2）貨物質(zhì)量均勻分布，貨物重心即為幾何中心；

（3）不考慮貨物承載能力，貨物上可放置任意貨物；

（4）貨物沒有擠壓和變形；

（5）貨物均到達(dá)同一個(gè)目的地。

1.2 符號(hào)說明

由于待裝載貨物種類多樣且每類貨物數(shù)量各不相同，故本文對(duì)關(guān)于集裝箱裝載問題變量及符號(hào)進(jìn)行如下定義。

N：待裝載貨物的總數(shù)量；

nk：第k類貨物的裝載數(shù)量，范圍為[nkmin,nkmax]；

uk：第k類貨物的堆碼層數(shù)，ukmax為第k類貨物作為最底層貨物的最大承載堆放層數(shù)；

vi：貨物i的體積；

K：貨物的種類數(shù)；

CT：最大迭代次數(shù)；

Ui：貨物i裝入集裝箱則Ui=1，否則Ui=0；

L,W,H：集裝箱的長、寬、高；

li,wi,hi：貨物i的長、寬、高；

PiT(xTi ,yiT ,zTi)：貨物i在集裝箱中的右-前-上角點(diǎn)及其坐標(biāo)；

PiB(xiB ,yiB ,ziB)：貨物i在集裝箱中的左-后-下角點(diǎn)及其坐標(biāo)；

s：狀態(tài)值，即由已裝載貨物種類和各類貨物的數(shù)量生成的二進(jìn)制數(shù)；

SΠ(i,p)：貨物i在貨物p上沿Z軸方向在XOY面上的投影面積。

1.3 裝載模型約束條件描述

（1）每類貨物的實(shí)際裝載數(shù)量不能超出該類貨物給定的數(shù)量范圍；

（2）貨物放置方向與集裝箱兩側(cè)面平行或正交；

（3）貨物不能懸空放置，即上方貨物必須完全放置在下方貨物的上面；

（4）實(shí)際裝載貨物的總?cè)莘e不能大于集裝箱的最大裝載容積；

（5）貨物其上可承載的層數(shù)為給定層數(shù)。

由于本文所研究的待裝載貨物在總重量和質(zhì)心方面均在允許范圍內(nèi)，故不再對(duì)此類約束討論。

根據(jù)實(shí)際裝箱考慮的約束條件，建立約束條件表達(dá)式如下所示。

（1）數(shù)量約束：每類貨物的實(shí)際裝載數(shù)量不能超出該類貨物給定的數(shù)量范圍，即：

（2）方向約束：貨物放置方向與集裝箱兩側(cè)箱面平行或正交，其放置姿態(tài)共有6種。以圖1放置為例，貨物i在集裝箱中的右-前-上角坐標(biāo)、左-后-下角坐標(biāo)及其與集裝箱坐標(biāo)軸間的位置關(guān)系，其形式化描述為：

圖1 貨物放置方向及標(biāo)識(shí)點(diǎn)示意圖Fig.1 Schematic diagram of cargo placement direction and marking points

其余5種可類比寫出。

（3）放置約束：貨物不能懸空放置，即上方貨物的下表面必須與下方貨物的上表面接觸，有：

（4）容積約束：實(shí)際裝載貨物的總?cè)莘e不能大于集裝箱的最大裝載容積，即：

（5）層數(shù)約束：實(shí)際裝載貨物縱向?qū)訑?shù)不能超過最底層貨物的最大承載堆放層數(shù)，即：

1.4 裝載模型目標(biāo)函數(shù)

單集裝箱裝載問題的優(yōu)化目標(biāo)是滿足一定約束條件下，使集裝箱的閑置空間最小，即最大化集裝箱的利用率，目標(biāo)函數(shù)表示如下：

定義1（閑置空間VI(m,s)）螞蟻m在狀態(tài)值為s時(shí)對(duì)應(yīng)的閑置空間集，如果剩余的未裝載貨物當(dāng)中沒有任何一個(gè)貨物可以裝入該剩余空間，則此空間被稱為閑置空間。

1.5 空間模型建立

選貨方式是基于貨物體積與當(dāng)前待裝箱空間的相對(duì)大小以及擺放次序的操作，每一個(gè)所選貨物放置于待裝載空間后，都將對(duì)布局空間產(chǎn)生結(jié)構(gòu)性影響。三空間分割法[20]是布局空間分解的一種典型方法，本文以該方法為基礎(chǔ)，進(jìn)行空間的分解和綜合利用。貨物在充填剩余空間時(shí)，采用從下到上（Z軸方向），從左到右（Y軸方向），從后到前（X軸方向）的順序依次擺放，在YOZ平面擺放完一層空間后，再開始第二層，直到裝滿該集裝箱。

針對(duì)裝箱后所產(chǎn)生的空間定義如下，并在后續(xù)過程中加以引用。

定義2（剩余空間（VA））對(duì)已分層來說，可以利用的空間以及可以進(jìn)行空間合并的空間。

定義3（殘余空間（VR））所有不能放置貨物以及無法進(jìn)行空間合并的空間。

定義4（待裝載空間（VU））對(duì)當(dāng)前層來說，待放置貨物的空間。

圖2 對(duì)閑置空間（VⅠ）、剩余空間（VA）、殘余空間（VR）、待裝載空間（VU）給出圖示。

圖2 空間定義示意圖Fig.2 Schematic diagram of space definition

2 貨物裝載方法

2.1 數(shù)據(jù)預(yù)處理算法

裝箱問題理論上屬于NP-Hard 的問題，貨物的種類、尺寸大小、數(shù)量等因素都會(huì)對(duì)裝載結(jié)果產(chǎn)生較大影響。隨著貨物種類的增加（即異構(gòu)性的增強(qiáng)），結(jié)果組合種類呈指數(shù)爆炸式增長。通過聚類算法能夠?qū)⒁唤M強(qiáng)異類問題拆分為若干組弱異類問題，提前對(duì)解空間進(jìn)行收斂，加快求解速度[21]。

本文采用經(jīng)典的K-means聚類方法，以選定貨物體積大小以及貨物最長邊長度的歸一化數(shù)據(jù)作為聚類的兩個(gè)指標(biāo)進(jìn)行聚類，最終根據(jù)聚類簇質(zhì)心的體積及最長邊的數(shù)據(jù)按照加權(quán)公式（8）從大到小排列，并將聚類簇中的貨物按最長邊降序排列，以獲得每個(gè)類別下貨物裝箱順序列表。綜合考慮貨物體積及最長邊長度，將貨物劃分為體積較大最長邊較長、體積較大最長邊較短、體積較小最長邊較長以及體積較小最長邊較短四種情況，故令聚類中心k=4，其聚類類別示意圖如圖3所示。

圖3 聚類類別示意圖Fig.3 Schematic diagram of clustering categories

其中，p為第i簇質(zhì)心體積vi所占的權(quán)重，(1-p)為第i簇質(zhì)心最長邊li所占的權(quán)重，經(jīng)過實(shí)驗(yàn)中對(duì)比計(jì)算，p為0.7時(shí)，聚類分析結(jié)果相對(duì)較好。

為了對(duì)數(shù)據(jù)處理算法的可用性進(jìn)行驗(yàn)證，本文以國際公測數(shù)據(jù)集BR8中的第一例實(shí)驗(yàn)數(shù)據(jù)為例，進(jìn)行聚類分析。因篇幅限制，只對(duì)部分?jǐn)?shù)據(jù)進(jìn)行展示，全部數(shù)據(jù)可從文獻(xiàn)[4]中下載。數(shù)據(jù)的長、寬、高等詳細(xì)信息如表1所示；聚類后數(shù)據(jù)的簇類型、質(zhì)心坐標(biāo)等詳細(xì)結(jié)果如表2所示。

表1 待裝載貨物信息Table 1 Ⅰnformation of goods to be loaded

表2 聚類結(jié)果Table 2 Clustering results

數(shù)據(jù)預(yù)處理算法并非簡單對(duì)貨物進(jìn)行分類，而是綜合考慮待裝載貨物的體積及最長邊長，依據(jù)數(shù)據(jù)特征減少裝箱貨物類型，盡可能保證同類貨物擺放規(guī)整，減少空間的浪費(fèi)提高集裝箱空間利用率。

2.2 剩余空間合并算法

在三維空間分解裝箱過程中，隨著箱體的不斷裝入，在不同位置將產(chǎn)生越來越多不規(guī)則“散碎”空間?？臻g合并就是把剩余的小空間進(jìn)行合并、分解，將其處理成一個(gè)個(gè)可利用的矩形體，便于后續(xù)裝箱過程中盛放適當(dāng)箱體，以提高空間利用率。

空間合并按照先左右合并，再前后合并的順序?qū)⒋喜⒖臻g整理到閑置空間列表中。合并前剩余空間如圖4所示。其中，i代表位于剩余空間A所在的區(qū)域，t代表位于剩余空間B所在的區(qū)域。

圖4 剩余空間示意圖Fig.4 Schematic diagram of remaining space

（1）左右合并：假設(shè)存在兩個(gè)剩余空間（剩余空間A和B），位于右側(cè)的剩余空間(B)為待合并空間，將待合并空間的左下角盡可能向左移動(dòng)。需要保證左側(cè)剩余空間的右側(cè)面包含右側(cè)剩余空間的左側(cè)面，即：

根據(jù)選出的Ymin，將空間向左側(cè)擴(kuò)大，并更新剩余空間表中的信息。左右合并后如圖5所示。

圖5 左右合并后剩余空間示意圖Fig.5 Diagram of remaining space of merging left and right

（2）前后合并：將當(dāng)前待合并空間分解為LEFT、RⅠGHT兩個(gè)空間，如圖6所示。

圖6 前后合并后剩余空間示意圖Fig.6 Diagram of remaining space of merging front and rear

其中，i代表位于閑置空間C所在的區(qū)域，t代表位于LEFT 空間所在的區(qū)域。假設(shè)存在兩個(gè)剩余空間（RⅠGHT 和C），位于前方的剩余空間C為待合并空間，將待合并空間的左后下角盡可能向后移動(dòng)。保證后方的剩余空間的前側(cè)面包含前方剩余空間的后側(cè)面，即：

根據(jù)選出的Xmin將空間向后方擴(kuò)大，并更新剩余空間表中的信息。前后合并后，最終效果如圖7所示。

圖7 空間合并最終效果圖Fig.7 Final effect diagram of space merging

上述兩種合并策略的綜合利用，將有效整合“散碎”剩余空間，進(jìn)而提高空間利用率。

2.3 確定貨物放置方向的啟發(fā)式策略

對(duì)每一個(gè)待裝載貨物而言，其放置方向如果不當(dāng)，將造成剩余空間浪費(fèi)，從而影響空間利用率。放置過程中，每一只螞蟻將綜合考慮待裝載貨物六種放置方向所產(chǎn)生的上方、右方和前方剩余空間的形態(tài)和大小，使貨物放入后所產(chǎn)生的剩余空間盡可能規(guī)整。該過程中，螞蟻將綜合考慮閑置的三個(gè)空間，使剩下的空間再一次放進(jìn)其他貨物，或盡可能使殘余空間為零。放置方向的確定是一個(gè)回溯過程，可以減少頂部和側(cè)部的廢棄空間數(shù)量。

如圖8 所示為對(duì)貨物及待裝載空間在YOZ面投影。若高度方向和寬度方向的剩余尺度面積之和最?。ㄈ珀幱懊娣e所示），則局部空間利用率最高，即：

圖8 貨物及待裝載空間投影圖Fig.8 Projection diagram of cargo and space to be loaded

其中，PTΩ(0,yTΩ,zTΩ)、PBΩ(0,yBΩ,zBΩ)分別為當(dāng)前待裝載空間的右上、左下角坐標(biāo)；PT i(0,yT i ,zTi)、PB i(0,yB i ,zB i)分別為貨物i的右上、左下角坐標(biāo)。

據(jù)此，本文提出了如下貨物放置方向策略：

（1）按公式（11）確定貨物擺放方向的優(yōu)先級(jí)；

（2）按最高優(yōu)先級(jí)確定層的寬度，將相同尺寸物體布局在該層，轉(zhuǎn)化為二維裝箱問題。

2.4 局部空間姿態(tài)調(diào)整策略

對(duì)每一個(gè)待裝箱體，存在6 種擺放姿態(tài)，姿態(tài)選擇恰當(dāng)與否，對(duì)于箱體裝載規(guī)整性以及盡可能減少空間浪費(fèi)，具有重要作用。在局部空間的計(jì)算中，由于裝載順序的原因，即上、右、前方向遞歸操作，前方向（即集裝箱箱體深度方向）遠(yuǎn)大于其他兩個(gè)方向，因而只要控制好集裝箱頂部和側(cè)方部位（分別對(duì)應(yīng)著裝載箱體的高度和寬度方向）的狹小縫隙，長度方向就不存在問題，使局部空間利用率最大化。

待裝箱體i初始姿態(tài)下的左-后-下角點(diǎn)PiB(xiB ,yiB ,ziB)和右-前-上角點(diǎn)，姿態(tài)調(diào)整在空間操作上意味著箱體分別繞X、Y、Z軸旋轉(zhuǎn)α、β、γ角，且遵守右手螺旋法則，變換后對(duì)應(yīng)的角點(diǎn)分別為和。因箱體軸線與集裝箱各軸線保持平行關(guān)系，這里α,β,γ∈{0°,90°}。以PiT和Pi′T為例，姿態(tài)調(diào)整前后二者之間的關(guān)系如式（12）所示：

并且有α∈{0°,90°},β=0°,γ=0°,α∈{0°,90°},β=90°,γ=90°,α∈{0°,90°},β=0°,γ=90°，在當(dāng)前擺放層，對(duì)貨物i經(jīng)過姿態(tài)調(diào)整后，將其代入公式（11），使局部空間利用率最高。

3 選貨策略

3.1 三空間貪心層疊法選貨策略

一方面，裝箱問題的NP-Hard 本質(zhì)，決定了精確求解算法難以實(shí)現(xiàn)，啟發(fā)式求解方法是求解該類問題的首選。另一方面，實(shí)際應(yīng)用中，由于約束條件多，且待裝箱體貨物類多、數(shù)量大，導(dǎo)致計(jì)算規(guī)模大，算法復(fù)雜度高，傳統(tǒng)的單一啟發(fā)式算法難以解決。因此，融合策略啟發(fā)式算法是解決該問題的有效思路之一。本文結(jié)合蟻群算法，提出了一種新的動(dòng)態(tài)融合策略優(yōu)化算法，用于求解三維裝箱問題。

針對(duì)蟻群算法有較強(qiáng)的尋優(yōu)性能、分布式并行計(jì)算、易于與其他方法相結(jié)合的優(yōu)點(diǎn)，以及算法運(yùn)行初期收斂速度慢、容易陷入局部最優(yōu)解等不足，本文構(gòu)建了按貨物體積大小和擺放次序?yàn)闆Q定因素的三空間貪心層疊法（GSM）選貨策略，用于前期選貨，彌補(bǔ)蟻群算法的收斂慢的不足，其步驟為：

步驟1初始化每個(gè)節(jié)點(diǎn)的信息素濃度。

步驟2判斷當(dāng)前空間是否是新開啟的一層，若是，選擇一個(gè)所能選擇的體積最大的待裝載貨物按照2.3節(jié)進(jìn)行擺放；若不是，直接轉(zhuǎn)到步驟3。

步驟3按照前一次擺放貨物的上-右-前的順序，并按照2.2節(jié)確定待裝載空間。

步驟4在步驟3 中確定的待裝載空間內(nèi)選擇一個(gè)能夠裝載的體積最大貨物，并按照2.3節(jié)進(jìn)行擺放，更新當(dāng)前節(jié)點(diǎn)的信息素濃度。

步驟5循環(huán)步驟2 至步驟4，直至本層都是殘余空間。

其中，考慮當(dāng)前待裝貨物i的前置貨物i-1，若vi+Δ≤vi-1，Δ∈[ ]0,C為常數(shù)，則放置規(guī)則為：

上述規(guī)則使貨物按（1）、（2）、（3）次序所確定放置方向，并調(diào)整放置姿態(tài)，否則終止裝箱。本策略確保當(dāng)前待裝載空間盡可能裝滿，并且使所裝載貨物盡可能規(guī)整。

3.2 三空間蟻群層疊法選貨策略

通過GSM 算法的前期計(jì)算，使得信息素濃度有較大提升，此時(shí)采用蟻群算法能發(fā)揮其快速收斂的優(yōu)勢。因此本文基于三空間分解法構(gòu)建了三空間蟻群層疊法（ASM）選貨策略用于后期選貨，其規(guī)則為：

步驟1判斷當(dāng)前節(jié)點(diǎn)信息素濃度是否達(dá)到有效范圍，若是，則利用當(dāng)前節(jié)點(diǎn)信息素；若不是，則初始化當(dāng)前節(jié)點(diǎn)信息素濃度。

步驟2判斷當(dāng)前空間是否是新開啟的一層，若是，選擇一個(gè)能夠裝載的體積最大貨物，按照2.3 節(jié)進(jìn)行擺放，并進(jìn)行下一步；若不是，轉(zhuǎn)到步驟3。

步驟3按照前一次擺放貨物的上-右-前的順序，并按照2.2節(jié)確定待裝載空間。

步驟4根據(jù)節(jié)點(diǎn)信息素濃度及算子序列等確定待裝載貨物，并按照2.3節(jié)進(jìn)行擺放。

步驟5更新信息素濃度，重復(fù)步驟2到步驟5，直至當(dāng)前層都為殘余空間。

步驟6開啟新的一層，判斷當(dāng)前層能否裝載貨物，若能，則轉(zhuǎn)到步驟2；若不能，將螞蟻數(shù)加1，更新信息素濃度。

步驟7判斷螞蟻數(shù)是否達(dá)到最大螞蟻數(shù)，若是，結(jié)束裝載，輸出最優(yōu)裝載鏈；否則執(zhí)行步驟1。放置規(guī)則如3.1節(jié)中（1）、（2）、（3）所示。

3.3 動(dòng)態(tài)融合策略

若能控制兩個(gè)階段中GSM 算法與ASM 的參與程度，則能更好地將兩種算法動(dòng)態(tài)融合，發(fā)揮各自算法優(yōu)勢的同時(shí)，解決好解的隨機(jī)多樣性問題。本文通過構(gòu)造具有均勻隨機(jī)分布函數(shù)與正態(tài)分布函數(shù)相比較的方法確定選貨方式。

對(duì)均勻隨機(jī)分布函數(shù)，采用C++中偽隨機(jī)數(shù)生成函數(shù)rand()，其當(dāng)前時(shí)刻t產(chǎn)生0-RAND_MAX之間的隨機(jī)數(shù)，RAND_MAX 為所有隨機(jī)數(shù)中的最大值，為便于比較對(duì)其進(jìn)行歸一化處理，即：

這里R(t)∈[0,1]。

對(duì)正態(tài)分布函數(shù)P(t)，為便于比較，取對(duì)稱軸右側(cè)大于零的部分，且進(jìn)行歸一化處理，即：

其中，ct是當(dāng)前迭代次數(shù)，則P(ct)∈[0,1]。在求解過程中，二者動(dòng)態(tài)融合的選貨概率規(guī)則如下：當(dāng)R(t)-P(t)≤0 時(shí)，采用三空間貪心層疊法進(jìn)行選貨；當(dāng)R(t)-P(t)>0時(shí)，采用三空間蟻群層疊法進(jìn)行選貨。如圖9所示為與迭代次數(shù)t相關(guān)的差值圖。

圖9 兩種選貨策略動(dòng)態(tài)融合示意圖Fig.9 Schematic diagram of dynamic hybrid of two selection methods

從圖9 可以看出，在算法初期采用GSM 概率較大（橫軸以下的范圍），但也存在一定概率選用ASM（橫軸以上的范圍）；隨著迭代次數(shù)的增加，采用ASM 的概率逐漸增大，但仍存在采用GSM的概率。

因此，可以實(shí)現(xiàn)求解初期以GSM 為主，ASM 算法為輔，后期以ASM算法為主，GSM算法為輔，并且兩種算法在前后兩個(gè)階段參與程度可控。

4 快速求解策略

4.1 信息素存取數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)

上述算法的快速求解有賴于大量信息素的存取設(shè)計(jì)，本文分別提出并設(shè)計(jì)了如下策略以實(shí)現(xiàn)快速求解。

螞蟻的每一次迭代查找以及對(duì)信息素進(jìn)行更新的過程中，都需要對(duì)信息素進(jìn)行查詢，識(shí)別出裝載貨物的種類、每種貨物的裝載數(shù)量以及裝載序列等信息，隨著問題求解規(guī)模變大，信息素的存取結(jié)構(gòu)對(duì)算法的運(yùn)算效率至關(guān)重要。由于問題規(guī)模無法在算法設(shè)計(jì)時(shí)確定，難以確定表規(guī)模大??；采用一般的哈希表結(jié)構(gòu)不易于對(duì)其進(jìn)行遍歷，而紅黑樹是一種自平衡二叉查找樹，能夠保障在最壞的情況下，查詢、插入或刪除的時(shí)間復(fù)雜度都為O(logn)，故本文采用紅黑樹對(duì)裝載信息進(jìn)行存取。其中，節(jié)點(diǎn)鍵碼表示當(dāng)前情況下裝載貨物的種類及各種貨物的裝載數(shù)量，節(jié)點(diǎn)的鍵值表示當(dāng)前情況下信息素值的大小。

對(duì)于鍵碼本文設(shè)計(jì)了一種新的狀態(tài)值表示方法。設(shè)貨物的種類數(shù)為K，則狀態(tài)字的結(jié)構(gòu)如圖10所示。

圖10 狀態(tài)字表示形式Fig.10 State word representation

一般地，狀態(tài)值的形式化表示為：

其中，K為待裝貨物種類數(shù)，a為螞蟻編號(hào)。tk={0,1}表示第k種貨物是否裝載，1 表示已裝載，0 表示未裝載。[0 …0]由0或1二進(jìn)制碼組成的Q位數(shù)，表示第k種貨物裝載數(shù)量，最大可裝載2Q-1 個(gè)貨物。以K×(1+Q)位二進(jìn)制碼作為狀態(tài)值，為樹結(jié)構(gòu)的key值，信息素量為value 值。信息素的value 值函數(shù)形式化表示如下：

其中，中括號(hào)內(nèi)分別對(duì)應(yīng)貨物種類i、貨物i擺放方式、貨物i左下角坐標(biāo)、貨物i長寬高、貨物i擺放后集裝箱殘余空間大小。由于組合爆炸的原因?qū)е驴尚薪饪臻g巨大，本文基于信息素存儲(chǔ)方法，設(shè)計(jì)了剪枝策略，去掉其中明顯不符合裝載目標(biāo)的裝載鏈，提高算法的運(yùn)行效率。

4.2 剪枝矩陣

本文所針對(duì)的問題規(guī)模大，且無法在算法運(yùn)行初期確定，若采用窮盡搜索，當(dāng)解空間較大時(shí)，算法時(shí)間復(fù)雜度也會(huì)相應(yīng)增大?？紤]到有的解在運(yùn)行初期就產(chǎn)生大量殘余空間，明顯無法達(dá)到算法所要求的近似最優(yōu)解，沒有計(jì)算必要，因此算法并沒有對(duì)每一個(gè)解都進(jìn)行完全計(jì)算。

采用剪枝策略，即通過設(shè)立特定的過濾條件，提前減少不必要的搜索路徑，可大大降低算法的時(shí)間復(fù)雜度。本文將VR（殘余空間）的大小作為過濾條件，殘余空間大小反映本條路徑的好壞，既提高了算法運(yùn)行準(zhǔn)確性，又大大降低算法的時(shí)間復(fù)雜度。

根據(jù)上一層已經(jīng)得到的當(dāng)前最優(yōu)結(jié)果，決定當(dāng)前的搜索是否還需要繼續(xù)。通過查詢狀態(tài)值和閑置空間大小建立的紅黑樹進(jìn)行剪枝操作。

設(shè)K為貨物類型數(shù)，T*i為對(duì)第i個(gè)箱體擺放后對(duì)應(yīng)的最優(yōu)類型域，Q*i為對(duì)應(yīng)的最優(yōu)數(shù)量域，VR*為對(duì)應(yīng)的殘余空間。

若存在螞蟻a對(duì)第i個(gè)箱體進(jìn)行空間擺放后，所對(duì)應(yīng)的類型域?yàn)?，?duì)應(yīng)的數(shù)量域?yàn)椋錃堄嗫臻g為且

當(dāng)前螞蟻b，在某時(shí)刻完成擺放后對(duì)應(yīng)類型域?yàn)椋瑢?duì)應(yīng)的箱體數(shù)域?yàn)?，其殘余空間為

當(dāng)Tai=Tbi且Qai=Qbi時(shí)：

當(dāng)狀態(tài)值相同時(shí)，擇優(yōu)存儲(chǔ)裝載鏈并更新剪枝矩陣，在剪枝矩陣中，每一個(gè)狀態(tài)值對(duì)應(yīng)一條當(dāng)前最優(yōu)裝載鏈。而狀態(tài)值只與裝載貨物的種類、數(shù)量有關(guān)，每一個(gè)狀態(tài)值只保存一條最優(yōu)裝載鏈信息，從而有效縮減了問題的解空間。

5 算法流程

本文提出了一種新的基于空間劃分與合并融合策略的啟發(fā)式算法，以此求解上述集裝箱裝載問題。首先，利用啟發(fā)式算法的局部最優(yōu)收斂性，得到一組粗略的解，并用該粗略解充實(shí)蟻群算法的信息素信息。其次，利用蟻群算法的潛在并行性、正反饋性及全局收斂性獲得最優(yōu)解。本算法相關(guān)參數(shù)設(shè)定如表3所示，其中ρ、α、β的取值來自于文獻(xiàn)[22]，m和CT的取值根據(jù)實(shí)踐經(jīng)驗(yàn)兼顧優(yōu)化效果與運(yùn)行時(shí)間后確定。

表3 算法參數(shù)取值Table 3 Algorithm parameter values

算法的具體的算法步驟如下所示。

步驟1初始化數(shù)據(jù)：貨物總數(shù)量N、貨物的種類數(shù)n、最大螞蟻數(shù)量AntNum、當(dāng)前螞蟻數(shù)m、貨物與集裝箱的尺寸和數(shù)量、初始時(shí)刻各路徑上的信息素均為τ0=C（v為常數(shù)）、剪枝矩陣信息、貨物裝載鏈信息（裝載順序、貨物的擺放方向以及貨物的坐標(biāo)等）、最大迭代次數(shù)CT。

步驟2判斷當(dāng)前迭代次數(shù)k是否大于最大迭代次數(shù)CT，若是則執(zhí)行步驟11；否則執(zhí)行步驟3。

步驟3判斷當(dāng)前螞蟻數(shù)m是否大于最大螞蟻數(shù)量AntNum，若是則將當(dāng)前迭代次數(shù)自增1后執(zhí)行步驟2；否則更新信息素信息。

步驟4若螞蟻i已經(jīng)裝載全部貨物或集裝箱已經(jīng)達(dá)到飽和，則將當(dāng)前螞蟻數(shù)m自增1 后執(zhí)行步驟3；否則，執(zhí)行步驟5。

步驟5查詢閑置空間集并重新對(duì)閑置空間進(jìn)行劃分和合并。

步驟6根據(jù)選貨概率公式確定貪心層疊法或蟻群層疊法作為本次選擇貨物方式，最終確定待裝載的貨物g。

步驟7確定貨物g的放置方向和姿態(tài)。

步驟8更新裝載鏈信息并生成狀態(tài)值。

步驟9依據(jù)狀態(tài)值查詢剪枝矩陣，若當(dāng)前對(duì)應(yīng)的殘余空間體積大于查詢獲取的值，則放棄當(dāng)前螞蟻m，直接選擇下一只螞蟻m+1；否則更新剪枝矩陣，將當(dāng)前螞蟻數(shù)m自增1并轉(zhuǎn)向步驟3，直至裝載完畢。

步驟10當(dāng)所有螞蟻完成一次循環(huán)后，各個(gè)路徑上的信息素濃度進(jìn)行實(shí)時(shí)更新。

步驟11更新迭代次數(shù)，若達(dá)到最大迭代次數(shù)CT后，從所有的裝載鏈中選擇最優(yōu)解輸出；否則，執(zhí)行步驟2。

6 實(shí)驗(yàn)驗(yàn)證

本文算法采用Visual Studio C++2017 開發(fā)，實(shí)驗(yàn)程序運(yùn)行在Ⅰntel?CoreTMi5-6500 CPU @ 3.20 GHz的處理器上，運(yùn)行內(nèi)存為8 GB。

本文采用了代表性測試數(shù)據(jù)集[4]進(jìn)行實(shí)驗(yàn)計(jì)算，該數(shù)據(jù)集為Bischoff和Ratcliff提出[4]的10組共1 000個(gè)算例，并與國內(nèi)外代表性求解算法的計(jì)算結(jié)果進(jìn)行了比較，比較結(jié)果如表4所示。

表4 多種算法對(duì)裝箱問題填充率及運(yùn)行時(shí)間比較Table 4 Comparison of filling rate and time of various algorithms for loading problem

通過對(duì)表4 所示的數(shù)據(jù)進(jìn)行分析可以發(fā)現(xiàn)：（1）隨著待裝載貨物種類的增加，箱體填充率呈下降趨勢。隨著貨物種類增加，相同種類的貨物裝載數(shù)量減少，必然造成剩余空間數(shù)量的增多，即需要不斷對(duì)剩余空間進(jìn)行合并，導(dǎo)致算法運(yùn)行效率降低，同時(shí)也造成箱體空間利用率下降。（2）在同時(shí)滿足方向約束與穩(wěn)定性約束的前提下求解三維布局優(yōu)化問題，從表4 中數(shù)據(jù)可以看出，獲得平均填充率由高到低的算法依次排序，第1 為BSG_VCS算法（填充率：94.60%）；第2為MOA算法（填充率：93.64%）；第3為是本文所提出的HSHA算法（填充率：93.59%）。同時(shí)也可以發(fā)現(xiàn)，在同時(shí)考慮兩種約束條件，且填充率相差不超過2%的前提下，運(yùn)行速度最快的是本文提出的HSHA 算法（運(yùn)行時(shí)間：69.96 s），本文算法運(yùn)行時(shí)間較之前文獻(xiàn)所述算法有較大的縮減。總體來說HSHA算法能夠以較快的速度對(duì)數(shù)據(jù)集進(jìn)行處理，具有較強(qiáng)的有效性與可行性。

表5 給出了融合策略啟發(fā)式算法實(shí)現(xiàn)強(qiáng)異類CLP時(shí)的一些測試細(xì)節(jié)，本文只考慮解決強(qiáng)異類裝箱問題，表中分別給出了10 組測例的運(yùn)行時(shí)間和填充率的Minimum（最小值）、Maxmum（最大值）及Average（平均值）。根據(jù)表5 可得圖11 的擬合關(guān)系，可以看出平均運(yùn)行時(shí)間與貨物種類是呈對(duì)數(shù)關(guān)系，也說明算法具有O(logn)的復(fù)雜度。

表5 HSHA在強(qiáng)異類集裝箱裝載時(shí)的測試細(xì)節(jié)Table 5 Test details of HSHA for strongly heterogeneous container loading

圖11 平均時(shí)間與貨物種類擬合關(guān)系Fig.11 Fitting relationship between average time and cargo type

7 結(jié)束語

本文提出了一種動(dòng)態(tài)融合策略啟發(fā)式算法，對(duì)單箱強(qiáng)異類問題進(jìn)行了綜合求解。通過聚類方法將強(qiáng)異類問題轉(zhuǎn)化為弱異類問題，使問題解空間提前收斂。設(shè)計(jì)了貨物局部空間姿態(tài)調(diào)整策略以及剩余空間合并策略以提高集裝箱空間利用率；設(shè)計(jì)了三空間貪心層疊法與三空間蟻群層疊法，并提出一種基于概率選擇的動(dòng)態(tài)融合算法，實(shí)現(xiàn)兩者優(yōu)勢互補(bǔ)且參與程度可控。此外，為了實(shí)現(xiàn)快速求解，構(gòu)建了狀態(tài)值與剪枝矩陣，在裝載過程中對(duì)每個(gè)狀態(tài)值擇優(yōu)存儲(chǔ)并更新剪枝矩陣，通過縮減問題的可行解空間，以加快求解速度。通過與公共數(shù)據(jù)集具體算例的運(yùn)行結(jié)果對(duì)比，在保證裝箱率的前提下，本文算法具有較好的競爭力。本文算法在填充率方面還有待進(jìn)一步提高，今后的研究將考慮在聚類方法和概率融合策略方面進(jìn)一步地改進(jìn)與優(yōu)化。