, ,

(武漢理工大學(xué) 物流工程學(xué)院， 武漢 430063)

集裝箱船舶裝箱排序問題優(yōu)化模型及算法

田維,張煜,程惠敏

(武漢理工大學(xué)物流工程學(xué)院，武漢430063)

針對(duì)現(xiàn)實(shí)約束下的船舶裝箱排序問題，利用整數(shù)規(guī)劃方法，以最小化橫傾力矩為目標(biāo)，構(gòu)建該問題的數(shù)學(xué)模型。開發(fā)3階段的啟發(fā)式算法，基于規(guī)則構(gòu)建預(yù)配載方案，進(jìn)行集裝箱互換，搜索優(yōu)化解。對(duì)小規(guī)模案例和不同規(guī)模實(shí)際案例進(jìn)行仿真試驗(yàn)，結(jié)果表明啟發(fā)式算法均能在0.1 s內(nèi)獲得船舶實(shí)配約束下裝箱排序問題的解。同時(shí)，通過與IBM ILOG CPLEX中分支定界算法的精確解求解情況進(jìn)行對(duì)比，驗(yàn)證模型及優(yōu)化算法的有效性和實(shí)用性。

裝箱排序； 整數(shù)規(guī)劃； 啟發(fā)式算法； 分支定界算法

Abstract: In order to solve the sequencing and bin packing problem with practical vessel stowage constraints, a mathematical model of the problem is constructed based on integer programming method, which aims to minimizing the heel moment. A three-phase heuristics algorithm is developed, which makes a tentative stowage plan according to given rules first, and then find the optimum solution by interchanging containers. Simulations of actual stowage cases show that the problems can be solved within 0.1 s regardless the scale of the problem. Effectiveness and practicality of the model and optimal algorithm are verified through comparison with the exact solutions obtained by the branch & bound algorithm from IBM ILOG CPLEX.

Keywords: sequencing and bin packing problem; integer programming; heuristics algorithm; branch & bound algorithm

集裝箱船配載是集裝箱水上運(yùn)輸中的重要環(huán)節(jié)，對(duì)保障船舶的安全航行、貨物的安全運(yùn)輸及運(yùn)營的效率和效益有著很大的影響。因此，以集裝箱裝船后船舶的穩(wěn)定性最優(yōu)為目標(biāo)研究港口集裝箱的裝船順序和裝載位置問題，避免后續(xù)在其他港口翻倒箱，實(shí)現(xiàn)有序裝載，有著十分重要的意義。集裝箱船舶裝箱排序問題(Sequencing and Bin Packing Problem，SBPP)指的是集裝箱堆場某個(gè)箱區(qū)貝內(nèi)的集裝箱按照一定的裝船順序發(fā)箱，并依次裝船至船舶貝內(nèi)具體箱位的問題。集裝箱裝船時(shí)，在考慮船舶穩(wěn)定性的基礎(chǔ)上，通過合理安排集裝箱的裝載順序達(dá)到滿足船舶貝內(nèi)的積載強(qiáng)度、重不壓輕、不存在阻塞箱、不懸空及不違背發(fā)箱順序規(guī)律等現(xiàn)實(shí)約束的要求。SBPP是典型的NP-hard組合優(yōu)化問題[1]，近年來已有一些學(xué)者對(duì)其進(jìn)行研究。張維英等[2]對(duì)單一目的港貝位排序建立模型，采用禁忌搜索算法求解；孫曉雅等[3]建立模型研究多港貝位排序問題，并采用粒子群算法求解，但僅考慮避免后續(xù)港口翻倒箱，未考慮積載強(qiáng)度、質(zhì)量及其他現(xiàn)實(shí)約束；王莉莉等[4]對(duì)裝船順序的優(yōu)化過程建立模型，并采用遺傳算法求解；孫俊清等[5]對(duì)多港口、多貝位的配載建立0-1規(guī)劃數(shù)學(xué)模型，考慮船舶穩(wěn)定性的約束，并用遺傳算法求解；張維英等[6]在貝位配載中考慮艙蓋分塊，采用隱士圖啟發(fā)式搜索技術(shù)求解混裝貝位的排箱優(yōu)化模型；李坤等[7]建立多貝位的整數(shù)規(guī)劃模型，將問題分為2個(gè)階段，并采用禁忌搜索算法求解；MONACO等[8]建立最小化裝船時(shí)間和翻箱的數(shù)學(xué)模型，但未對(duì)集裝箱在堆場的發(fā)箱順序及對(duì)配載的約束進(jìn)行研究；DUBROVSKY等[9]考慮船舶單貝配載計(jì)劃，以最小化翻箱次數(shù)為目標(biāo)，利用遺傳算法求解；DELGADO等[10]使用約束規(guī)劃(CP)和整數(shù)規(guī)劃(IP)建立模型并進(jìn)行精確求解；MOURA等[11]將配載問題與船舶路徑相結(jié)合建立數(shù)學(xué)模型，研究延伸到全航線的成本優(yōu)化。

