船舶實配現(xiàn)實約束下的裝箱排序問題研究*

田　維　張　煜　程惠敏

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

船舶實配現(xiàn)實約束下的裝箱排序問題研究*

田維張煜程惠敏

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

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

關(guān)鍵詞：船舶配載；裝箱排序；整數(shù)規(guī)劃；分支定界

0引言

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

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

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

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

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

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

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

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

2集裝箱裝船配載模型

2.1模型假設(shè)

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

圖1　集裝箱裝載

2.2基本參數(shù)

N為堆場待裝載到船舶某貝的集裝箱集合；I為貝內(nèi)列的集合；J為貝內(nèi)層的集合；D為堆場集裝箱目的港的集合；k為堆場待裝載到船舶貝內(nèi)的集裝箱編號，對應(yīng)其裝船順序，k∈N={1,2,…,n}；Ji為船舶該貝第i列所有箱位的集合；p=(i,j)為船舶該貝第i列第j層的箱位，i∈I={1,2,…,‖I‖}；j∈Ji={1,2,…,‖Ji‖};L(p)為船舶該貝左側(cè)的箱位的集合；R(p)為船舶該貝右側(cè)的箱位的集合；tp為集裝箱裝到船舶上p箱位的裝船時間，由于陸側(cè)起重機初始位置在船舶最左邊的上方，每一層從左向右裝船時間逐一遞增，按列從上向下裝船時間逐一遞增，則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；δ為力矩敏感系數(shù)，可取5，10，15，…，HM的單位為：kN·m.

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

2.3模型

優(yōu)化目標是使裝船時間最小，同時保證在后續(xù)港卸船時的翻倒箱數(shù)最少.

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

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

圖2　翻箱操作過程

綜上，目標函數(shù)：

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

約束條件:

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

8) 決策變量ξkp計算

(8)

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

3案例分析

3.1案例描述

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

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

圖3　貝位圖(單位：t)

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

3.2案例結(jié)果及分析

3.2.1初始案例求解

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

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

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

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

3.2.2增大目的港案例求解

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

表2　增大目的港后的案例數(shù)據(jù)處理結(jié)果

而將堆場40個集裝箱的目的港增大為6求解.發(fā)現(xiàn)有很多案例在兩小時內(nèi)無法求出結(jié)果，5個隨機案例的求解，數(shù)據(jù)結(jié)果如表3.

表3　B3-N40-D6的數(shù)據(jù)計算結(jié)果

注：*表示案例在2 h內(nèi)無計算結(jié)果.

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

3.2.3改變力矩敏感系數(shù)求解

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

表4　不同δ值下的案例求解結(jié)果

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

4結(jié) 束 語

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

參 考 文 獻

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

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

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

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

[5]?；垤`,計明軍.集裝箱船舶全航線配載優(yōu)化模型與改進遺傳算法[J].交通運輸工程學(xué)報,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- )：女，碩士生，主要研究領(lǐng)域為物流系統(tǒng)建模與優(yōu)化

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