基于混合遺傳算法的多箱型集裝箱裝載問題研究

周勇

寰宇東方國際集裝箱（青島）有限公司 山東青島 266500

1 問題描述

多箱型集裝箱裝載問題可以描述為：在一定的約束條件下，將大量質(zhì)量不等、大小不同的貨物以適當?shù)难b載方法裝入到多個集裝箱中，其中待裝載集裝箱為常用的四種航空集裝箱（AMA、AKE、AMF、AAU集裝箱），使得滿足實際約束的情況下各集裝箱的體積利用率最大，以提高航空集裝箱運輸中對集裝箱的合理利用，從而降低運輸成本提高經(jīng)濟效益。

考慮到貨物實際裝箱問題的復雜性，作出如下假設：①貨物密度均勻，形狀均為長方體，尺寸各異且不大于集裝箱尺寸；②貨物由擠壓產(chǎn)生的微小形變可忽略；③貨物的碼放不受限制，可放置在箱內(nèi)任意位置。④貨物具有不同到站。

2 模型搭建

符號說明：

以各集裝箱底面為XY平面、垂直底面向上為Z軸，以其左后下角為原點建立空間直角坐標系。符號說明如下：n為待裝貨物總數(shù)量，N為航空集裝箱總數(shù)量；αij為0/1變量，貨物i裝入集裝箱j則值為1，否則值為0；λj為0/1變量，若集裝箱j被使用則為1，若未使用則為0；，jjMV為集裝箱j的最大載重量及容積：wi，hi，di，vi，mi，[gxi，gyi，gzi]是貨物i的長、寬、高、體積、質(zhì)量及其重心坐標；Beari，BLi分別是貨物i所承受的重量及最大承受力；Bi，Ci分別是貨物編號、裝載順序編號。[conx1，conx2]，[cony1，cony2]，[0，conz]分別是x、y、z軸重心安全區(qū)間；（xi，yi，zi）是貨物i在集裝箱中的放置位置坐標即左后下，右前上角坐標。

3 混合遺傳算法設計

3.1 遺傳操作過程

選擇操作：

選擇過程采用輪盤賭與最佳個體保護策略。

最佳個體保護策略：為保留最優(yōu)的算子，應盡可能地保證高評價值個體的存在，充分利用遺傳算法“適者生存”的特點，當生成新種群后，通過評價函數(shù)計算出本代中最差的個體，并用上代最優(yōu)的個體去替代，使得最優(yōu)個體得到保存。

3.2 混合遺傳算法裝載多箱型集裝箱的步驟

基于以上思想，加入模擬退火算子，用其突跳性使遺傳避免陷入局部最優(yōu)的情況。混合遺傳算法求解多箱型集裝箱具體步驟如下：第1步將集裝箱的型號、尺寸與貨物的基本信息輸入程序，并設置算法相關參數(shù)。第2步計算初始所需集裝箱數(shù)量N，對貨物編號進行預處理并確定問題采用的編碼方式。第3步采用隨機產(chǎn)生初始種群S的方式以方便進行全局搜索，保證算法的全局搜索優(yōu)越性，避免早熟現(xiàn)象的出現(xiàn)。第4步基于空間劃分的擬人式放置原則裝載初始數(shù)量的集裝箱。第5步判斷貨物是否剩余，若剩余，隨機打開新的集裝箱N：=N+1，轉步驟3；若貨物無剩余，轉第6步。第6步對現(xiàn)有種群進行以下操作，直到生成下一代新種群：計算種群中個體的評價函數(shù)值，利用輪盤賭實現(xiàn)個體選擇。

4 實例驗證

由表1可以看出，雖然貨物具有強異構性，且集裝箱形狀不規(guī)則，但四種不同集裝箱的平均體積利用率高于82%，在滿足實際裝載條件的前提下保證了較高的體積利用率，避免了不必要的空間浪費。

表1 航空集裝箱參數(shù)

5 結語

（1）模擬工人的操作經(jīng)驗與方法，設計了貨物的放置規(guī)則，采用罰函數(shù)處理重心約束、不重疊約束和承重約束，并加入最佳個體保護策略、模擬退火算子等進一步提高了遺傳算法的優(yōu)化效果。

（2）實驗部分通過性能測試，表明所提算法能夠較好的解決大規(guī)模貨物的裝載問題，并通過實際航空貨物裝載實驗，四種不同箱型的集裝箱體積利用率均高于82%，表明該算法能夠有效解決多箱型航空集裝箱的裝載問題。