以上研究主要從貝內(nèi)排箱問題的角度建立數(shù)學(xué)模型，采用禁忌搜索算法、粒子群算法、遺傳算法和分支定界算法等算法進(jìn)行求解，而未考慮堆場發(fā)箱順序?qū)Υ柏悆?nèi)排箱問題的影響。堆場貝內(nèi)堆存狀態(tài)較差及其裝船發(fā)箱順序不合理會(huì)導(dǎo)致船舶貝內(nèi)生成阻塞箱，從而增加后續(xù)港口卸貨時(shí)的翻倒箱數(shù)，不利于全航線的配載。對(duì)此，結(jié)合港口運(yùn)作的實(shí)際經(jīng)驗(yàn)和規(guī)則，建立符合實(shí)際的優(yōu)化模型，設(shè)計(jì)有效的啟發(fā)式算法，以滿足港口實(shí)際配載的需要。

1 集裝箱船舶裝箱排序問題的優(yōu)化模型

1.1 模型假設(shè)

考慮到堆場與船舶的實(shí)際運(yùn)作情況，針對(duì)配載問題給出以下假設(shè)：

1) 集裝箱堆場實(shí)際堆碼按照PSCW規(guī)則實(shí)施，即同一個(gè)目的港、同一尺寸、同一種類的集裝箱按照質(zhì)量級(jí)別堆放在堆場的同一貝位內(nèi)，一般重箱在上、輕箱在下。

2) 集裝箱堆場內(nèi)不同種類的集裝箱不混裝，危險(xiǎn)品箱、冷藏箱等特殊箱與標(biāo)準(zhǔn)箱不在同一貝內(nèi)擺放，這里僅考慮具有相同尺寸的標(biāo)準(zhǔn)集裝箱。

3) 為提高堆場的作業(yè)效率，避免起重機(jī)小車無序行走，堆場貝內(nèi)集裝箱通常遵循港口實(shí)際操作經(jīng)驗(yàn)逐列依次裝船發(fā)箱(見圖1)，可確定各個(gè)出口箱的發(fā)箱順序。

圖1 堆場發(fā)箱順序

4) 集裝箱堆場待裝船箱區(qū)貝內(nèi)的集裝箱總數(shù)和質(zhì)量小于船舶貝內(nèi)的箱位數(shù)及允許的最大承重，保證堆場貝內(nèi)所有待裝船集裝箱都能完成裝載。

5) 為保證安全，集裝箱船舶貝內(nèi)實(shí)際配載需考慮任意列的集裝箱積載強(qiáng)度要求，避免單列集裝箱質(zhì)量之和大于船舶局部載荷強(qiáng)度。

1.2 數(shù)學(xué)模型

2) 決策變量為xkp，表示集裝箱k是否裝到船舶上的p箱位，為0-1決策變量。

