內地多港口間的集裝箱配載最優方案

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

(1.東華大學 旭日工商管理學院，上海 200051；2.上海民航職業技術學院 基礎教學部，上海 200232；3.同濟大學 經濟與管理學院，上海 200092)

0 引 言

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

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

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

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

1 問題描述

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

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

圖1 集裝箱船的側視和俯視

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

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

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

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

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

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

2 模型建立

2.1 符號說明

(1)索引

t：表示港口的序號；

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

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

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

(2)參數

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

C：每個貝位中的總列數；

R：表示貝位中每列的總層數；

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

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

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

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

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

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

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

M：一個充分大的正整數；

(3)決策變量

2.2 建立0-1整數規劃模型

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

(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)

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

圖2 目標箱6在第2列中被卸載

圖3 目標箱6被裝載到第2列中

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

圖5 非目標箱6在進港和出港時改變了位置

3 貪婪算法及實例分析

3.1 貪婪算法

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

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

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

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

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

步驟5 根據翻箱規則，計算多港口間的總翻箱次數。

3.2 實例分析

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

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

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

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

注：GM表示貪婪算法。

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

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

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

4 結束語

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

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

參考文獻：

[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).[澎湃新聞網.上海一輪船側傾44只集裝箱落江,經一夜打撈全部出水[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).[梁承姬,鄭娟娟,劉揚.基于啟發式算法的集裝箱預翻箱問題仿真研究[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).[孫俊清,陳忱,劉鳳連.考慮船舶穩定性的多港口集裝箱配載問題[J].計算機工程與應用,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).[韓京偉.長江內河集裝箱物流發展空間研究[J].經濟與管理研究,2014(3):103-109.]