多目標(biāo)蟻群算法在集裝箱配載問(wèn)題中的應(yīng)用

汪圓圓 陳順懷

(武漢理工大學(xué)交通學(xué)院高性能船舶技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 武漢 430063)

多目標(biāo)蟻群算法在集裝箱配載問(wèn)題中的應(yīng)用

汪圓圓 陳順懷

(武漢理工大學(xué)交通學(xué)院高性能船舶技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 武漢 430063)

針對(duì)集裝箱配載問(wèn)題，提出一種基于Pareto解集的蟻群算法以及基于權(quán)值分配的蟻群算法，采用分步式方法，將三維集裝箱裝載問(wèn)題分解為Bay位優(yōu)選和二維集裝箱裝載問(wèn)題.在保證倒箱量為零的策略下，以船舶中縱剖面彎矩值、重心橫向偏移、初穩(wěn)性高為目標(biāo)，以船舶吃水差值為約束條件，優(yōu)化集裝箱配載，從而達(dá)到提高集裝箱船裝載效率、節(jié)約裝載成本和時(shí)間并使集裝箱船獲得穩(wěn)定航行狀態(tài)的目的.

多目標(biāo)；蟻群算法；集裝箱；配載優(yōu)化

0 引 言

集裝箱船舶配載問(wèn)題是一個(gè)復(fù)雜的NP完全問(wèn)題[1]，配載的優(yōu)劣關(guān)系到船舶在港口裝卸貨物時(shí)效率的高低、船體強(qiáng)度，以及船舶穩(wěn)性的合理與否，除此之外，還需考慮如何通過(guò)合理配載來(lái)使船舶具有較合理的浮態(tài)，從而保證船舶的快速性.想要通過(guò)整體方法快速有效地解決集裝箱配載問(wèn)題基本不可能，因此，對(duì)于大型集裝箱船的配載問(wèn)題，一個(gè)較為明顯的做法就是對(duì)問(wèn)題進(jìn)行分解.

Gümü等[2]將集裝箱配載問(wèn)題分解為四步：①為每一目的港分派Bay位；②對(duì)Bay位中的每一層進(jìn)行分配；③進(jìn)行箱位分配；④當(dāng)某一個(gè)箱子放到某一個(gè)箱位后，計(jì)算其適應(yīng)度值.這四步分解能夠較好地解決大型集裝箱的配載問(wèn)題，但是其倒箱模型復(fù)雜，且目標(biāo)函數(shù)僅有倒箱，而將船舶的橫傾作為約束處理，實(shí)際上是一個(gè)單目標(biāo)優(yōu)化問(wèn)題.Ambrosino 等[3]將配載問(wèn)題分解為兩步，即首先根據(jù)目的港確定Bay位，而后對(duì)每一Bay位的集裝箱進(jìn)行優(yōu)化排布.張維英[4]在其博士論文中將此問(wèn)題分解為Bay位選擇和Bay位排箱兩個(gè)子問(wèn)題，針對(duì)Bay位排箱這一子問(wèn)題，給出了單一目的港和船舶掛靠多港的求解模型.而其求解模型以加權(quán)形式給出所謂多目標(biāo)的求解形式，或者是以倒箱量最少為目標(biāo)函數(shù)的單目標(biāo)形式，這樣的模型對(duì)于多目標(biāo)問(wèn)題來(lái)說(shuō)，顯然不是很合理.

集裝箱船在一個(gè)航次中一般都要掛靠多個(gè)港口，在配載過(guò)程中，就會(huì)出現(xiàn)先卸載箱被后卸載箱壓在下面的情況，這種情況稱為倒箱.倒箱的產(chǎn)生將會(huì)使船舶的裝載成本提高，船舶的經(jīng)濟(jì)效益減小.配載優(yōu)化的一個(gè)關(guān)鍵目標(biāo)就是盡可能減少倒箱.因此，很多關(guān)于配載優(yōu)化的文章都將減少倒箱量作為目標(biāo).

