船舶實配現實約束下的裝箱排序問題研究*

田　維　張　煜　程惠敏

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

船舶實配現實約束下的裝箱排序問題研究*

田維張煜程惠敏

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

摘要：針對現實約束下的船舶裝箱排序問題，利用整數規劃方法，以最小化裝船時間以及翻倒箱時間成本為目標，構建了該問題的數學模型.利用ILOG CPLEX和分支定界算法，對不同規模案例，按照三種裝船發箱規則進行求解，能夠獲得船舶實配約束下裝箱排序問題的精確解，并且發現不同的發箱規則對問題求解的速度和解的質量，有明顯的規律特征.算例結果表明，模型構建正確，能夠快速求解中小型規模案例.

關鍵詞：船舶配載；裝箱排序；整數規劃；分支定界

0引言

目前，集裝箱運輸方式已經成為海上交通貨流運輸的主要作業方式，在工作效率和經濟效率的雙重要求下，集裝箱的合理裝船過程就成為了提高工作效率和經濟效率的主要手段之一.堆場集裝箱裝船至集裝箱船舶的裝箱排序問題是典型的NP-hard組合優化問題[1]，受到堆場集裝箱的擺放、作業機械、集卡運輸、船舶結構等因素的影響.因此，研究港口集裝箱的裝載順序與裝載位置問題，實現有序裝載，從而使得裝船后船舶的穩定性較高，并減少后續港口的翻箱率，對集裝箱船舶運輸作業過程有著十分重要的意義.

近年來，已有一些學者對集裝箱的裝箱排序進行了研究，如王莉莉等[2]對裝船順序的優化過程建立了模型，但模型只考慮了翻箱情況，沒有考慮集裝箱裝船時間的優化；張維英等[3]研究了預配優化模型，但研究的重點是在貝(bay)位選擇上，對貝位中集裝箱排序沒有進行具體研究；李坤等[4]構建了多貝位的整數規劃模型，采用禁忌搜索算法求解；祝慧靈等[5]將問題擴展到全航線，船舶貝結構被劃分成多個箱位塊，不涉及具體貝內箱位的安排，采用遺傳算法求解；Maria等[6]建立了最小化裝船時間和翻箱的數學模型，但對于集裝箱在堆場如何發箱，以及對配載的影響沒有進行研究；Ana等[7]結合路徑優化建立了多船多港口配載和船舶路徑問題的模型，研究主要針對的是全航線的成本的優化，對裝箱排序問題研究得不夠深入.

文中主要以船舶實配的過程為研究對象，將船舶的貝作為集裝箱裝載容器，并考慮集裝箱后續港口裝卸順序、強度、橫傾和堆場集港箱堆碼一定等現實約束，探討集裝箱的裝載順序和裝載位置，并實現最短裝卸時間和最少翻箱量的目標.

1集裝箱船裝箱排序問題的描述

裝箱排序，指的是集裝箱按照一定的順序、服從一定的規則有序裝載到集裝箱船內指定位置的搬運過程.集裝箱的裝箱排序問題，分為2個問題：裝箱和排序.

裝箱是集裝箱與箱位的一一對應過程，這種對應性需要考慮很多因素.在船舶裝箱過程中，不同重量的集裝箱必須對應合適的箱位，以確保船舶的穩定和平衡.而且所有的集裝箱在裝船后，必須在重量分布上呈現出一種較為均勻的狀態，以維持船舶的橫傾平衡.在裝船過程中，裝船時間是影響船舶在港口停靠時間的重要因素，對運輸效率的提升至關重要.因此，本文將集裝箱的裝船時間最為優化目標，盡可能地減少集裝箱的裝船時間.

排序是集裝箱由陸側起重機裝船并按照指定順序進入集裝箱船艙內的過程，一般而言集裝箱的裝船順序也就是堆場集裝箱的提箱順序.集裝箱的提箱順序往往會對集裝箱的裝箱有較大的影響，在不同的順序規則下，集裝箱的裝船時間、裝載后的位置、船舶的穩定性及后續港的翻箱情況都可能出現較大差異.而翻箱的出現會極大的降低裝卸效率，因而本文也將翻箱量作為另一個優化目標.因此，合理安排堆場集裝箱的提箱順序，可以提高集裝箱裝箱排序過程的工作效率，同時降低運輸成本、作業成本，最終提高船、貨、港三方的集體經濟效益.

在實際中，碼頭堆場和船舶中的集裝箱均是按照貝、列和層的三維空間擺放.一般情況下，集裝箱的重量、尺寸、航線、目的港等信息不可隨意更改.本文研究的堆場集裝箱集合雖然是運往多個目的港的，但都是屬于同一條船.在集裝箱的裝船過程中，應將重量大、航程遠的集裝箱放在船舶的下面，以避免船舶在后續港口的翻倒箱操作，從而減少運作成本.在整個裝船過程中，始終要保持船舶的穩性，同時要盡可能地減少集裝箱的裝船時間.

2集裝箱裝船配載模型