3) SBPP問題優(yōu)化模型為

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(1)中：z為最小化船舶貝的橫傾力矩，t·m；d(取2.438 m)為集裝箱的寬度；Δ(取0.3 m)為相鄰2個(gè)集裝箱之間的間隙。由于集裝箱船舶貝內(nèi)的集裝箱會(huì)對(duì)貝內(nèi)橫切面中心軸產(chǎn)生力矩，因此為避免船舶結(jié)構(gòu)出現(xiàn)損傷，需控制貝內(nèi)左右兩邊的力矩之差，即要求貝內(nèi)橫傾力矩越小越好。式(2)表示船舶貝內(nèi)任意箱位最多放一個(gè)集裝箱；式(3)表示一個(gè)集裝箱必須占用一個(gè)船舶貝內(nèi)箱位；式(4)表示船舶配載時(shí)集裝箱不懸空；式(5)表示船舶裝載時(shí)堆場先發(fā)箱不能置于后發(fā)箱的上面；式(6)表示船舶貝位單列的堆積約束；式(7)表示船舶配載中的質(zhì)量等級(jí)約束，即重不壓輕；式(8)表示船舶貝內(nèi)避免形成阻塞箱。

2 集裝箱船舶裝箱排序問題算法設(shè)計(jì)

集裝箱船舶裝箱排序問題是NP問題，在裝船量較小的情況下也是大規(guī)模的復(fù)雜優(yōu)化問題，且隨著問題規(guī)模的增大，求解時(shí)間成指數(shù)倍增長。由于大規(guī)?，F(xiàn)實(shí)問題無法在現(xiàn)實(shí)時(shí)間要求范圍內(nèi)給出最優(yōu)解，因此設(shè)計(jì)三階段啟發(fā)式算法對(duì)集裝箱船舶裝箱排序問題進(jìn)行求解。

1) 第1階段是預(yù)處理階段。按照堆場貝內(nèi)集裝箱裝船發(fā)箱規(guī)則確定各個(gè)集裝箱的發(fā)箱順序，按照發(fā)箱順序排列形成待裝船集裝箱集合N，依次進(jìn)行裝船。在船舶貝中，按照自中間向左右兩側(cè)遞增的方式對(duì)列進(jìn)行優(yōu)先級(jí)定義，自下而上對(duì)層進(jìn)行優(yōu)先級(jí)定義。對(duì)每列按照層的優(yōu)先級(jí)形成空箱位集合，并初始化每列的當(dāng)前載重TW。

2) 第2階段是預(yù)配載階段。對(duì)待裝船集裝箱集合N中的所有集裝箱進(jìn)行裝船操作。按照列、行的優(yōu)先級(jí)順序依次選取各集裝箱的目標(biāo)箱位，并對(duì)目標(biāo)箱與緊挨目標(biāo)箱位之下的箱位p′=(i,j-1)中所裝載的集裝箱k′進(jìn)行質(zhì)量等級(jí)、目的港的比較，以此檢驗(yàn)是否能滿足重不壓輕、翻倒箱的約束；對(duì)目標(biāo)箱的質(zhì)量與該列當(dāng)前所能承受的剩余負(fù)荷Si-Ti進(jìn)行比較，以此檢驗(yàn)是否能滿足積載強(qiáng)度的約束。依次將集裝箱裝船，完成所有集裝箱的裝載，得到預(yù)配載方案。

3) 第3階段是橫傾優(yōu)化階段，包括列交換和箱位交換2部分。

(1) 對(duì)第2階段得到的預(yù)配載方案進(jìn)行列交換操作。在相同大小的列集合中互換所有列，并計(jì)算相應(yīng)的橫傾力矩。

(2) 選擇最小橫傾力矩的列交換方案進(jìn)行箱位交換操作。列出所有集裝箱的箱位互換組合，并進(jìn)行裝箱順序、質(zhì)量等級(jí)、阻塞箱形成及列積載約束的判斷，若滿足約束，則進(jìn)行箱位互換操作，并計(jì)算對(duì)應(yīng)的橫傾力矩。

