鄭斐峰，梅啟煌+，王 璐，張小寧

(1.東華大學(xué) 旭日工商管理學(xué)院，上海 200051；2.上海民航職業(yè)技術(shù)學(xué)院 基礎(chǔ)教學(xué)部，上海 200232；3.同濟大學(xué) 經(jīng)濟與管理學(xué)院，上海 200092)

0 引 言

集裝箱配載問題[1]的基本目標(biāo)是保證船舶在運輸過程中的船體平衡安全。對應(yīng)地，裝卸操作需要遵從兩條規(guī)則：①離港時船舶上的每個集裝箱堆列滿足重箱在下輕箱在上的碼放規(guī)則；②所有堆列的箱子重量分布滿足在船舶前后端、左右側(cè)的平衡規(guī)則。通過設(shè)計滿足上述裝載規(guī)則的具體配載方案，提高船舶在港裝卸效率以及運輸效率。在裝卸操作時，不妨把從碼頭堆場裝載到船上以及從船舶卸載到堆場的集裝箱稱為目標(biāo)箱，同時，將船上的其它集裝箱均稱為非目標(biāo)箱，對非目標(biāo)箱的每次臨時卸載或者裝載操作都稱作一次翻箱。

近年來，不少的研究學(xué)者都對配載問題進行了研究，Delgado等[2]對于大型的集裝箱船的裝載成本進行研究，提出的模型能夠在1 s內(nèi)實現(xiàn)236個實例中的90%；Monaco等[3]以最小裝載時間為優(yōu)化目標(biāo)建立優(yōu)化模型，并設(shè)計出兩階段啟發(fā)式算法，驗證了模型的有效性；Kevin等[4]對港口內(nèi)部集裝箱運輸情況進行研究，以最小化集裝箱交付延遲時間為目標(biāo)，建立兩步式求解步驟模型，通過應(yīng)用文中的模型能夠解決現(xiàn)實中的很多實際情況，并且有利于解決交通擁堵和交付延遲懲罰等問題，對集裝箱運輸?shù)拈L期決策具有一定的指導(dǎo)作用；Liu等[5]研究岸橋雙循環(huán)和優(yōu)化集裝箱船內(nèi)部的翻箱操作的問題，以總的服務(wù)時間和啟動時間為目標(biāo)，設(shè)計了一種在多項式時間內(nèi)的啟發(fā)式算法，并將此方法與目前最先進的方法進行比較，結(jié)果表明作者提出的方法更能有效的解決此問題的模型，并且該算法能夠在數(shù)秒鐘內(nèi)對現(xiàn)實世界中的實例得出方案，極大提高了裝載效率。

從以上文獻可以看出，這些都是以單個港口為研究背景，沒有考慮到整條航線過程中的多個港口的配載情況。Francisco等[6]對集裝箱配載問題主要是對貝位的配載情況進行研究，與以往不同的是，文中提出明確處理已出貨的集裝箱和對危險箱的分離規(guī)則兩個特點。對集裝箱的配載問題建立整數(shù)規(guī)劃模型，并設(shè)計出貪婪隨機自適應(yīng)搜索算法。仿真結(jié)果表明，該方法能夠快速獲得高質(zhì)量的求解方法，并與以往研究中相同的實例進行比較分析，表明文中提出的算法對于求解此類問題可以取得更好的結(jié)果。Azevedo等[7]充分考慮航線中集裝箱船舶的裝載與卸載的不同操作，分析出12種不同的裝載和卸載的過程。在此基礎(chǔ)上依據(jù)遺傳算法、模擬退火和光束搜索3種算法開發(fā)出啟發(fā)式算法求解3D集裝箱的裝載問題。文中設(shè)計的編碼方式能夠始終保持所有的解都是可行解，極大縮短了運算時間。在一些實例中，可行解的值還能夠非常接近下界值，表明文中的方法對于港口的實際操作有一定的指導(dǎo)意義。Araújo等[8]將集裝箱看作是一個三維的結(jié)構(gòu)，提出一個旨在維持穩(wěn)定性及最小化翻箱數(shù)量的帕累托聚類搜索方法來解決3維集裝箱的配載問題，并將元啟發(fā)式算法和本地搜索啟發(fā)式算法相結(jié)合，通過數(shù)值模擬實驗證明該方法的效果比單目標(biāo)的模擬退火算法更好。Ding等[9]通過設(shè)計一個啟發(fā)式算法解決集裝箱船在多港口航線中的總翻箱數(shù)量最小的問題，并將該啟發(fā)式算法與Avriel提出的啟發(fā)式算法相比較，結(jié)果表明文中的方法對于解決此類配載問題有著更好的效果。Ambrosino等[10]在已有的單港口配載模型的文獻基礎(chǔ)上，建立了一個多港口主貝位配載計劃的混合整數(shù)規(guī)劃模型，以船舶最小化在港時間為目標(biāo)，利用混合整數(shù)規(guī)劃設(shè)計啟發(fā)式算法在短時間內(nèi)求出集裝箱的配載方案，從而幫助計劃制定人員更好應(yīng)對航行過程中變動的運輸需求。實驗結(jié)果表明，該方法能夠高效得出裝載多于18000TEUs的集裝箱配載方案。

