集裝箱船全航線智能預(yù)配問題研究*

汪圓圓 陳順懷

(高性能船舶技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 武漢 430063)

集裝箱船全航線智能預(yù)配問題研究*

汪圓圓 陳順懷

(高性能船舶技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室 武漢 430063)

針對掛靠多港口集裝箱船的全航線預(yù)配問題，以倒箱量最少、船舶縱向強(qiáng)度最優(yōu)為目標(biāo)，提出該問題的0-1整數(shù)規(guī)劃模型.利用基于規(guī)則的方法，并分別采用混合整數(shù)規(guī)劃算法、蟻群算法和遺傳算法求解之.結(jié)果表明，在待配載箱數(shù)較少時(shí)，混合整數(shù)規(guī)劃算法快速，且得到的解為最優(yōu)解.給出了基于以上三種算法及一定的裝箱規(guī)則的全航線智能配載算法.采用該算法模擬計(jì)算得出了8 Bay集裝箱船全航線智能預(yù)配結(jié)果，保證了倒箱量為0，且考慮到了縱向強(qiáng)度目標(biāo)，即集裝箱重心距離船舯的距離最小.

集裝箱船；預(yù)配；整數(shù)規(guī)劃；遺傳算法；蟻群算法

0 引 言

集裝箱預(yù)配問題是一類較為復(fù)雜的組合優(yōu)化問題，其求解的復(fù)雜度隨集裝箱所占Bay位數(shù)的增加而呈爆炸式增長，預(yù)配需考慮如何通過合理配載使船舶具有較合理的浮態(tài)并且使船舶重量合理分布，以保障船舶的快速性和結(jié)構(gòu)強(qiáng)度的安全.多年以來，國內(nèi)外學(xué)者對此問題進(jìn)行了一系列的研究.

張維英等[1-3]提出首先將集裝箱按貨物種類、尺寸和目的港組成同類箱組，以同類箱組為處理單元，以倒箱數(shù)量最少、船舶載箱率最高及不同目的港集裝箱占用Bay位數(shù)量最少為目標(biāo)，以滿足船舶縱向強(qiáng)度和吃水差要求為約束條件，采用超尺寸裝箱完成集裝箱在船上的縱向布置，并產(chǎn)生配載的總布置圖.而后在預(yù)配的基礎(chǔ)上，針對單一目的港集裝箱和混合目的港集裝箱Bay位，分別以初穩(wěn)性高度最優(yōu)及橫傾力矩最小、倒箱量最少為目標(biāo)，采用基于指派問題的禁忌搜索算法和隱式圖啟發(fā)式搜索算法進(jìn)行求解.而其給出的全航線配載算例中，沒有賦予每個(gè)集裝箱重量，實(shí)際上得到的全航線配載結(jié)果是無意義的.

Ambrosino等[4]提出一種針對集裝箱配載問題的分解啟發(fā)式算法，將集裝箱配載問題分為三個(gè)子問題，預(yù)配問題則相當(dāng)于這三個(gè)問題中的第一個(gè)問題.其采用系統(tǒng)的配載優(yōu)化策略，運(yùn)用啟發(fā)式搜索策略，在理論上解決了大型集裝箱船的配載問題.Avriel等[5]將集裝箱配載問題轉(zhuǎn)換為圖著色問題，并且證明了當(dāng)Bay位列數(shù)大于4時(shí)，無能力約束倒箱問題為NP完全問題.但并未給出具體求解策略及相關(guān)算例.Araújo等[6]將Pareto前沿與聚類搜索算法相結(jié)合，提出一種Pareto聚類搜索算法(pareto clustering search,PCS)，以倒箱量最少和船舶穩(wěn)定性最優(yōu)為目標(biāo)，得到了在船舶掛靠不同數(shù)目的港口時(shí)，采用該算法得到的前沿要優(yōu)于其他兩種算法.Pacino等[7]提出一種能夠快速產(chǎn)生近優(yōu)配載計(jì)劃的二步分解算法，采用混合整數(shù)規(guī)劃模型，松弛整數(shù)約束，使整個(gè)解產(chǎn)生的時(shí)間小于330 s，且解的效果良好.孫俊清等[8]討論了停泊多港口的集裝箱運(yùn)輸班輪全航線配載問題，以船舶穩(wěn)性為約束，倒箱量為目標(biāo)，建立了0-1整數(shù)規(guī)劃模型，并采用改進(jìn)的遺傳算法求解之.其優(yōu)勢在于其算法的設(shè)計(jì)，而其劣勢在于對集裝箱全航線配載問題模型的建立過于簡單，沒有考慮到重量的合理分布，這顯然是不合理的.