(3) 根據(jù)計(jì)算結(jié)果得出橫傾力矩值最小的箱位交換方案，輸出該方案及最小的橫傾力矩值，即為最終的配載方案。

基于上述3個(gè)階段，啟發(fā)式算法的流程見圖2。

圖2 三階段啟發(fā)式算法

3 仿真分析

利用MATLAB對(duì)所提出的啟發(fā)式算法進(jìn)行驗(yàn)證，所有結(jié)果均在Intel Core 42.4 GHz CPU及8G內(nèi)存平臺(tái)下測(cè)得。

3.1 小規(guī)模案例

集裝箱堆場某個(gè)箱區(qū)貝內(nèi)有24個(gè)集裝箱，擺放成6列，掛靠3個(gè)目的港，其質(zhì)量由Excel隨機(jī)生成。這些集裝箱待裝載入某船舶貝，該船舶貝有7列6層，每一列允許的最大積載強(qiáng)度(單位為t)見圖3，其中：堆場貝中方框表示集裝箱；中間的數(shù)字表示提箱順序；左下角的數(shù)字表示集裝箱的質(zhì)量；右上角的數(shù)字表示集裝箱的目的港。

采用設(shè)計(jì)的啟發(fā)式算法對(duì)案例進(jìn)行求解，得出的最小橫傾力矩為2.738 t·m。使用CPLEX軟件對(duì)上述案例進(jìn)行精確解求解，得出的最小橫傾力矩為0，得出的配載方案見圖4。從圖4中可看出，利用啟發(fā)式算法得到的解與利用CPLEX軟件得到的精確解較為接近。

圖3 小規(guī)模案例

a) 啟發(fā)式算法

b) CPLEX

船舶貝的最大允許橫傾力矩計(jì)算式為

(9)

式(9)中：δ為力矩敏感系數(shù)。由該計(jì)算式可計(jì)算出該貝的最大允許橫傾力矩MH(δ取5 t，相當(dāng)于1個(gè)輕箱所導(dǎo)致的M偏差)為41.07 t·m。利用啟發(fā)式算法得到的解也遠(yuǎn)低于MH，且該算法得到的配載方案在船舶貝的列上同一目的港的集裝箱較為集中，這樣有利于后續(xù)港口進(jìn)行集裝箱卸載操作。

3.2 實(shí)際案例

為進(jìn)一步驗(yàn)證算法的有效性，結(jié)合某港某集裝箱船舶的實(shí)際案例進(jìn)行仿真分析。該港口待裝載到該船舶有6個(gè)目的港，這里選取其中4個(gè)不同結(jié)構(gòu)的貝進(jìn)行案例求解(見圖5)。

a)貝09b)貝17

c)貝45d)貝47

圖5 船舶貝

將堆場中的36個(gè)集裝箱(6列6層堆放)、48個(gè)集裝箱(8列6層堆放)、66個(gè)集裝箱(11列6層堆放)和72個(gè)集裝箱(12列6層堆放)分別裝載到貝09(最大允許承重為640 t)、貝17(最大允許承重為780 t)、貝45(最大允許承重為1 000 t)及貝47(最大允許承重為1 060 t)中。在每個(gè)場景下進(jìn)行5個(gè)隨機(jī)案例的仿真試驗(yàn)，使用設(shè)計(jì)的啟發(fā)式算法及CPLEX中的分支定界算法求解,結(jié)果見表1，其中*表示案例在2 h內(nèi)無計(jì)算結(jié)果。

