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

周勇

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

1 問題描述

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

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

2 模型搭建

符號(hào)說明：

以各集裝箱底面為XY平面、垂直底面向上為Z軸，以其左后下角為原點(diǎn)建立空間直角坐標(biāo)系。符號(hào)說明如下：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ì)量及其重心坐標(biāo)；Beari，BLi分別是貨物i所承受的重量及最大承受力；Bi，Ci分別是貨物編號(hào)、裝載順序編號(hào)。[conx1，conx2]，[cony1，cony2]，[0，conz]分別是x、y、z軸重心安全區(qū)間；（xi，yi，zi）是貨物i在集裝箱中的放置位置坐標(biāo)即左后下，右前上角坐標(biāo)。

3 混合遺傳算法設(shè)計(jì)

3.1 遺傳操作過程

選擇操作：

選擇過程采用輪盤賭與最佳個(gè)體保護(hù)策略。

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

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

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

4 實(shí)例驗(yàn)證

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

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

5 結(jié)語

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

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