另外，Wei等[11]、Wang[12]、Carlo[13]、Zhang[14]和Ramos等[15]也對堆場配載和配載復(fù)雜性等問題做了相關(guān)的研究。在關(guān)于配載問題的相關(guān)文獻中，大部分都是關(guān)于單個港口配載計劃的文獻，多個港口配載計劃的文獻相對較少，前人的研究大多是以船舶的在港時間或裝載時間作為目標(biāo)。文中不只是對單個港口的配載情況進行優(yōu)化，主要針對多港口的集裝箱船配載問題，以最小化的總航線的翻箱數(shù)量為目標(biāo)，在考慮船舶穩(wěn)定性的基礎(chǔ)上，提出從考慮所有翻箱的可能性角度出發(fā)，充分考慮整個航線中的具體翻箱操作，建立0-1整數(shù)規(guī)劃模型，使得整個航線過程中翻箱的數(shù)量達到最小，最后利用CPLEX對中小型集裝箱船單個貝位的裝載實例進行求解得出精確的配載方案，提高了港口的運作效率，彌補了以往研究在中型集裝箱船配載問題中無法快速取得精確解的不足，對現(xiàn)實中我國如武漢港、蕪湖港等內(nèi)地港口船舶配載有實際的指導(dǎo)意義。

1 問題描述

集裝箱船舶在碼頭進行裝卸操作時，船上每一個貝位的所有目標(biāo)箱的裝卸工作只能由一個岸橋來完成，在此過程中涉及的非目標(biāo)箱翻箱作業(yè)也必須在該貝位內(nèi)由同一個岸橋進行操作。由于目標(biāo)箱本身的裝卸操作時間是確定的，因此，貝位內(nèi)的裝卸效率大小取決于非目標(biāo)箱的翻箱次數(shù)或時間。要降低艘船舶的在港逗留時間或者提升裝卸效率，其中一個可行的思路就是設(shè)法減少貝位內(nèi)的翻箱次數(shù)?？紤]船舶在整條航行路線中需要歷經(jīng)上下游多個港口，因此，為了提升它在整條航線上的運輸效率，就要減少它在所有港口非目標(biāo)箱的翻箱總次數(shù)。假定所有岸橋的作業(yè)效率相同，則每個貝位在任一港口的作業(yè)效率取決于該貝位內(nèi)的翻箱作業(yè)量。本研究以船舶的某個貝位作為具體分析對象，研究該貝位在多個港口中的配載計劃方案，以實現(xiàn)在船舶的整個運輸過程中，該貝位的翻箱次數(shù)最少的優(yōu)化目標(biāo)。

圖1是一個平面二維上的集裝箱船舶示意圖。從船舶的側(cè)面看，船頭至船尾接連堆放的集裝箱組成了不同的貝位，一個貝位的寬度等于一個集裝箱的長度；每個貝位從甲板的左側(cè)至右側(cè)碼放著許多列的集裝箱，每一列上垂直堆放著多個集裝箱，一個箱子占用一層的位置。因此，每個集裝箱在船舶上的位置可以用它所在的(列，層)編號來表示。這里，假設(shè)所有的集裝箱都是20英尺的TEU標(biāo)準(zhǔn)箱。

