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

, ,

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

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

田維,張煜,程惠敏

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

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

裝箱排序； 整數(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

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

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

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

1.1 模型假設(shè)

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

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

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

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

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

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

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

1.2 數(shù)學模型

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

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

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

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

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

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

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

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

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

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

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

3 仿真分析

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

3.1 小規(guī)模案例

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

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

圖3 小規(guī)模案例

a) 啟發(fā)式算法

b) CPLEX

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

(9)

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

3.2 實際案例

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

a)貝09b)貝17

c)貝45d)貝47

圖5 船舶貝

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

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

3.3 算法性能分析

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

(10)

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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

[7] 李坤,唐立新.集裝箱碼頭裝船計劃問題建模與優(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

國家自然科學基金(71372202)

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

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