Dubrovsky等[5]提出了以倒箱數(shù)最少為目標(biāo)的基于緊湊編碼的遺傳算法，算法采用緊湊而高效的編碼方式縮小搜索域，在遺傳算法中加入局部?jī)?yōu)化策略，最終可以將倒箱數(shù)減少為零.但是，算法僅僅以倒箱數(shù)為目標(biāo)，屬于單目標(biāo)的優(yōu)化方式，船舶橫穩(wěn)性沒(méi)有得到有效的保證.張維英針對(duì)混合港Bay位排箱優(yōu)化問(wèn)題，以倒箱數(shù)最少為目標(biāo)，提出一種基于隱式圖啟發(fā)式搜索技術(shù)的Bay位排箱優(yōu)化算法，并且給出一個(gè)掛靠6個(gè)港口，含80個(gè)箱位的Bay位優(yōu)化算例.算法依然是基于單目標(biāo)的優(yōu)化方式，雖然可以減少倒箱量，但不能保證穩(wěn)性和左右均衡.

衛(wèi)家駿[6]提出一種針對(duì)集裝箱箱位分配問(wèn)題的混合蟻群算法，算法以裝船后所有箱子的合重心距船舶中縱排剖面的距離最小為目標(biāo)，在蟻群算法中加入禁忌算法，即將已選擇的螞蟻和其所選擇的箱位加入禁忌表，以此來(lái)避免算法陷入局部最優(yōu).很顯然，這樣的算法依然是針對(duì)單目標(biāo)問(wèn)題的，其實(shí)用性不大.

文中將集裝箱船舶配載問(wèn)題分解為縱向Bay位選擇和Bay位排箱優(yōu)化這樣兩個(gè)子問(wèn)題，采用控制倒箱量為零的策略，提出多目標(biāo)蟻群算法進(jìn)行優(yōu)化配載，實(shí)現(xiàn)了這兩步操作的無(wú)縫連接.先給出一個(gè)模擬Bay位排箱問(wèn)題的算例，最后給出一個(gè)實(shí)際集裝箱船配載算例.

1 配載問(wèn)題的數(shù)學(xué)模型

1.1 問(wèn)題描述

集裝箱船配載問(wèn)題是一個(gè)多目標(biāo)、多約束的復(fù)雜問(wèn)題，如前所述，問(wèn)題可以被分解為縱向Bay位選擇和Bay位排箱優(yōu)化這樣兩個(gè)子問(wèn)題，在縱向Bay位選擇問(wèn)題中，最關(guān)心的是船舶的結(jié)構(gòu)強(qiáng)度和船體的浮態(tài).Bay位排箱優(yōu)化問(wèn)題的一個(gè)最主要目標(biāo)就是減少倒箱量，倒箱的定義如下：當(dāng)在港口i卸載的集裝箱被在港口j卸載的集裝箱所阻礙時(shí)，便產(chǎn)生倒箱[7].很顯然，船舶將先在港口i港口停泊.在本算法中，采用基于零倒箱規(guī)則的方式來(lái)處理多港排箱中的倒箱問(wèn)題，即后卸載箱先裝、先卸載箱后裝的方式，這樣的裝箱方式可以確保在裝箱過(guò)程中不產(chǎn)生倒箱操作，避免了由于倒箱所帶來(lái)的數(shù)學(xué)模型的復(fù)雜性.第二個(gè)目標(biāo)是最小化重心的垂向高度，以此來(lái)提高船舶的初穩(wěn)性.第三個(gè)目標(biāo)是最小化重心到中線面的距離，以此確保船舶的左右均衡.

1.2 數(shù)學(xué)模型的建立

集裝箱船箱位排布俯視和側(cè)視圖見(jiàn)圖1～圖2.

圖1 箱位排布俯視圖

圖2 箱位排布側(cè)視圖

在圖1中，以L1，L2，…，Lm表示箱位的縱向排布順序，按自船首至船尾增序排列.其所包含的集裝箱數(shù)量分別為n1，n2，…，nm，重量分別為M1，M2，…，Mm，距船中的位置分別為x1，x2，…，xm，圖中顯示了TEU和FEU集裝箱的排布示意.

