基于類粒子群算法的集裝箱裝載模型優(yōu)化研究

連志剛，林蔚天，曹 宇，計(jì)春雷

(1. 上海電機(jī)學(xué)院 電子信息學(xué)院，上海 201306；2. 上海電機(jī)學(xué)院 電氣學(xué)院，上海 201306)

集裝箱運(yùn)輸(Container Transport)是指以集裝箱這種大型容器為載體，將貨物集合組裝成集裝單元，以便在現(xiàn)代流通領(lǐng)域內(nèi)運(yùn)用大型裝卸機(jī)械和大型載運(yùn)車輛進(jìn)行裝卸、搬運(yùn)作業(yè)和完成運(yùn)輸任務(wù)，從而更好地實(shí)現(xiàn)貨物“門到門”運(yùn)輸?shù)囊环N新型、高效率和高效益的運(yùn)輸方式。學(xué)界對(duì)集裝箱運(yùn)輸?shù)南嚓P(guān)研究比較豐富，但大部分都集中在泊位指派、船舶的卸載/裝載作業(yè)、集卡調(diào)度優(yōu)化、空箱調(diào)度、存儲(chǔ)與堆放物流的研究。關(guān)于集裝箱內(nèi)貨物的優(yōu)化裝載研究還是比較少，并都集中在基于啟發(fā)式規(guī)則的集裝箱貨物裝載問題[1-4]。基于優(yōu)化算法和集裝箱貨物裝載的研究較少，并且優(yōu)化的模型相對(duì)簡(jiǎn)單[5-6]，離指導(dǎo)實(shí)際工作還有很大差距。

通過研究運(yùn)籌學(xué)中集裝箱裝載的經(jīng)典實(shí)例，筆者發(fā)現(xiàn)其數(shù)學(xué)模型有缺欠，按照該模型無法指導(dǎo)集裝箱的貨物裝載，因此，建立了集裝箱裝載模型，并提出求解的方法，利用類粒子群算法對(duì)所建模型進(jìn)行優(yōu)化。仿真實(shí)驗(yàn)表明，該方法可行有效，對(duì)于提高運(yùn)輸資源利用率和運(yùn)輸組織效率都具有重要意義。

1 集裝箱裝載實(shí)例“數(shù)學(xué)模型”分析

集裝箱貨物裝載問題常使用的實(shí)例見文獻(xiàn)[7]。該實(shí)例及數(shù)學(xué)模型問題詳細(xì)分析如下。

某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表1，那么兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大？

表1 承載貨物

依照文獻(xiàn)[7]，該數(shù)學(xué)模型建立如式(1)。

設(shè)甲、乙兩種貨物托運(yùn)箱數(shù)分別為x1，x2，建立的數(shù)學(xué)規(guī)劃如下。

Maxz=20x1+10x2

(1)

模型(1)比較簡(jiǎn)單，且有嚴(yán)重缺欠。下面用簡(jiǎn)單的反例分析上述模型根本不能指導(dǎo)實(shí)際，幾乎毫無意義。

反例：某廠擬用集裝箱托運(yùn)一種貨物，每箱體積、重量、可獲利潤(rùn)以及托運(yùn)工具的大小及承重限制如表2，那么該種貨物托運(yùn)多少箱，可使獲得利潤(rùn)最大？

表2 承載貨物特征

若參照文獻(xiàn)[7]，設(shè)貨物托運(yùn)箱數(shù)為x，則建立的數(shù)學(xué)模型如下：

Maxz=20x

(2)

若按照模型(2)組織托運(yùn)，因x=2是該模型(2)的解，即托運(yùn)貨物2箱，可獲得最大利潤(rùn)為4 000元。這很顯然存在錯(cuò)誤，因?yàn)橥羞\(yùn)貨物是箱裝，不能擠壓變形，現(xiàn)實(shí)當(dāng)中是1箱都不能托運(yùn)，因?yàn)樨浳锍L(zhǎng)，根本不能放入。

2 集裝箱貨物裝載數(shù)學(xué)模型及其優(yōu)化

2.1 集裝箱貨物裝載數(shù)學(xué)模型

裝箱問題是指將不同尺寸的物品擺放入有一定容量的容器中, 以獲得某種最佳的效益。裝箱問題是一個(gè)具有復(fù)雜約束條件的組合優(yōu)化問題，在理論上屬NP-hard問題。目前所流行的求解集裝箱裝載問題的方法，還沒有一種能有效地求解一切裝箱問題。下面以實(shí)例分析，先建立集裝箱貨物裝載問題數(shù)學(xué)模型。

