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

田　維　張　煜　程惠敏

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

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

田維張煜程惠敏

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

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

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

0引言

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

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

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

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

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

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

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

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

2集裝箱裝船配載模型

2.1模型假設(shè)

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

圖1　集裝箱裝載

2.2基本參數(shù)

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

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

2.3模型

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

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

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

圖2　翻箱操作過程

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

式中：第1項(xiàng)為堆場(chǎng)集裝箱的裝船時(shí)間，第2項(xiàng)為翻倒箱時(shí)間.

約束條件:

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

(1)

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

(2)

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

(3)

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

(4)

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

(5)

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

(6)

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

(7)

8) 決策變量ξkp計(jì)算

(8)

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

3案例分析

3.1案例描述

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

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

圖3　貝位圖(單位：t)

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

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

3.2.1初始案例求解

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

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

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

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

3.2.2增大目的港案例求解

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

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

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

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

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

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

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

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

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

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

4結(jié) 束 語

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

參 考 文 獻(xiàn)

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

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

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

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

[5]祝慧靈,計(jì)明軍.集裝箱船舶全航線配載優(yōu)化模型與改進(jìn)遺傳算法[J].交通運(yùn)輸工程學(xué)報(bào),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

中圖法分類號(hào)：U695.2

doi:10.3963/j.issn.2095-3844.2016.03.024

田維(1990- )：女，碩士生，主要研究領(lǐng)域?yàn)槲锪飨到y(tǒng)建模與優(yōu)化

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