本文將針對文獻(xiàn)[3]中的算例進(jìn)行修改和一定的拓展，以倒箱量最少、船舶縱向強(qiáng)度最優(yōu)為目標(biāo)(模擬算例未考慮吃水差)，提出該問題的0-1整數(shù)規(guī)劃模型，并分別采用混合整數(shù)規(guī)劃算法、蟻群算法和遺傳算法求解之.結(jié)果表明，在待配載箱數(shù)較少時(shí)，混合整數(shù)規(guī)劃算法快速，且得到的解為最優(yōu)解.給出了基于以上三種算法及一定裝箱規(guī)則的全航線智能預(yù)配算法，最后采用該算法模擬計(jì)算得出了8Bay集裝箱船全航線智能預(yù)配結(jié)果.

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

1.1 問題描述

預(yù)配即按船上Bay為裝載單元，將集裝箱按類別(如尺寸、目的港、不同種類箱等)組成同類箱組，以同類箱組為裝載單元，采用合適的裝箱算法確定同類箱組在船上縱向布置，完成配載的總布置圖，見圖1.

圖1 箱位排布俯視圖

在圖1中，以L1，L2，…，Lm為箱位的縱向排布順序，按自船首至船尾增序排列.其所包含的箱位數(shù)量分別為r1，r2，…，rm，距船舯的位置為x1，x2，…，xm，圖中顯示了TEU和FEU箱位的排布示意.

以t表示裝箱矩陣，即

(1)

式中：tij為裝載港為i，卸載港為j的集裝箱數(shù)量，j>i，否則tij=0，并且裝箱矩陣元素符合下述關(guān)系為

(2)

式中：tn為第n港的裝箱量.

則問題可以描述為：將tn個(gè)集裝箱配載入圖1的m個(gè)Bay位中，其中這tn個(gè)集裝箱可以分為若干個(gè)同類箱組，如何配載可使得所產(chǎn)生的倒箱量，即先卸載集裝箱被后卸載集裝箱壓在下面的次數(shù)最少、船舶的縱向強(qiáng)度最優(yōu).

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

假設(shè)與裝箱矩陣對應(yīng)的重量矩陣為

(3)

式中：wij為裝載港為i，卸載港為j的集裝箱重量.設(shè)待配載同類箱組分別為1，2，…，n，集裝箱船Bay位號從首至尾分別為1，2，…，m，則集裝箱船預(yù)配問題即如何將這n個(gè)同類箱組配載至這m個(gè)Bay位中，使得倒箱量最少、結(jié)構(gòu)強(qiáng)度最優(yōu).

在集裝箱全航線配載過程中，將配載變量定義為cij，表示將第i個(gè)箱組裝載于第j個(gè)Bay位，見表1.

表1 配載變量定義

在配載過程中，對于混裝Bay位，將按照先卸載港后裝，后卸載港先裝的規(guī)則，從而保證不產(chǎn)生倒箱量.由此，給出如下集裝箱全航線配載0-1整數(shù)規(guī)劃模型為

(4)

(5)

(6)

(7)

wi≤[w] (i=1，2，…，m)

(8)

n≤m

(9)

ti≤ri(i=1，2，…，m)

(10)

upID≤downID

(?BayID∈MixedBay)

(11)

ShiftNums≤[Nums]

(?BayID∈MixedBay)

(12)

式(4)表示所有集裝箱組對船舯的力矩越小越好，集裝箱船的總縱強(qiáng)度以左右集裝箱組對于船舯的力矩來表示，因此，該值越小，表示總縱強(qiáng)度越好.式(5)～(7)表示配載變量約束，即配載變量只能取0或者1之間的一個(gè)，且表1的任意一行、任意一列相加都要為1，即每一個(gè)箱組只能占用一個(gè)Bay位，每一個(gè)Bay位只能被一個(gè)箱組所占據(jù).式(8)表示每一個(gè)Bay位所裝載的集裝箱重量不得超過該Bay所允許裝載的集裝箱最大重量.式(9)表示箱組個(gè)數(shù)不得超過集裝箱船的Bay位總數(shù).式(10)表示任意箱組中的集裝箱數(shù)目不得超過其所占據(jù)的Bay位中的集裝箱箱位數(shù)量.式(11)表示對于混合Bay，卸載港編號小的集裝箱不得處于卸載港編號大的集裝箱之下，即保證先卸載港的集裝箱后裝，后卸載港的集裝箱先裝.式(12)表示在整個(gè)裝配過程產(chǎn)生的倒箱量不超過[Nums]，本文模擬算例將之取為0.