在圖2所示的Bay位圖中，最大列數(shù)為R，最大層數(shù)為T，由最底層往最上層依次裝載將于第Q，Q-1，…，k港卸載的集裝箱，每港占據(jù)若干Bay位，如果第i港有冗余箱，則冗余箱按由輕到重選擇，將冗余箱加至第i-1港的集裝箱中進(jìn)行排位.將坐標(biāo)原點(diǎn)取在船舶中縱剖面處，沿船寬方向?yàn)閅軸，垂向?yàn)閆軸，以Cij(y,z)代表Bay位中第i(i=k,k+1,…,Q)港第j(j=1,2,…,Ni)箱位的坐標(biāo)，其重量以w(y,z)表示.圖中數(shù)字表示箱位順序，即按從左到右、自下而上增序編號(hào).

假定某集裝箱船計(jì)劃掛靠P個(gè)港口，該船舶的某一Bay位共混裝Q個(gè)港口的集裝箱，其中，Q≤P， 并假定該Bay位共有N個(gè)箱位，Q個(gè)港口的集裝箱要裝滿這N個(gè)箱位.設(shè)每一港口集裝箱數(shù)目分別為N1，N2，…，NQ，以wi(i=1,2,…,N)代表每一集裝箱的重量.設(shè)該Bay位中在最前港卸載集裝箱的港口為k(k=1,2,…,Q)，所需裝載的集裝箱數(shù)目為Nk.

在一次優(yōu)化過(guò)程中，一個(gè)集裝箱只能占據(jù)一個(gè)箱位，一個(gè)箱位也只能被一個(gè)集裝箱占據(jù)，其數(shù)學(xué)表達(dá)形式為

(1)

對(duì)于某一個(gè)Bay位來(lái)說(shuō)，其重心的橫向和垂向位置為

(2)

(3)

式中：yj，zj為每一箱子的重心坐標(biāo).

對(duì)于每一港口及整個(gè)Bay位的集裝箱重心位置的表示與其類似，限于篇幅，這里直接給出全船集裝箱重心橫向和垂向位置為

(4)

(5)

(6)

f2=YG

(7)

f3=ZG

(8)

(9)

p(r,c)≥p(r+1,c)

(10)

(11)

(12)

(13)

(14)

式(9)為變量值只能為0或1；式(10)為在某一列中，上層集裝箱的卸載港要在下層集裝箱的卸載港前；式(11)為所裝載的集裝箱總數(shù)要不超過(guò)船舶的箱位數(shù)；式(12)為每一列的集裝箱數(shù)目不能大于該列的箱位總數(shù)；式(13)為船舶最好有一定的尾傾；式(14)為船舶的縱向強(qiáng)度約束，其中s為一與船長(zhǎng)和排水量相關(guān)的常數(shù).

2 多目標(biāo)蟻群算法

2.1 多目標(biāo)蟻群算法的數(shù)學(xué)模型

蟻群算法(ant colony optimization, ACO)最早成功應(yīng)用于TSP(travelling salesmen problem)問(wèn)題，集裝箱配載問(wèn)題與TSP問(wèn)題類似，故應(yīng)用蟻群算法求解集裝箱配載問(wèn)題.

石榴采摘后能有多種用途。個(gè)頭大，汁多味甜的石榴用于出售給消費(fèi)者食用。外觀不好，但是酸甜可口的石榴被送到工廠進(jìn)行產(chǎn)品加工，制成石榴汁進(jìn)行售賣。而味道酸澀的石榴將被用作制作石榴酒，石榴醋等產(chǎn)品。而剩余的石榴皮可以曬干后進(jìn)行賣入中藥店用作藥材。而剩下的石榴籽可以加工精油進(jìn)行出售，或者賣入化妝品生產(chǎn)公司進(jìn)行深加工。而老了的果樹(shù)進(jìn)行加工后，可以制作成為觀賞價(jià)值較高的盆景。由于石榴的多種用途，給石榴種植產(chǎn)業(yè)化發(fā)展提供了有利的條件。

進(jìn)行蟻群算法的前提是要構(gòu)建距離函數(shù)，在多目標(biāo)蟻群算法中，針對(duì)每一個(gè)目標(biāo)，都需要定義合適的距離函數(shù)，距離函數(shù)的定義依據(jù)的是目標(biāo)函數(shù)，因此，將距離函數(shù)定義為