圖1 集裝箱船的側(cè)視和俯視

考慮多港口的單貝位配載計劃問題研究主要基于以下一些基本假設(shè)：

(1)船舶依次停靠1,2,…,T港口，在各個港口的所有目標(biāo)箱信息事先已知。在港口1只有裝載操作，而在港口T只有卸載操作并且船上所有集裝箱都要求卸載；

(2)為了員工操作簡單，非目標(biāo)箱的翻箱不允許在甲板不同列之間直接進行操作，它必須包括臨時卸載和再次裝載兩次操作，而且翻箱操作只在該貝位內(nèi)進行；

(3)所有集裝箱的重量分為1,2,3這3個等級，數(shù)字越大表示集裝箱越重。在任一時刻船舶上的所有集裝箱列必須滿足重箱在下輕箱在上的碼放規(guī)則；

(4)基于配載安全要求，每一列的集裝箱數(shù)量以及集裝箱總重量均有一個規(guī)定上限。

在相關(guān)文獻中，理工學(xué)院Avriel等假設(shè)每個集裝箱的翻箱成本都為1，以此來求的最小的翻箱成本，實質(zhì)上與翻箱數(shù)量是相同的，翻箱成本即為最終的翻箱數(shù)量，而且文中的模型并沒有考慮貝位中的重量約束，集裝箱重量不同的情況以及航線中船舶的穩(wěn)定性。梁承姬等[16]考慮了單港口集裝箱船裝載計劃，在堆場中的預(yù)翻箱數(shù)量問題，孫等[17]假設(shè)集裝箱在某港口產(chǎn)生翻箱時，先后兩次的位置是不相同的，而在實際中，翻箱先后的兩次位置也是有可能會是相同的，文中考慮的是所有翻箱的情況，包含翻箱先后兩次位置相同和不相同的情況。

2 模型建立

2.1 符號說明

(1)索引

t：表示港口的序號；

i,j：表示集裝箱的序號；

c：表示貝位中列數(shù)的序號，從左到右依次是1,2,3,…,C；

r：表示貝位中層數(shù)的序號，從上到下依次是1,2,3,…,R；

(2)參數(shù)

T：航線中港口的集合，t=1,2,3,…,T；

C：每個貝位中的總列數(shù)；

R：表示貝位中每列的總層數(shù)；

N：T個港口中裝載的集裝箱的集合，i,j=1,2,3,…,N；

wi：第i個集裝箱的重量；

si：向船舶中裝載的第i個集裝箱的出發(fā)港口；

di：從船舶中卸載的第i個集裝箱的目的港口；

Dt：在第t個港口目標(biāo)箱的集合，即，Dt={i|di=t}∪{i|si=t}；