2 全航線智能預(yù)配算法

目前，針對全航線配載問題的算法多基于經(jīng)典裝箱算法[9]，以Bay位利用率、倒箱量為目標(biāo)進(jìn)行配載，而后校核強(qiáng)度、吃水差等約束條件.本文則以強(qiáng)度、倒箱量為目標(biāo)，并遵循若干裝卸規(guī)則，對掛靠多港口的集裝箱船全航線配載問題提出一種全航線智能預(yù)配算法.

Azevedo等[10]針對集裝箱船配載問題，提出6種裝載規(guī)則和2種卸載規(guī)則.Benedito等[11]提出在混合Bay裝載過程中，先卸載港后裝載，后卸載港先裝載的規(guī)則.利用以上這些規(guī)則，可以減小集裝箱全航線配載問題的求解難度.

全航線智能預(yù)配算法的基本步驟如下.

步驟1 將集裝箱船Bay位按自船艏至船艉進(jìn)行編號，記作：BayID=1，2，…，m，其所包含的箱位數(shù)量分別為r1，r2，…，rm，距船舯的位置分別為x1，x2，…，xm.

步驟3 按上節(jié)所述0-1整數(shù)規(guī)劃模型，采用混合整數(shù)規(guī)劃算法或兩種智能算法(遺傳算法、蟻群算法)求解之，得到第1港裝載結(jié)果.

在蟻群算法求解過程中，將距離函數(shù)定義為

(13)

其他諸如概率函數(shù)、信息素更新規(guī)則等的定義與基本蟻群算法一致，且采用蟻周模型進(jìn)行更新[12].

步驟4 船舶航行至第2港，先清空卸載港編號為本港的集裝箱，于其他港卸載的集裝箱保持不變，卸載完成后，更新船舶Bay位屬性，在第2港，箱子的拆分、重量的分配要視當(dāng)前集裝箱對于船舯的力矩而定，規(guī)定船舯往船艏為正方向，則如果當(dāng)前力矩為正值，且 需要補(bǔ)充箱子的Bay位位置為負(fù)，則取同一卸載港重箱進(jìn)行補(bǔ)充；反之，取同一卸載港輕箱補(bǔ)充.若補(bǔ)充后，剩余箱子數(shù)目小于被補(bǔ)充Bay位原有箱子數(shù)目，則不進(jìn)行補(bǔ)充.補(bǔ)充完成后，按卸載港編號從大到小進(jìn)行配載，對于數(shù)量不超過Bay位容量的，作為一個(gè)箱組進(jìn)行配載，對于數(shù)量超過Bay位容量的，要對其進(jìn)行拆分，拆分時(shí)，要不選擇最輕箱進(jìn)行拆分，要不選擇最重箱進(jìn)行拆分，視當(dāng)前力矩值的正負(fù)及Bay位位置而定.當(dāng)有多種Bay位可選時(shí)，調(diào)用混合整數(shù)規(guī)劃算法或者智能算法求解之.如此往復(fù)，直到所有箱子都配載完畢，便得到第2港配載方案.

步驟5 對除目的港以外的其他港進(jìn)行相同操作，并在目的港清空Bay位中的所有集裝箱，得到整個(gè)全航線預(yù)配方案.

3 結(jié)果與分析

假設(shè)某集裝箱船在某一航線上將要掛靠6個(gè)港口，該船上共有8個(gè)Bay位，均裝TEU，相鄰兩Bay位之間的間距都為100 mm，每一Bay位的最大容量都為46箱.另一艘集裝箱船同樣在這一航線上掛靠6個(gè)港口，該船上共有40個(gè)Bay位，亦均裝20英尺的標(biāo)準(zhǔn)箱，相鄰兩Bay位之間的間距都為100 mm，每一Bay位的最大容量都為200箱，箱子的重量有3種規(guī)格，即7，12和18 t.8 Bay集裝箱船的裝箱矩陣及與之對應(yīng)的重量矩陣分別為

表2為三種算法對8 Bay集裝箱船在第1港口裝載后的求解結(jié)果比較.其中蟻群算法和遺傳算法都計(jì)算100代.遺傳算法中，交叉概率取0.75，變異率取0.25，種群數(shù)量取200，精英個(gè)體數(shù)取30.蟻群算法中，螞蟻數(shù)量取5，信息素啟發(fā)因子α取2，期望啟發(fā)式因子β取3，信息素?fù)]發(fā)系數(shù)ρ取0.3，信息素常量Q取1 000.并在同一臺(tái)計(jì)算機(jī)上進(jìn)行計(jì)算.