(15)

式中：c為箱位坐標(biāo)，包括x,y與z軸坐標(biāo)；w為箱重.

蟻群算法的另一個(gè)關(guān)鍵點(diǎn)是螞蟻選擇某一路徑的概率函數(shù)的定義，文中概率函數(shù)的定義與基本蟻群算法一致.

在每一只螞蟻遍歷完所有城市后，要對(duì)殘留信息素進(jìn)行更新，按照蟻周模型對(duì)信息素進(jìn)行更新.

2.2 多目標(biāo)蟻群算法

在對(duì)多目標(biāo)蟻群算法中的一些要素進(jìn)行定義以后，就可以進(jìn)行算法的具體實(shí)現(xiàn)，實(shí)現(xiàn)步驟如下：

步驟1 設(shè)置初始參數(shù)，循環(huán)次數(shù)Tc=0，初始化各路徑下的信息素量τij=常數(shù)，Δτij=0，建立禁忌表Tabu.

步驟2 對(duì)將在第Q港卸載的NQ個(gè)集裝箱進(jìn)行Bay位優(yōu)化，將mQ只螞蟻隨機(jī)放在NQ個(gè)箱位上循環(huán)次數(shù)TQ,C=1，針對(duì)不同目標(biāo)函數(shù)，計(jì)算螞蟻選擇城市j的概率，按輪盤賭規(guī)則選擇螞蟻將要移動(dòng)到的箱位，并將之加入到禁忌表中，直到訪問(wèn)完所有箱位.存儲(chǔ)mQ只螞蟻的路徑.

步驟3 對(duì)信息素量進(jìn)行更新.

步驟4 如果TQ,C=TQ,max，則循環(huán)結(jié)束，將所有mQ×TQ,max條路徑暫存；否則，TQ,C=TQ,C+1，禁忌表清空，返回步驟2.

步驟5 根據(jù)步驟4存儲(chǔ)的mQ×TQ,max條路徑計(jì)算YgQi，ZgQi，并兩兩進(jìn)行比較，保留其中的非劣路徑.

步驟6 對(duì)其他港進(jìn)行相同操作.

步驟7 根據(jù)將在第k～Q港卸載的集裝箱箱位優(yōu)化選擇結(jié)果計(jì)算Yg，Zg，得到一個(gè)Pareto前沿.

以上是一種基于Pareto前沿的多目標(biāo)蟻群算法的基本步驟，這種算法可求得多組解，提供多種可選方案.除此之外，還可以以加權(quán)方式來(lái)求解多目標(biāo)問(wèn)題，這里不再贅述.加權(quán)方式算法簡(jiǎn)潔，但所得結(jié)果與權(quán)值選取有很大關(guān)聯(lián)，且所能提供的可選方案少，而上述算法結(jié)果多樣，所能提供的方案較多，且比較快速.

3 結(jié)果與分析

3.1 算例1

假定船舶某一Bay位共有30個(gè)箱位[8]，裝載將在4個(gè)港口卸載的集裝箱，每一個(gè)集裝箱都為標(biāo)準(zhǔn)箱，將寬計(jì)為兩個(gè)單位長(zhǎng)度，則高為2.125 5個(gè)單位長(zhǎng)度.港口排序按由近到遠(yuǎn)的增序排列，在第4港卸載的集裝箱數(shù)目為6，第3港為8，第2港為12，第1港為4，起點(diǎn)港為第0港.箱子的初始重量(單位：104N)排布見(jiàn)圖3.

圖3 重量初始排布圖

Bay位重心坐標(biāo)：Yg=6.125 m，Zg=7.117 m.取α=1，β=2，ρ=0.2，Q=50，計(jì)算50代，優(yōu)化后，結(jié)果見(jiàn)圖4.

圖4 優(yōu)化排布結(jié)果

由非劣解所組成的Pareto前沿見(jiàn)圖5，由圖5可知，Bay位的重心縱向和垂向距離都能夠得到優(yōu)化解集.而倒箱量可嚴(yán)格控制為0.

圖5 Bay位排箱優(yōu)化后的Pareto前沿

3.2 算例2