Ut：在第t個港口非目標(biāo)箱的集合，即，Ut={i|si

W：貝位中每一列允許的集裝箱最大載重量；

M：一個充分大的正整數(shù)；

(3)決策變量

2.2 建立0-1整數(shù)規(guī)劃模型

根據(jù)在整個航線過程中，保證船舶運輸安全的情況下，最小翻箱的目標(biāo)，建立如下的0-1整數(shù)規(guī)劃模型

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

i,j∈N,r,c∈Z+,r≤R,c≤C,t∈T

(16)

目標(biāo)函數(shù)(1)表示最小化整條航線中的翻箱數(shù)量；約束(2)和約束(3)指任意一個集裝箱i的出發(fā)港口si大于目前所?？康母劭趖或者目的港口di小于目前所?？康母劭趖，這兩種情況下，集裝箱i都不能被裝載在貝位的任何一個箱位上；約束(4)表示在航線中的任何港口，任何一列上所有集裝箱的總重量不能超過規(guī)定的總重量W；約束(5)表示在航線中的任何港口，任何一列上所有的集裝箱的總數(shù)量不能超過總的層數(shù)R；約束(6)表示在航線中的任何港口，任何一個箱位上最多只能裝載一個集裝箱；約束(7)任意一個已經(jīng)被裝載到貝位上的集裝箱在還沒有到達目的港口之前，一定是在貝位中的一個箱位上，不能被提前卸載；約束(8)在航線中的任何一個港口的任意一列上，如果一個箱位上已經(jīng)被裝載了集裝箱，那么它的下一層也一定裝載了集裝箱；約束(9)表示在航線中的任何港口，任何一列上都必須滿足重量大的集裝箱必須裝載在重量小的集裝箱的下面；約束(10)船舶離開航線中的任意一個港口(除了最后一個港口)時，貝位中集裝箱的位置與剛到達下一個港口時位置是相同的；約束(11)在集裝箱船到達最后一個港口時，所有的集裝箱都應(yīng)該被卸載；約束(12)如果非目標(biāo)箱i在進入港口t與離開港口t時的位置不同，那么它一定會產(chǎn)生一次翻箱，如圖2和圖3所示；約束(13)在船舶到達港口t時，集裝箱i是裝載在(c,r)箱位上的非目標(biāo)箱，如果在集裝箱i同一列的下面存在一個目標(biāo)箱j，即使集裝箱i的位置沒有發(fā)生變化，它在t港口也一定會產(chǎn)生一次翻箱，如圖4所示，集裝箱6被卸載，集裝箱9被裝載到了原來集裝箱6的位置上，雖然集裝箱3 的位置沒有變化，但是集裝箱3一定產(chǎn)生過一次翻箱操作；約束(14)在船舶到達港口t時，集裝箱i,j是裝載在同一列上的兩個非目標(biāo)箱，并且集裝箱i裝載在j的下面，如果集裝箱i在港口t被翻箱一次，那么即使集裝箱j的裝載位置在離開港口t時沒有產(chǎn)生變化，集裝箱j在港口t也一定產(chǎn)生了一次翻箱，如圖5所示，集裝箱6被裝載到了其它的位置上，集裝箱9裝載到了原來集裝箱6的位置上，雖然集裝箱3沒有改變位置，但是集裝箱3肯定產(chǎn)生過一次翻箱操作；約束(15)和約束(16)分別表示決策變量和各參數(shù)的范圍。

圖2 目標(biāo)箱6在第2列中被卸載

圖3 目標(biāo)箱6被裝載到第2列中

圖4 裝載和卸載的集裝箱在同一個箱位上

圖5 非目標(biāo)箱6在進港和出港時改變了位置

3 貪婪算法及實例分析

3.1 貪婪算法

貪婪算法是指，在對問題求解時，不從整體最優(yōu)上加以考慮，所做出的是在某種意義上的局部最優(yōu)解，有時甚至可以達到全部最優(yōu)解。在實際的集裝箱運輸過程中，港口的工作人員一般都是根據(jù)以往的工作經(jīng)驗進行船舶集裝箱的配載工作，文中針對這一配載情況，采用貪婪策略進行研究如下：

步驟1 將每個港口所裝載的集裝箱按照重量大小排序，重量相同的按照目的港口由近到遠排列；

步驟2 將重量相同的集裝箱裝載在貝位同一列中，目的港口較遠的優(yōu)先裝載；

步驟3 在每列中滿足重箱在下輕箱在上的裝載規(guī)則，并且每列裝載的數(shù)量不能超過規(guī)定值，滿足層數(shù)約束；

步驟4 檢驗每列的裝載重量和層數(shù)，若不滿足重量限制，則將最上面的集裝箱與目的港口相同且較輕的集裝箱交換裝載位置或者將該集裝箱裝載到新的一列上，直到滿足每列的重量約束；

步驟5 根據(jù)翻箱規(guī)則，計算多港口間的總翻箱次數(shù)。

3.2 實例分析

從運力上來看，大型集裝箱船(5000TEUs以上)的運力與小型集裝箱船(3000TEUs以下)達到了相同的比例，加上中型集裝箱船，則中小型船達到了63.3%的比例，中小型集裝箱船仍然占據(jù)著主要的地位。文中的模型針對我國內(nèi)地港口的發(fā)展情況，對中小型集裝箱船的配載問題能夠很快得以解決，并且能夠直接求得最優(yōu)的配載方案。以下是文中精確解與文獻中精確解的比較分析，見表1。由表1中結(jié)果分析可知，文章中的方案可以求解出多個港口較大運輸量的集裝箱配載方案。

表1 文章精確解與文獻精確解的比較

為了考慮船舶航行的安全性，結(jié)合實際情況考慮，甲板上裝載的集裝箱最高只能達到8層。假設(shè)集裝箱的重量有3種等級，分別為1、2、3，重量為1代表輕箱，重量為2代表中型箱，重量為3代表重箱；船舶上每個貝位一共裝載7列，并且貝位中的每一列上的重量不超過23，重量越大的集裝箱裝載的層數(shù)越低。船舶從第一個港口開始，分別經(jīng)過2、3、4、5、6、7港口，最終到達第8號港口，并且在第一個港口時船上不存在集裝箱，只進行裝箱操作，當(dāng)船舶到達最后一個港口時，集裝箱應(yīng)全部被卸載。在多港口的實際配載過程中，由于每次裝載集裝箱的重箱比例以及航線中船舶的裝載率并不一定都是保持不變，因此文章針對航線中集裝箱船的裝載率以及集裝箱不同等級的重量比例進行仿真實驗。分別對30%、40%、50%、60%、70%的裝載率下重箱比例分別為30%、45%、60%、75%、90%的配載情況，利用模型和貪婪策略進行實驗分析，仿真實驗的結(jié)果見表2。

表2 不同裝載率以及不同重箱比例下的翻箱結(jié)果

注：GM表示貪婪算法。

隨著裝載率和重箱比例的不斷增加，貪婪算法對于求解此類問題也逐漸產(chǎn)生較好的方案。通過查閱相關(guān)資料所得，在內(nèi)地港口翻箱一次所產(chǎn)生的費用大約是100元，每次的翻箱時間為3分鐘。當(dāng)船舶航線中裝載率為30%時，文章中的算法比貪婪算法所提出的配載方案能使班輪公司每次航行平均大約節(jié)約2400元，節(jié)省72分鐘；而當(dāng)裝載率為70%時，每次航行大約能節(jié)約2000元，節(jié)省60分鐘。

近年來，長江流域是我國最具經(jīng)濟活力的地區(qū)之一，增速達到年均10%。由于長江沿岸集裝箱運輸發(fā)展迅速，雖然出現(xiàn)了“一哄而起，趕潮進入”現(xiàn)象，使得競爭加劇，但是仍然有大量的資金融入市場，對于船運公司和港口碼頭來說，這是一個新的機遇與挑戰(zhàn)。根據(jù)相關(guān)文獻統(tǒng)計，長江沿岸集裝箱貨物裝載率大約為50%至70%左右，而重箱的比例大約是50%至60%左右[19]。進一步說明文中的研究與長江沿岸集裝箱船舶的實際裝載情況相符合。

由以上分析可知，雖然隨著裝載率和重箱比例的逐漸增加，貪婪算法求解的配載方案也逐漸優(yōu)化，但文中模型中的方法比貪婪算法更有效。同時與貪婪算法相比，也進一步降低了班輪公司的運輸成本并且提高了港口的工作效率，對我國長江沿岸港口集裝箱的配載情況具有一定的指導(dǎo)作用。

4 結(jié)束語

配載計劃一直是集裝箱運輸?shù)囊淮蟓h(huán)節(jié)，制定出合理的配載方案是提高集裝箱裝載效率的關(guān)鍵。針對以往研究中大多是以在港時間和裝載時間為目標(biāo)的配載研究，在維持航行過程中船舶穩(wěn)定性的情況下，建立了0-1整數(shù)規(guī)劃模型，提出考慮航線中所有港口的各種可能產(chǎn)生翻箱的情況，詳細的記錄了每個港口集裝箱的位置，具體的描述了每個港口的翻箱操作，以最小化航線過程中翻箱的數(shù)量為目標(biāo)，解決了每個貝位在整條航線中精確配載問題，對于我國內(nèi)地港口的中小型集裝箱船的配載研究具有一定的指導(dǎo)意義。