某廠擬用集裝箱托運(yùn)貨物，每箱體積、重量、可獲利潤(rùn)以及托運(yùn)工具大小及承重限制如表3，那么貨物各托運(yùn)多少箱，如何裝載可使獲得利潤(rùn)為最大？

表3 承載貨物清單

設(shè)D1，D2，…，Dn貨物托運(yùn)箱數(shù)分別為x1，x2，…，xn，其數(shù)學(xué)模型如下：

(3)

模型(3)是一個(gè)整數(shù)規(guī)劃，其求解比較復(fù)雜，更難的是“裝載的貨物最優(yōu)擺放后不能超過裝載限制的長(zhǎng)、寬、高”。也就是貨物裝載的時(shí)候，橫或豎擺放不同直接影響空間的利用效率。不同的擺放方式尋優(yōu)，其實(shí)就是組合優(yōu)化。下面初步探討模型(3)的求解。

2.2 集裝箱貨物裝載問題求解

集裝箱貨物裝載一般都是從內(nèi)到外，從下到上，從左到右(從右到左原理相同)依次裝載，至裝滿為止，如圖1。

圖1 集裝箱貨物裝載方式Fig.1 Container loading goods mode

針對(duì)模型(3)的復(fù)雜性，筆者采用迭代進(jìn)化的方法對(duì)其求解。

在數(shù)組G1的元素中，可能有m個(gè)相同，其表示該裝載方案中有m個(gè)相同的貨物；軸對(duì)稱相等的邊可以看作是同一條邊；初始解G1表示，以原點(diǎn)為起始點(diǎn)進(jìn)行裝載，第1個(gè)貨物Di的裝載方式為li，bi，hi邊分別與Y，X，Z軸平行；接著裝載貨物Dj，其裝載方式為lj，bj，hj邊分別與Dk貨物的li，bi，hi邊平行；依次類推，直到超出集裝箱的長(zhǎng)、寬、高任何一個(gè)限制即退出。不妨假設(shè)裝載到貨物Dk時(shí)，超出了集裝箱長(zhǎng)的限制。

解G2表示以原點(diǎn)為起始點(diǎn)進(jìn)行裝載，第一個(gè)貨物Ds的裝載方式為hs，ls，bs邊分別與Y，X，Z軸平行；接著裝載貨物Di，其裝載方式為li，hi，bi邊分別與Ds貨物的hs，ls，bs邊平行；依次類推，直到超出集裝箱的長(zhǎng)、寬、高任何一個(gè)限制即退出。不妨假設(shè)裝載到貨物Dt時(shí)，超出了集裝箱長(zhǎng)的限制。重組、迭代時(shí)，數(shù)組的元素互相“交互”，元素內(nèi)元素也互相“交換”。

步驟5：當(dāng)?shù)Ｖ箺l件滿足，輸出數(shù)組，即為裝載方案。

下面將用類粒子群優(yōu)化算法進(jìn)行詳細(xì)模擬，從而徹底解決模型(3)的求解問題。

3 類粒子群優(yōu)化算法

3.1 類粒子群優(yōu)化算法編碼

最初提出來的PSO算法是一種基于迭代的優(yōu)化工具[8-10]。系統(tǒng)初始化為一組隨機(jī)解，通過迭代搜尋最優(yōu)值，并沒有遺傳算法用的交換(Crossover)以及變異(Mutation)，而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。目前已廣泛應(yīng)用于函數(shù)優(yōu)化，神經(jīng)網(wǎng)絡(luò)訓(xùn)練，模糊系統(tǒng)控制以及其他遺傳算法的應(yīng)用領(lǐng)域，但關(guān)于OPSO算法應(yīng)用于NP難的調(diào)度問題，報(bào)道比較鮮見。

Z.G.Lian，等[11-12]曾用整數(shù)編碼方法，借鑒OPSO算法的思想及遺傳算法(Genetic Algorithm, GA)交換(Crossover)操作，采用整數(shù)編碼，提出類粒子群算法(Similar Particle Swarm Optimization, SPSO)，并將其應(yīng)用于有效優(yōu)化FSSP。劉勇，等[13]利用隨機(jī)擴(kuò)散算法求解二次背包問題。

集裝箱貨物裝載也是一個(gè)特殊的背包問題。筆者基于其思想，用類粒子群優(yōu)化算法解決貨物裝載問題。下面以10箱待裝貨物為例，介紹一些類粒子群算法優(yōu)化貨物裝載問題的算子操作，其具體編碼如下。

類粒子群算法交換算子操作如圖2。

圖2 類粒子群算法交換操作示意Fig.2 Illustration of the various types of SPSO crossover operators with permutation strings