表2 不同算法的計(jì)算結(jié)果

模擬集裝箱Bay位總長為49.164 m，在各港裝載后的重心縱向偏移量見表3.按照第2部分的全航線智能預(yù)配算法，可得采用混合整數(shù)規(guī)劃求解8Bay集裝箱船的結(jié)果，見表4.

表3 重心縱向偏移量

表4 全航線預(yù)配結(jié)果

注：a(i,j,w)表示裝載港為i，卸載港為j的集裝箱數(shù)量為a，重量為w；a1(i,j,w1)+a2(k,q,w2)+…，表示混裝Bay位，且按裝載順序相加.

4 結(jié) 束 語

本文針對掛靠多港口集裝箱船的全航線預(yù)配問題，采用了基于規(guī)則的方式，以倒箱量最少、船舶縱向強(qiáng)度最優(yōu)為目標(biāo)，并結(jié)合三種算法即混合整數(shù)規(guī)劃算法、蟻群算法和遺傳算法，提出了針對該問題的智能預(yù)配算法.采用該算法，可以得到船舶在首港預(yù)配的最優(yōu)解及后續(xù)港預(yù)配的近似最優(yōu)解.模擬實(shí)驗(yàn)結(jié)果表明所提出的算法可行，為集裝箱船舶的全航線多目標(biāo)預(yù)配問題提供了一個(gè)可用的模型，為Bay位排箱(進(jìn)一步優(yōu)化穩(wěn)性與橫傾)奠定基礎(chǔ).并可為其他船舶的智能配載問題作參考。

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

[2]張維英,林焰,紀(jì)卓尚,等.集裝箱船全航線Bay位排箱優(yōu)化模型[J].上海交通大學(xué)學(xué)報(bào),2007,41(2):199-204.

[3]張維英,林焰,紀(jì)卓尚,等.集裝箱船全航線預(yù)配優(yōu)化模型與算法研究[J].大連理工大學(xué)學(xué)報(bào),2008,48(5):673-678.

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

[5]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.

[7]PACINO D, DELGADO A, JENSEN R M, et al. Fast generation of near-optimal plans for eco-efficient stowage of large container vessels[C]∥ International Conference，2011(2):286-301.

[8]孫俊清,陳忱,劉鳳連.考慮船舶穩(wěn)定性的多港口集裝箱配載問題[J].計(jì)算機(jī)工程與應(yīng)用,2012,48(32):236-243.

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

[10]AZEVEDO A T D, ARRUDA E F D, NETO L L D S, et al. Solution of the 3D stochastic stowage planning for container ships through representation by rules[C]∥ International Workshop on Knowledge Discovery, Knowledge Management and Decision Support，2013:120-129.

[11]BENEDITO M P L, SANTOS A G D. Evolutionary algorithm and ant colony optimization for a container stowage problem[J]. Discrete Applied Mathematics,2015(1):55-58.

[12]汪定偉.智能優(yōu)化方法[M].北京：高等教育出版社,2007.

A Research on Intelligent Pre-stowage Planning Problem for Containerships in Full Routes

WANG Yuanyuan CHEN Shunhuai

(KeyLaboratoryofHighPerformanceShipTechnology,MinistryofEducation,Wuhan430063,China)

In order to solve the pre-planning problem for containerships in full routes using an intelligent way, a 0-1 integer programming for the problem is put forward by setting the number of shift and ship longitudinal bending moment value as goals. By the rule based methods, the problem is solved by the Mixed Integer Programming Algorithm (MIPA), Ant Colony Algorithm (ACA) and Genetic Algorithm (GA), respectively. It shows that when the scale of the problem is small, the MIPA is very efficient, and the optimal solution can be found by it. An intelligent algorithm for pre-planning problem of containerships in full routes based on the MIPA, ACA and GA is given, respectively. Finally, the pre-planning result of a containership with 8 bays is shown, it assures that the number of shift is zero, and the ship longitudinal bending moment value is considered as the objective, which means the longitudinal offsets of the center of gravity is minimized.

containerships; pre-stowage; integer programming; Genetic Algorithm; Ant Colony Algorithm

2017-06-15

U695.22

10.3963/j.issn.2095-3844.2017.04.034

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