另外，針對多港口集裝箱配載問題，由于船舶的穩(wěn)定性受諸多因素的影響，航行過程中整個船舶的配載情況，船首和船尾裝載的重量差以及船舶左右裝載的重量差限制，重心的傾斜程度等?？紤]影響船舶配載的各種因素，提高裝載的效率，降低運營成本，這是下一步研究的重點。

參考文獻：

[1]Surging News.A ship roll 44 containers down the river,all the salons overnight salvage in Shanghai[EB/OL].[2016-05-02].http://www.thepaper.cn/newsDetail_forward_1463772(in Chinese).[澎湃新聞網(wǎng).上海一輪船側(cè)傾44只集裝箱落江,經(jīng)一夜打撈全部出水[EB/OL].[2016-05-02].http://www.thepaper.cn/newsDetail_forward_1463772.]

[2]Delgado A,Jensen R M,Janstrup K,et al.A constraint programming model for fast optimal stowage of container vessel bays[J].European Journal of Operational Research,2012,220(1):251-261.

[3]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.

[4]Tierney K,Vo? S,Stahlbock R.A mathematical model of inter-terminal transportation[J].European Journal of Operational Research,2014,235(2):448-460.

[5]Liu M,Chu F,Zhang Z,et al.A polynomial-time heuristic for the quay crane double-cycling problem with internal-reshuffling operations[J].Transportation Research Part E,2015,81:52-74.