一段交換(C1)：在父代①和②粒子長(zhǎng)度內(nèi)隨機(jī)選擇兩個(gè)交換點(diǎn)，將父代①和②交換點(diǎn)內(nèi)的裝載貨物對(duì)應(yīng)復(fù)制到半子代，然后將其互換，如圖2(a)。

兩段交換(C2)：在父代①和②粒子長(zhǎng)度內(nèi)隨機(jī)選擇兩對(duì)交換點(diǎn)，將父代①和②交換點(diǎn)內(nèi)的裝載貨物對(duì)應(yīng)復(fù)制到半子代，然后將其互換，如圖2(b)。

三段交換(C3)：類似兩段交換，如圖2(b)。

類粒子群算法變異算子操作如圖3。

圖3 類粒子群算法中的變異操作示意Fig.3 Illustration of the shift types of SPSO with permutation strings

一段移動(dòng)插入(M1)：在父代隨機(jī)選擇一段待裝貨物，再移至父代的長(zhǎng)度內(nèi)隨機(jī)選擇的插入點(diǎn)后，如圖3(a)。

兩段移動(dòng)插入(M2)類似于一段移動(dòng)插入，如圖3(b)。

隨機(jī)選擇貨箱翻轉(zhuǎn)(M3)：在父代粒子長(zhǎng)度內(nèi)隨機(jī)選擇幾個(gè)待裝貨箱，然后分別隨機(jī)選擇翻轉(zhuǎn)點(diǎn)，將其翻轉(zhuǎn)點(diǎn)和貨箱長(zhǎng)交換，如圖3(c)。

隨機(jī)選擇一段貨箱大翻轉(zhuǎn)(M4)：在父代粒子長(zhǎng)度內(nèi)隨機(jī)選擇一段待裝貨箱，將該段內(nèi)所有貨箱的長(zhǎng)、寬、高變?yōu)楦摺㈤L(zhǎng)、寬，如圖3(d)。

隨機(jī)選擇兩段貨箱大翻轉(zhuǎn)(M5)類似隨機(jī)選擇一段貨箱大翻轉(zhuǎn)，如圖3(d)。

隨機(jī)產(chǎn)生新的待裝貨箱排序(M6)：如產(chǎn)生新種群內(nèi)新粒子一樣，隨機(jī)產(chǎn)生新的貨物裝載序列即可，如圖3(e)。

3.2 類粒子群優(yōu)化算法遞推方程

vi(k+1)=pi(k)⊕pg(k)

(4)

(vr1,vr2,…,vrN)(k+1)=M(vr1,vr2,…,vrN)

(5)

xi(k+1)=xi(k)⊕vi(k+1)

(6)

(xr1,xr2,…,xrN)(k+1)=M(xr1,xr2,…,xrN)

(7)

4 類粒子群算法解決貨物裝載仿真

4.1 貨物裝載實(shí)例模型

貨物裝載問題為組合爆炸問題，該組合爆炸問題最優(yōu)解搜索空間非常大，很難搜索到其最優(yōu)解，有時(shí)智能算法搜索到近似解，也很難判斷其是否為最優(yōu)解。為了檢測(cè)筆者提出的類粒子群算法優(yōu)化貨物裝載問題的可行性，下面給出一個(gè)測(cè)試實(shí)例，進(jìn)行模擬實(shí)驗(yàn)。為了用數(shù)學(xué)原理容易找出其最優(yōu)解，并與筆者提出的智能算法搜索的最優(yōu)解進(jìn)行對(duì)比，本實(shí)例不妨設(shè)定的裝載器具、貨物尺寸比較特殊。該實(shí)例的集裝箱也可理解為散貨船的船艙，裝載的貨物是不同大小的木箱。該實(shí)例及數(shù)學(xué)模型問題詳細(xì)分析如下。

某廠擬用集裝箱托運(yùn)1種貨物，每箱的長(zhǎng)、寬、高、重量、及托運(yùn)所受限制如表4，那么該貨物最多能托運(yùn)多少箱？貨物所受體積和重量的最大限制如表4。

表4 承載貨物實(shí)例

(8)

該問題有許多種裝載方法，為組合爆炸問題。用常用的數(shù)學(xué)規(guī)劃方法解決模型(8)幾乎不可能。筆者采用類粒子群優(yōu)化算法解決。

4.2 類粒子群算法優(yōu)化貨物裝載實(shí)例模型

步驟3：輸出pgbest。

用類粒子群優(yōu)化算法搜索到了模型(8)的最優(yōu)解，其裝載方法是(30,10,20)針對(duì)x,y,z軸的長(zhǎng)、寬、高。分別裝長(zhǎng)5箱、寬3箱，高2箱，共裝載30箱。筆者用類粒子群算法及遺傳算法對(duì)模型(8)進(jìn)行優(yōu)化并比較收斂效果，其收斂結(jié)果見圖4。