2.1模型假設

考慮堆場與船舶的實際情況，本文給出配載問題以下假設：(1)不考慮危險品箱和冷藏箱等特殊箱，只考慮具有相同尺寸的標準集裝箱；(2)堆場出口箱已經按類別和目的港進行了分類，同目的港的集裝箱已經按照輕、中、重3種類型進行了從下到上的堆碼，即堆場集裝箱裝船時，在堆場內不存在倒箱；(3)堆場集裝箱集合裝載到船舶的一個貝位內，則船舶待裝貝位的容量不小于堆場待裝箱集合的勢，見圖1.

圖1　集裝箱裝載

2.2基本參數

N為堆場待裝載到船舶某貝的集裝箱集合；I為貝內列的集合；J為貝內層的集合；D為堆場集裝箱目的港的集合；k為堆場待裝載到船舶貝內的集裝箱編號，對應其裝船順序，k∈N={1,2,…,n}；Ji為船舶該貝第i列所有箱位的集合；p=(i,j)為船舶該貝第i列第j層的箱位，i∈I={1,2,…,‖I‖}；j∈Ji={1,2,…,‖Ji‖};L(p)為船舶該貝左側的箱位的集合；R(p)為船舶該貝右側的箱位的集合；tp為集裝箱裝到船舶上p箱位的裝船時間，由于陸側起重機初始位置在船舶最左邊的上方，每一層從左向右裝船時間逐一遞增，按列從上向下裝船時間逐一遞增，則tp=i+‖J‖-j；π(p)為船舶箱位p上面緊挨它的箱位，即π(p)=(i,j+1)；ωk為集裝箱k的重量；θk為集裝箱k的重量等級，其值取0，1，2，分別表示輕箱、中箱、重箱，而它們的重量取值范圍分別為:輕箱(0,10]t；中箱(10,20]t；重箱(20,30]t；dk為集裝箱k的目的港，dk∈D={1,2,…,m}；STi為船舶該貝第i列最大允許的積載強度，一般取80t；HM為船舶貝的最大允許橫傾力矩；HM=(‖I‖-1)(d+Δ)δ/2，其中：d為集裝箱的寬度，取d=2.438m；Δ為相鄰2個集裝箱之間的間隙，取Δ=0.3m；δ為力矩敏感系數，可取5，10，15，…，HM的單位為：kN·m.

決策變量為：xkp為集裝箱k是否裝到船舶上p箱位，為0-1決策變量；ξkp為箱位π(p)的集裝箱是否為p箱位集裝箱的阻塞箱，為0-1決策變量.

2.3模型

優化目標是使裝船時間最小，同時保證在后續港卸船時的翻倒箱數最少.

裝船時間是將集裝箱從堆場裝載到船上的過程中消耗的時間，在堆場消耗的時間(包括堆場提箱時間和吊車行走時間)幾乎是固定不能再進行優化的，故本文考慮的裝船時間為將集裝箱裝載到船上的時間.

翻箱時間是船舶貝內相鄰集裝箱存在阻塞所導致的后續港口卸船所產生的額外操作時間.在后續港卸船時，當且僅當對某個集裝箱卸載，才對位于其上方的集裝箱進行翻箱操作，翻箱是將阻塞箱放到岸上，待目標箱卸載后，再裝回到船上的同一位置，過程見圖2.為了便于計算，這2步操作的時間用該集裝箱2倍的裝/卸時間來表示，將這個操作時間作為懲罰，加上裝船時間進行優化.

圖2　翻箱操作過程

綜上，目標函數：

式中：第1項為堆場集裝箱的裝船時間，第2項為翻倒箱時間.

約束條件:

1) 同一個箱位最多放一個集裝箱，即

(1)

2) 一個集裝箱必須占用一個箱位，即

(2)

3) 船舶配載時集裝箱不懸空，即

(3)

4) 船舶裝載時，堆場先發箱不能置于后發箱的上面，即

(4)

5) 船舶貝位單列的堆積約束，即

(5)

6) 船舶該貝的橫傾力矩約束，即

(6)

7) 船舶配載重量等級重不壓輕，即

(7)

8) 決策變量ξkp計算

(8)

以上，式(1)～(4)是集裝箱裝船的規則約束，式(5)～(7)是船舶航行的安全性能約束，式(8)是用來限制變量ξkp的值.

3案例分析

3.1案例描述

對于堆場集裝箱的提箱順序有3種策略，在這樣的情況下，堆場不存在翻箱操作：(1)按照層，由高到低順序提箱(記為R1)；(2)按照列，由左到右順序發箱(記為R2)；(3)根據目的港，按照層由高到低順序發箱(記為R3).

假設船舶貝結構有小、中、大3種，見圖3，分別記為B1,B2,B3.每種貝結構的每一列的最大承重量如圖所示.

圖3　貝位圖(單位：t)