由表1可知，設(shè)計(jì)的啟發(fā)式算法在不同規(guī)模的不同案例下均能得到與精確解較為接近的解，個(gè)別情況下與精確解相同，解的質(zhì)量較高。對(duì)于規(guī)模較大的現(xiàn)實(shí)問題，CPLEX大部分案例在有效時(shí)間內(nèi)不能得到解，少數(shù)案例雖能得出精確解，但求解時(shí)間較長；而啟發(fā)式算法運(yùn)算速度極快，能在0.1 s內(nèi)求解，遠(yuǎn)遠(yuǎn)超過實(shí)際應(yīng)用的需求，具有良好的實(shí)用性。

3.3 算法性能分析

為評(píng)估三階段啟發(fā)式算法的性能，結(jié)合問題的上、下界理論定義算法性能的間隙公式，即

(10)

數(shù)據(jù)分析結(jié)果見表2，利用啟發(fā)式算法在不同場景下得到的間隙值G最大為5.82%，最小為2.91%，這表明利用三階段啟發(fā)式算法所得解的質(zhì)量較高，能滿足實(shí)際裝船時(shí)對(duì)橫傾安全性的要求，可在有效時(shí)間內(nèi)解決現(xiàn)實(shí)情況下的集裝箱船舶裝箱排序問題。

表1 案例的數(shù)據(jù)處理結(jié)果

表2 數(shù)據(jù)分析結(jié)果

4 結(jié)束語

針對(duì)堆場某個(gè)箱區(qū)貝內(nèi)的集裝箱裝載到船舶某個(gè)貝位確定位置的裝箱排序問題，提出解決方案，并基于橫傾力矩最小化的目標(biāo)與現(xiàn)實(shí)約束構(gòu)建該問題的混合整數(shù)規(guī)劃模型。該模型可保證船舶在安全性最優(yōu)的情況下完成配載，且可避免形成阻塞箱。此外，進(jìn)一步開發(fā)了三階段的啟發(fā)式算法，通過現(xiàn)實(shí)案例驗(yàn)證了模型及算法的有效性和實(shí)用性。

[1] 黎明,翟金剛.集裝箱裝船順序的多目標(biāo)整數(shù)規(guī)劃優(yōu)化模型[J].計(jì)算機(jī)應(yīng)用研究,2012,29(10):3635-3639.

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

[3] 孫曉雅,林焰.集裝箱船多港Bay位排箱的優(yōu)化方法[J].大連海事大學(xué)學(xué)報(bào),2011,37(1): 75-79.

[4] 王莉莉,于紅.集裝箱裝船順序優(yōu)化模型及遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(5):234-238.

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

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

[7] 李坤,唐立新.集裝箱碼頭裝船計(jì)劃問題建模與優(yōu)化研究[J].控制工程,2015,22(4): 683-689.

[8] MONACO M F, SAMMARRA M, SORRENTINO G. The Terminal-Oriented Ship Stowage Planning Problem[J].European Journal of Operational Research,2014,239(1): 256-265.

[9] 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(6):585-599.

[10] DELGADO A, JENSEN R M. A Constraint Programming Model for Fast Optimal Stowage of Container Vessel Bays[J]. European Journal of Operational Research, 2012, 220,(1):251-261.

[11] MOURA A, OLIVEIRA J, PIMENTEL C. A Mathematical Model for the Container Stowage and Ship Routing Problem[J].Math Model Algor, 2013,12(3):217-231.

Optimal Model and Algorithm of Sequencing and Bin Packing Problem for Container Carrier

TIANWei,ZHANGYu,CHENGHuimin

(School of Logistics Engineering,Wuhan University of Technology,Wuhan 430063, China)

1000-4653(2016)04-0118-05

U695.2+2

A

2016-07-25

國家自然科學(xué)基金(71372202)

田 維(1990—)，女，湖北荊州人，碩士生，從事物流系統(tǒng)建模與優(yōu)化研究。E-mail: twaisy@126.com

張 煜(1974—)，男，天津人，教授，博士，從事智能決策、物流系統(tǒng)建模與仿真研究。E-mail: sanli@whut.edu.cn