[7]Azevedo A T D,Ribeiro C M,Sena G J D,et al.Solving the 3D container ship loading planning problem by representation by rules and meta-heuristics[J].International Journal of Data Analysis Techniques & Strategies,2014,6(3):228-260.

[8]Araújo E J,Chaves A A,Neto L L D S,et al.Pareto clustering search applied for 3d container ship loading plan problem[J].Expert Systems with Applications,2015,44(1):50-57.

[9]Ding D,Chou M C.Stowage planning for container ships:A heuristic algorithm to reduce the number of shifts[J].European Journal of Operational Research,2015,246(1):242-249.

[10]Ambrosino D,Paolucci M,Sciomachen A.A MIP heuristic for multi-port stowage planning[J].Transportation Research Procedia,2015,10:725-734.

[11]Wei L,Zhu W,Lim A.A goal-driven prototype column ge-neration strategy for the multiple container loading cost minimization problem[J].European Journal of Operational Research,2015,241(1):39-49.

[12]Wang S.Optimal sequence of container ships in a string[J].European Journal of Operational Research,2015,246(3):850-857.

[13]Carlo H J,Vis I F A,Roodbergen K J.Transport operations in container terminals:Literature overview,trends,research directions and classification scheme[J].European Journal of Operational Research,2014,236(1):1-13.

[14]Zhang Z,Lee C Y.Multiobjective approaches for the ship stowage planning problem considering ship stability and container rehandles[J].IEEE Transactions on Systems Man & Cybernetics Systems,2016,46(10):1374-1389.

[15]Ramos A G.Dynamic stability metrics for the container loa-ding problem[J].Transportation Research Part C,2015,60:480-497.

[16]LIANG Chengji,ZHENG Juanjuan,LIU Yang.Container pre-marshalling simulation research based on heuristic algorithm[J].Computer Simulation,2014,31(12):416-420(in Chinese).[梁承姬,鄭娟娟,劉揚.基于啟發(fā)式算法的集裝箱預(yù)翻箱問題仿真研究[J].計算機仿真,2014,31(12):416-420.]

[17]SUN Junqing,CHEN Chen,LIU Fenglian.On stowage planning for mult-port container transportation based on stabi-lity constraint[J].Computer Engineering and Applications,2012,48(32):236-243(in Chinese).[孫俊清,陳忱,劉鳳連.考慮船舶穩(wěn)定性的多港口集裝箱配載問題[J].計算機工程與應(yīng)用,2012,48(32):236-243.]

[18]Cruz-Reyes L,P H H,Melin P,et al.Constructive algorithm for a benchmark in ship stowage planning[M].Recent Advances on Hybrid Intelligent Systems. Springer Berlin Heidelberg,2013:393-408.

[19]HAN Jingwei.Research on the development of the yangtze river container logistics space[J].Research on Economics and Management,2014(3):103-109(in Chinese).[韓京偉.長江內(nèi)河集裝箱物流發(fā)展空間研究[J].經(jīng)濟與管理研究,2014(3):103-109.]