對(duì)文獻(xiàn)[4]中的“冰河”號(hào)在起始港進(jìn)行Bay位優(yōu)化，取α=1，β=2，ρ=0.2，Q=50，采用分步策略，重心垂向坐標(biāo)權(quán)值取為0.5，橫向偏移權(quán)值取為0.5.結(jié)果見(jiàn)表1(限于篇幅，僅給出部分結(jié)果)，其中a為該Bay位所有集裝箱總重量之和，優(yōu)化前與優(yōu)化后的比較見(jiàn)表2.

優(yōu)化后，中縱剖面彎矩減少了2.44%，吃水差絕對(duì)值下降14.2%，初穩(wěn)性高增加43.5%，重心橫向基本無(wú)偏移.

表1 部分“冰河”號(hào)配載優(yōu)化結(jié)果圖(Bay27)

表2 優(yōu)化前后結(jié)果比較

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

文中提出一種基于Pareto解集的蟻群算法，采用不倒箱策略，對(duì)集裝箱配載問(wèn)題進(jìn)行了優(yōu)化求解，利用基于權(quán)值分步的蟻群算法，給出一個(gè)全船集裝箱配載實(shí)例，并進(jìn)行了比較，結(jié)果表明，這兩種蟻群算法都大大節(jié)約了優(yōu)化求解時(shí)間，能夠?qū)⑴漭d問(wèn)題中最為重要的倒箱量指標(biāo)嚴(yán)格控制為0，對(duì)集裝箱船的重心、吃水差以及結(jié)構(gòu)強(qiáng)度也有較大程度的優(yōu)化.

[1]AVRIEL M, PENN M, SHPIRER N. Container ship stowage problem: complexity and connection to the coloring of circle graphs[J]. Discrete Applied Mathematics,2000,103(1):271-279.

[2]GüMü M, KAMINSKY P, TIEMROTH E, et al. A multi-stage decomposition heuristic for the container stowage problem[J]. Journal of Heuristics,2008(1):55-58.

[3]AMBROSINO D, SCIOMACHEN A, TANFANI E. A decomposition heuristics for the container ship stowage problem[J]. Journal of Heuristics,2006,12(3):211-233.

[4]張維英.集裝箱船全航線配載智能優(yōu)化研究[D].大連：大連理工大學(xué),2005.

[5]DUBROVSKY O, LEVITIN G, PENN M. A genetic algorithm with a compact solution encoding for the container ship stowage problem[J]. Journal of Heuristics,2002(8):585-599.

[6]衛(wèi)家駿.集裝箱船智能配載研究[D].大連：大連海事大學(xué),2012.

[7]BENEDITO M, SANTOS A. Evolutionary algorithm and ant colony optimization for a container stowage problem[J]. Discrete Applied Mathematics,2015(2):356-363.

[8]張維英,林焰,紀(jì)卓尚,等.基于指派問(wèn)題的Bay位排箱優(yōu)化模型與算法[J].大連理工大學(xué)學(xué)報(bào),2011,51(1):61-67.

Multi-objective Ant Colony Algorithms for Solving Container Loading Plan Problem

WANG Yuanyuan CHEN Shunhuai

(Key Laboratory of High Performance Ship Technology, Ministry of Education, School of Transportation, Wuhan University of Technology, Wuhan 430063, China)

In order to solve the three-dimensional container loading plan problem (3D CLPP), the ant colony algorithm based on the Pareto solution set and ant colony algorithm based on weight distribution are put forward. Using the method of step by step, the three-dimensional container loading problem is decomposed into the bay optimization and a two-dimensional container loading plan problem (2D CLPP). In a strategy of controlling the number of shift to be zero, the ship longitudinal bending moment value, center of gravity in the lateral displacement and height of initial stability are set as the goal and the ship draft difference between fore and aft is set as the constraint. In this way, the container loading plan is optimized such that the efficiency of containership loading can be improved, the cost and time of loading could be saved and the container ship state could have a stable state for sailing.

multiple objective; ant colony algorithm; container; loading optimization

2017-01-24

U695.22

10.3963/j.issn.2095-3844.2017.03.024

汪圓圓(1992—)：男，碩士生，主要研究領(lǐng)域?yàn)橹悄艽?/p>