圖4 類粒子群和遺傳算法優(yōu)化模型(8)的收斂曲線Fig.4 Convergence contrast figure of SPSO and GA algorithmsfor model (8)

從圖4明顯可以看出類粒子群優(yōu)化貨物裝載模型可行、有效，比GA收斂速度快，并且搜索到得最優(yōu)解好。

5 結(jié) 語

分析發(fā)現(xiàn)運(yùn)籌學(xué)中被廣泛使用的一個(gè)集裝箱貨物裝載實(shí)例數(shù)學(xué)模型的缺欠，并建立了適合集裝箱運(yùn)輸實(shí)際的集裝箱貨物裝載模型，提出求解所建模型方法，利用類粒子群算法對(duì)所建模型進(jìn)行優(yōu)化，仿真實(shí)驗(yàn)表明，該方法可行有效，為該類問題的優(yōu)化尋找了一條新的途徑與方法。

筆者只分析了長(zhǎng)方體的同一種貨物在集裝箱中優(yōu)化裝載的問題。其實(shí)當(dāng)貨物裝載約束條件多時(shí)，如不同種類的貨物，大小、重量各異，且貨物托運(yùn)時(shí)某些易損品上面壓力有限制；還有其他球體，錐體及

不規(guī)則體等貨物時(shí)，其建模及優(yōu)化更加復(fù)雜，是未來研究的一個(gè)努力方向。

該文獲得連城物流www.1885656.com;www.11056.net的支持。

[1] George J A,Robinson D F.A heuristic for packing boxes into a container [J].Computers & Operational Research,1980,7(3):147-156.

[2] Pisinger D.Heuristics for the container loading problem [J].European Journal of Operational Research,2002,141(2):382-392.

[3] 劉霞,呂漢興.集裝箱裝載矩形貨物的一種啟發(fā)式算法[J].起重運(yùn)輸機(jī)械,2003(1):16-18.

Liu Xia,Lv Hanxing.A heuristic for packing rectangular boxes in a container [J].Hoisting and Conveying Machinery,2003(1):16-18.

[4] 閻威武,邵惠鶴,田雅杰.集裝箱裝載的一種啟發(fā)式算法[J].信息與控制,2002,31(4):353-356.

Yan Weiwu,Shao Huihe,Tian Yajie.A heuristic algorithm for three dimension packing problem [J].Information and Control,2002,31(4):353-356.

[5] Gehring H,Bortfeldt A.A genetic algorithm for solving the Container loading problem [J].International Transactions in Operational Research,1997,4(5/6):401-418.

[6] 卜雷,尹傳忠,蒲云.集裝箱運(yùn)輸多箱三維裝載優(yōu)化問題的遺傳算法 [J].鐵道學(xué)報(bào),2004,26(2):21-25.

Bu Lei,Yin Chuanzhong,Pu Yun.Genetic algorithm for resolution of the three-dimensional multi-bin packing optimization problem in container transportation [J].Journal of the China Railway Society,2004,26(2):21-25.

[7] 錢頌迪.運(yùn)籌學(xué)[M].修訂版.北京:清華大學(xué)出版社,2004.

Qian Songdi.Operational Research [M].Revision ed. Beijing :Tsinghua University Press,2004.

[8] Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//Proceedings of the 6thInternational Symposium on Micro Machine and Human Science.Nagoya,Japan:IEEE,1995:39-43.

[9] 連志剛,焦斌.一種混合搜索的粒子群算法[J].控制理論與應(yīng)用,2010,27(10):1404-1410.

Lian Zhigang,Jiao Bin.Particle-swarm optimization algorithm with mixed search [J].Control Theory & Applications,2010,27(10):1404-1410.

[10] 許昆,李智勇.改進(jìn)的量子粒子群多目標(biāo)優(yōu)化算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30 (1):164-167.

Xu Kun,Li Zhiyong.Quantum particle swarm optimization method for multi-objective optimization [J].Computer Engineering and Design,2009,30 (1):164-167.

[11] Lian Zhigang,Gu Xingsheng,Jiao Bin.A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan [J].Applied Mathematics and Computation,2006,175(1):773-785.

[12] Lian Zhigang,Jiao Bin,Gu Xingsheng.A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan [J].Applied Mathematics and Computation,2006,183(2):1008-1017.

[13] 劉勇,馬良.隨機(jī)擴(kuò)散算法求解二次背包問題[J].控制理論與應(yīng)用,2011,28(8):1140-1144.

Liu Yong,Ma Liang.Stochastic diffusion search algorithm for quadratic knapsack problem [J].Control Theory & Application,2011,28(8):1140-1144.