假設堆場某貝的集裝箱個數有12(2個目的港，4列堆放)、28(3個目的港，6列堆放)、40(3個目的港，6列堆放)3種.對每種集裝箱個數的集合由Excel隨機生成不同重量的案例.以下用B(貝)、N(集裝箱數目)、D(目的港數)、R(提箱策略)組合表示案例，如B1-N12-D2-R1-1表示12個集裝箱(有2個目的港)的第一個隨機案例在第一種提箱策略下裝載到船舶B1結構的情況.

3.2案例結果及分析

3.2.1初始案例求解

由于案例具有隨機性，故本文針對每個場景下的5個隨機案例，均采取了多次仿真求取平均值的處理方式，每一個案例均經過了5次仿真過程，以保證結果的精確性和有效性.

將堆場12個集裝箱、28個集裝、40個集裝箱分別按3種提箱策略，使用CPLEX中的分支定界算法求解.所得到的數據經過處理和分析整理后見表1.

表1　案例的數據處理結果

由于模型對翻箱進行了懲罰，故模型求解的最優解幾乎沒有翻箱數，即船舶在初始港裝船后，后續港卸船時基本不需要翻箱，這就減少了船舶的裝卸時間.由表1可知，與R2，R3策略相比，R1策略的運算時間最長，且貝結構越大，集裝箱數目越多，即問題規模越大，R1與R2，R3的運算時間的差距越大.

3.2.2增大目的港案例求解

將堆場12個集裝箱的目的港增大為4，即集裝箱目的港按列從左到右依次為4，3，2，1.將28個集裝箱的目的港增大為6，即集裝箱目的港按列從左到右依次為6，5，4，3，2，1.提箱策略只有按層和按列2種，再次求解，數據結果見表2.

表2　增大目的港后的案例數據處理結果

而將堆場40個集裝箱的目的港增大為6求解.發現有很多案例在兩小時內無法求出結果，5個隨機案例的求解，數據結果如表3.

表3　B3-N40-D6的數據計算結果

注：*表示案例在2 h內無計算結果.

由此可知，增加集裝箱的目的港數，運算時間也會增加.當貝結構增大為B3，堆場集裝箱的目的港數增大為6時，問題規模增大，導致該模型程序在2 h內無法求解.并且在R1策略下，模型求解更難.故下面將對此類案例進一步分析.

3.2.3改變力矩敏感系數求解

現改變力矩敏感系數δ的值，進一步分析.選擇B3-N40-D6-R1-3和B3-N40-D6-R2-3兩個案例分別改變力矩敏感系數.計算結果見表4.

表4　不同δ值下的案例求解結果

由表4可知，當問題規模擴大后，在微小的橫傾力矩約束下，模型在2 h內無法求解，若增大橫傾力矩系數，即放寬橫傾力矩約束，模型有解.而且同樣的堆場集裝箱集合裝載到同樣的船舶貝內，不同的提箱順序下的求解結果明顯不同，R1策略使得問題更為復雜，求解時間更長，需要的橫傾約束更寬.

4結 束 語

本文提出了以解決堆場集裝箱集合裝載到船舶的某個貝位確定位置的裝箱排序問題，并構建了該問題的混合整數規劃模型.該模型可以利用CPLEX中的分支定界算法進行求解.進一步，本文還分析了不同的堆場集裝箱提箱策略對船舶配載情況的影響，3種提箱策略相比，按層提箱策略明顯增加了模型求解的難度，最容易引起后續港卸船時的翻箱.而堆場中混裝集裝箱的目的港越多，問題越復雜，模型求解時間越長，但若放寬橫傾約束，求解時間可縮短.

參 考 文 獻

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

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

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

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

[5]祝慧靈,計明軍.集裝箱船舶全航線配載優化模型與改進遺傳算法[J].交通運輸工程學報,2014,14(5):59-67.

[6]MARIA F M, MARCELLO S, GREGORIO S. The terminal-oriented ship stowage planning problem[J]. European Journal of Operational Research,2014,239(1):256-265.

[7]ANA M, JORGE O, CARINA P. A mathematical model for the container stowage and ship routing problem[J]. Math Model Algor,2013,12(3):217-231.

Research on Sequencing and Bin Packing Problem with Practical Vessel Stowage Constraints

TIAN WeiZHANG YuCHENG Huimin

(SchoolofLogisticsEngineering,WuhanUniversityofTechnology,Wuhan430063,China)

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 at minimizing the loading time and overstowing time cost. According to three kinds of container sending rules, exact solutions of the cases in different scales of the problem can be obtained by using ILOG CPLEX and branch & bound algorithm. In addition, some obvious characteristics of the speed and quality of the solutions are discovered. The experiment results show that this model is effective and the cases in medium and small scales of the problem can be solved.

Key words：ship stowage; sequencing and bin packing problem; integer programming; branch & bound algorithm

收稿日期：2016-03-26

中圖法分類號：U695.2

doi:10.3963/j.issn.2095-3844.2016.03.024

田維(1990- )：女，碩士生，主要研究領域為物流系統建模與優化

*國家自然科學基金項目資助(71372202)