跨區域遠洋航線空集裝箱動態調運優化模型

蘆立華 ，張恒振 ，王曉峰

1.復旦大學 計算機科學技術學院，上海市智能信息處理重點實驗室，上海 200433

2.上海電機學院 電子信息學院，上海 201306

3.上海海事大學 信息工程學院，上海 201306

1 引言

近年來，隨著全球一體化進程的發展，國際貿易快速增長，集裝箱運輸在國際運輸體系，尤其是海上運輸體系中的地位日益增高。據不完全統計，2013年國際貿易貨物運輸總量中，77%的貨物是通過海運完成的，而海運中超過23.7%以上的貨物又是通過集裝箱運輸的[1]。另外，由于世界經濟發展的不平衡以及國家間進出口貿易的差異，導致了在集裝箱導入國的各個港口（多箱港）集聚了大量的空集裝箱，如歐洲和美洲區域的港口。與此同時，在集裝箱導出國的各個港口（需箱港）又急需大量的空集裝箱，如東南亞區域的港口。以太平洋航線為例：2013年從亞洲到北美運輸的貨物量大約為13.3百萬TEUs（20尺標準箱），而從北美到亞洲僅運送了6.9百萬TEUs貨物[1]。

此外，據不完全統計，每年全球集裝箱空箱調運量占全部集裝箱總運量的20%左右，部分航線空箱調運的比率甚至接近50%。巨大的空箱調運費用、存儲費用和租借費用大大降低了航運企業的利潤，甚至進一步威脅到其在航運企業的生存狀況。因此，為增加市場競爭力，對空集裝箱進行合理調運和優化管理越來越成為各個航運企業亟待解決的問題。

通常說來，一個大型的航運企業經營多條航線，其中包括遠洋航線和近洋航線。前者一般指跨越大洋連接兩個或多個大洲的航線，后者一般指距離較短的近陸港口間的海上運輸航線，包括內河航線、和鄰近國家間航線。遠洋航線和近洋航線又通過樞紐港（hub port）和支線港（feed port）交織形成了一個復雜的航運網絡。如何針對這兩種航線進行空箱調運優化操作是本文研究的關鍵問題。

2 相關研究

國內外學者對于集裝箱空箱調運問題進行了諸多研究，主要集中在兩個方面：一方面主要是基于建立港口空集裝箱安全庫存管理體系[2-4]，另一方面則主要是利用動態網絡方法進行集裝箱空箱調運優化研究[5-7]。施欣[8]通過對集裝箱海上空箱調運過程的剖析，建立了相應的系統優化模型。Cheung和Chen[9]建立了海上空箱調運的兩階段隨機優化模型，第一階段是多箱港口可提供的空集裝箱數量、需箱港口需要的空集裝箱數量和船舶可裝載集裝箱量等諸多參數是確定的；第二階段則將上述這些參數看作是隨機變量，然后在此基礎上建立優化模型。Lam[10]提出了在操作層面上的近似動態集裝箱空箱調運優化方法，并且根據航運公司實際航線網絡，將通用網絡技術應用到航運業中。Meng和Wang[11]融合中心輻射模式和多港直靠模式，設計航線服務網絡和開發混合整數線性規劃模型。Crainic等[12]研究了空集裝箱的動態隨機分配問題，并將長期租箱問題作為其中的要素加以考慮。Li等[2]從減少空箱調運的數量這個角度出發，研究了港口間的空箱調運問題。石玉峰[13]采用隨機機會約束規劃方法建立戰時運輸路徑優化模型，設計了基于隨機模型獲取適應度的遺傳算法求解問題。綜合考慮航運公司戰略層、策略層和操作層運營規劃，Song和Dong[14]提出了綜合遠洋班輪航線設計、船舶部署和空集裝箱調運三層次的最小成本優化模型。Long等[15]從集裝箱供需不確定性的角度出發設計了一個兩階段隨機規劃模型，目標是優化集裝箱空箱調運成本。Song和Dong[16]在多航線、多船舶部署和多班輪航次，整體規劃重箱運輸線路和空箱調運，以達到相關運營成本最小。

傳統的研究主要集中在將港口劃分為多箱港和需箱港，調度計劃在港口-港口間這種點-點的模式下發生，因此存在如下三個問題：（1）集裝箱調運計劃往往是提前制定的，由于遠洋航線距離較長，船舶離開多箱區域始發港，到達需箱區域目的港時，需箱區域各個港口需箱量或多箱量都發生了較大變化，這種計劃調運和實施調運的不同步性直接導致調運成本劇增和調運效率低下。（2）傳統的港口-港口的調運計劃，受港口業務波動影響較大，進而產生了相應的存儲成本和租賃成本。（3）大量的決策變量和無用的約束條件，導致模型復雜，優化求解時間較長。

集裝箱空箱調運計劃是建立在對未來某時期內需箱港口需箱量預測的基礎上的。如果計劃周期過長往往導致計劃供需和實際供需之間波動較大，這樣制定的調運計劃往往有諸多弊端，產生的經濟效益會大打折扣。因此，本文針對計劃供需和實際供需時間的不同步性，根據港口歷史數據和經濟形勢判斷，設立港口安全庫存量，由于該部分不在本文討論的范圍，因此在文中假設安全庫存量為一個給定的值。其次，由于航運公司在某港口集裝箱量是動態變化的，因此，建立了一個周期的跨區域遠洋航線空箱動態調運優化模型。和以往研究者重點研究港口-港口之間調運優化模型不同，該模型是基于連接兩個區域的遠洋航線空箱調運計劃。該模型將調運計劃分為兩個部分：第一部分是建立在區域之間一個與貨物流相反的空箱調運流，即基于宏觀區域調運，這樣可以使得空箱調運受微觀港口變化影響較小。第二部分建立動態調運優化模型，將調運計劃分為兩階段。第一階段制定調出計劃，此時根據需箱區域的需箱量，利用成本優化算法計算調出港口的空箱數量，只確定調往的需箱區域，不確定具體卸載空箱的需箱港口。第二階段，當班輪抵達需箱區域后，再根據各港口的需箱量利用成本最小算法做具體的分配計劃。經過這兩個階段的處理，可以在一定程度上消除計劃供需和實際供需時間上不同步帶來的供需不一致問題，從而降低相應的租賃成本和存儲成本。

3 集裝箱空箱調運優化模型

3.1 問題描述

集裝箱班輪運輸是按事先制定的航線和船期表進行運營且短期內不發生變化的運輸形式。遠洋班輪一般為一周發一班。通常說來，3~6個月可能根據季節業務變化進行一些調整。一條航線由多個港口掛靠序列組成，航運網絡由港口和航線組成。由于空箱調運問題牽涉的因素較多，如港口繁忙程度、船舶在航線上的部署情況、班輪裝載量因子、班輪在港口掛靠時裝卸集裝箱情況、班輪重箱裝載問題等等。因此該問題是一個典型的且復雜的優化問題[17]。

為便于建立優化模型，文中抽取了直接影響空箱調運的主要因素如下：

（1）港口集裝箱的供給量和需求量。其中，供給主要包括客戶還箱量、調入港口的集裝箱量和租借集裝箱量。當客戶還箱量加上庫存箱量和調入箱量均無法滿足客戶用箱需求量時，班輪公司采用租箱策略，即向集裝箱租賃公司租借集裝箱以滿足用箱需求。需求主要是指客戶需要租賃班輪公司的空集裝箱來裝載貨物。

（2）調運費用。主要包括空箱裝卸費用和運輸費用。

（3）航線。航運網絡中所有可以用來調運空箱的航線。

（4）安全庫存。指航運公司在一個港口預先存儲一定的空集裝箱，以滿足客戶的用箱需求。文中在計算港口空箱多箱量的時候指的是空集裝箱凈多箱量，即已經考慮了安全庫存之后的值。同樣在計算港口需箱量的時候也是指空箱凈需箱量。

（5）地理區域。根據航運企業遠洋航線設計和貿易情況，文中把全球劃分成幾個重要的經濟區域，包括東南亞區域（需箱區域）、歐洲區域（多箱區域）、北美區域（多箱區域）等。不失一般性地，由于貿易不平衡，多箱區域和需箱區域短期內其狀態不會發生變化。文中的區域主要指地理位置上所屬的經濟區域，跨區域航線指的就是跨越上述兩個區域的遠洋航線。

（6）船舶可用艙位。因為空箱運輸不會直接帶來經濟收益，因此利用船舶裝載重箱之后所余的艙位進行空箱調運，以此降低調運成本。

本文設計了一個時間-空間網絡模型來模擬跨區域空箱調運問題，如圖1所示。圖1表示兩個區域K1和K2間的集裝箱流，包括三條航線L1，L2，和L3。其中，L1是跨區域的航線，即遠洋航線，部署在L1航線上的班輪在K1區域內依次掛靠A港、B港和C港，裝載從K1區域調運的空集裝箱進入區域K2，在K2內分別掛靠D港、E港和F港。從K1區域各港口調運的空集裝箱根據K2區域實時需求分配到各個掛靠港口，班輪掛靠F港后再次返回K1區域的A港，重復此過程。L2和L3是區域內航線，即近洋航線，分別在K1和K2區域內循環航行，可以分別在K1和K2區域內進行空箱調運。由于區域內航線時間短，掛靠港口的頻率較高，相應的費用也比較低，一般跨區域航線和區域內航線都能進行調運的情況下，優先選用區域內航線。如：從A港到B港的調運，既可以選擇L1航線，也可以選擇L2航線，此時后者優先。

3.2 模型假設

圖1 兩個區域（K1和K2）間的集裝箱調運流

由于班輪公司進行集裝箱空箱調運過程中，影響其調運決策的因素很多，為了簡化問題，并最大限度地和實際運輸業務相一致，文中對該模型作如下假設。模型內（包括租箱）所有集裝箱大小尺寸相同，即，只考慮單一箱型，如20英尺箱。其他尺寸的箱型可以轉化為20英尺的標準箱。如果自有集裝箱不能滿足需求，可以使用租賃策略且沒有數量限制。任何港口在任何時刻存儲集裝箱的能力不受限制。多箱港口可以提供的可用空集裝箱數量和需箱港口所需要的空集裝箱數量都是滿足本港口集裝箱保有量的前提下給出的，即凈需求或凈供給。航線和船期是事先給定的。

3.3 模型參數

3.3.1 參數

gt,i,k：t周期內K區域內港口i空集裝箱供給量。

ht,i,k：t周期內K區域內港口i空集裝箱需求量。

i,j,l：港口標識符，i,j,l∈{1,2,…,P}，P是港口編號，其中，i,l∈K1，j∈K2。

t：周期，t∈{1,2,…,T}，T表示計劃周期的長度。

k：港口所在的區域，k∈{1,2,…,Q}，Q是區域編號。

3.3.2 決策變量

ut,i：t周期內港口i卸載的集裝箱數量。

wt,i：t周期內港口i裝載的集裝箱數量。

xt,i,j：t周期內從港口i到港口j運輸集裝箱數量。

yt,i：t周期內港口i存儲集裝箱數量。

zt,i：t周期內港口i租借集裝箱數量。

3.4 數學模型

目標函數（1）包含兩部分：Ct和Ct+1。其中，第一項表示在t周期內發生的費用，包括裝載費用、區域內的運輸費用和未調出的空集裝箱的存儲費用。Ct+1表示t+1周期內發生的費用，包括卸載費用、跨區域的運輸費用、多余空集裝箱的存儲費用和通過調箱仍不能得到滿足的空箱量而產生的租箱費用。

約束條件（2）表示多箱區域跨區運出的空集裝箱量之和等于多箱區域各個港口裝載的空集裝箱量之和。約束條件（3）表示多箱區域內多箱港口多余的集裝箱量之和等于調出的箱量和本地存儲箱量之和。此約束確保集裝箱總量保持不變。約束（4）保證t+1周期內港口i庫存空集裝箱量等于t周期內庫存的空集裝箱量加上t+1時間段內卸載的集裝箱量（或者減去裝載的空集裝箱量）再加上租借的集裝箱量和客戶歸還的集裝箱量。約束（5）保證在t+1周期內，港口i裝載的空集裝箱量小于可利用的集裝箱量。

3.5 遠洋跨區域動態空箱調運算法

本節給出跨區域遠洋航運動態空箱調運算法，其偽碼如算法1所示。其中，第6行的第二項表示t周期的運輸費用，這個階段計算的運輸費用是指從空箱裝載港口到離開多箱區域K1的最后一個港口之間所發生的運輸費用。如果空箱裝載港口是多箱區域的最后一個港口，則運輸費用為0。

算法1遠洋跨區域動態空箱調運算法

第19行表示從K1區域調運的空箱量大于K2區域的需箱港口的需箱量之和。在這種情況下，跨區域調運的集裝箱量大于新的需求，但是根據實際業務情況考慮，不可能再將多余的空集裝箱返航調回，只能選擇在需箱區域的各個港口進行卸載。本文對這些多余空箱分配策略采用的是：在滿足重箱運載需求的情況下，將多余的空箱盡量卸載到成本最小的港口。

第20行的第二項表示運輸費用，這里的運輸費用是指從離開K1區域最后一個港口到空集裝箱卸載港口之間發生的運輸費用，也就是第二階段的運輸費用。第三項表示存儲費用，它包含兩部分，第一部分是從K1區域到K2區域多調的空箱所產生的存儲費用，第二部分是指表示K2區域內多箱港口多出的空箱所產生的存儲費用。

第21行表示所有港口存儲的集裝箱量等于從K1區域到K2區域多調的空箱量Trans-N′t+1,k2和K2區域內多箱港口多出的空箱量Nt+1,k2之和。

第23行表示K1區域調運的空集裝箱量與K2區域內多箱港口多余的空集裝箱之和小于K2區域需箱港口的需箱量，也就是不管區域間調運還是區域內調運都不能滿足用箱需求，這種情況下就必須通過租箱來滿足客戶需求。

第28行表示K1區域調運的空集裝箱量與K2區域內多箱港口多的空集裝箱之和大于K2區域需箱港口的需箱量。

4 實驗與數據分析

實驗模擬了遠洋航線連接的兩個主要經濟區域的航運網絡，包括跨區域遠洋航線2條，區域內航線4條，分別屬于K1區域和K2區域，港口9個。其中，4個港口屬于K1區域內港口，5個屬于K2區域內港口。

根據兩個階段可能發生的情況列舉了六種不同供需關系下的情況，如表1所示。第一階段存在兩種情況，情況1：K1區域港口能夠提供的空集裝箱總量大于K2區域港口估計需要的空集裝箱量，此時，調運量等于K2區域港口的估計需求量。情況2：K1區域港口能夠提供的空集裝箱總量小于K2區域港口估計需要的空集裝箱量，此時，調運量等于K1區域港口的供給量。第二階段存在三種可能發生的情況，情況1：從K1區域運輸到K2區域的集裝箱量大于K2區域需箱港口實際需求量。情況2：從K1區域運輸到k2區域的集裝箱量小于K2區域需箱港口實際需求量，并且K2區域多箱港口調運仍然不能滿足K2區域需箱港口的需要，K2需箱港口需要租箱。情況3：從K1區域運輸到K2區域的集裝箱量小于K2區域需箱港口實際需求量，但是K2區域多箱港口調運能夠滿足K2區域需箱港口的需要，K2需箱港口不需要租箱。將上述兩個階段的五種情況進行組合得出表1中的六種情況（case）。

本文利用CPLEX12.6求解數學模型，運行環境為win7 64位操作系統，Intel?CoreTM2 i5-2400 CPU，3.1 GHz，4 GB內存。經過實驗表明，該算法的運行時間是秒級的，故而本文沒有進行時間復雜度分析。

4.1 與傳統的港口-港口模型對比（ECR-TM）

表1 兩階段供需關系情況細分圖

基于表1的六種情況，將文中提出的ECR-RDM與ECR-TM進行了比較，在兩個模型中，每個港口需箱量和多箱量、經t周期時間變化后每個港口多箱量或需箱量、每個港口存儲成本、租箱成本、裝載成本、卸載成本、港口間的運輸費用、調運數量等數據均相同，實驗結果如表2所示。

表2 跨區域動態空箱調運優化模型與傳統港口-港口空箱調運優化模型各成本對比表

容易發現，ECR-RDM總營運成本明顯低于ECR-TM，成本相差最大的是Case 4，大約節省29.3%的成本，成本相差最小的是Case 5，節省成本約11%。從租箱數量看，ECR-RDM的優勢明顯優于ECR-TM，其中對于Case 1兩者差距最大，ECR-TM租箱數量占調運數量的20%，而ECR-RDM則無需租箱。這在一定程度上說明ECR-RDM可以加快航運公司自有空箱的周轉率。在Case 5中，K2區域港口需箱港口總需箱量為2 509 TEU，從K1區域調運為1 904 TEU，K2區域多箱港口調運為180 TEU，租箱量為425 TEU，調運成本為75 434，租箱成本為25 500，在不考慮存儲成本和季節變化的情況下，平均每個TEU租箱成本是調運成本的1.67倍，如果考慮存儲成本和季節變化因素，租箱成本將是調運成本的2倍以上，因為在多箱港口由于存儲倉庫屬于緊缺資源，一般存儲費用比較高。而且在需箱高峰季節，比如圣誕節之前月份，東南亞很多出口為主的港口需箱量比較大，導致空集裝箱成為緊缺資源，租箱成本也會大幅上漲。

通過對兩模型六個情況比較，總結ECR-RDM優于ECR-TM的方面：

（1）ECR-RDM是基于港口集合-港口集合的，而ECR-TM是港口點-港口點模型，由于遠洋航線周期比較長，計劃調運開始到計劃實施結束周期較長，港口用箱情況變化波動較大，ECR-RDM中港口集合內部會相互消除一些變化，導致總成本開銷要比ECR-TM節省。

（2）ECR-RDM是調運開始時只確定調往區域，不確定調往的具體港口，到了目標區域后，再根據目標區域的用箱情況優化分配空箱，這樣優化比ECR-TM更加貼合實際業務中用箱需求，調運計劃更加高效，從表2可以看出，ECR-RDM減少很多租箱，從而使得租箱費用大大降低。

4.2 費用組成分析

表3中列舉了ECR-RDM方法中各項成本在總成本中的權重，其中每一行代表表1中的一個case，列表示某項成本在這個case中總成本所占的比例。

表3 ECR-RDM各項成本在集裝箱調運總成本所占比例 %

實驗表明，在總成本中，所占比例最大是裝卸成本，通常要達到總成本的50%，甚至高達65%，如case 4。其中，case 2和case 5除外，因為這兩者空箱調運不足，要在需箱港口租借一些空集裝箱，由于單位租箱成本較高，從而導致總租箱成本在總成本中所占比例達到25%左右。

此外，從表3可以看出，利用跨區域動態空箱調運策略已經使得運輸成本和租箱成本達到最優，如果想進一步降低成本開銷，可以從以下兩方面出發：一是盡量減少裝卸次數，即減少轉運次數，在文中提出的模型中限制轉運最多一次。二是從成本優化的角度，在滿足業務需求的條件下，盡量在裝卸成本較低的港口進行相應操作。對于case 1、case 2和case 3，他們的第一階段情況相同，而第二階段分為了三種不同情況，對比三個case發現運輸成本與裝卸成本成正比關系，運輸費用、裝載費用和卸載費用在總成本中的比例差距不大，最大不到5%。

5 結束語

班輪公司提高自有空箱周轉率，減少短期租箱，對提高公司競爭力起著居住輕重的作用。本文主要在操作層面上提出了一個跨區域遠洋航線空集裝箱動態調運優化模型：ECR-RDM，并且對各種實際業務中可能發生的六種情況進行了實驗和數據分析，而且將實驗結果和傳統的港口-港口的調運模型：ECR-TM進行了比較，結果顯示ECR-RDM能夠節省調運總成本11%~20%，大大減少了租箱。在實驗中，通過分析ECR-RDM中各項成本在空箱調運總成本中所占的比例，發現在空箱相對寬裕的情況下，存儲成本和租箱成本在總成本中所占的比例很小，而裝載成本、卸載成本和運輸成本各占總成本的1/3左右。但是在空箱緊缺的情況下，租箱成本要占總成本的1/4，如果需箱數量持續增加，租箱成本所占的比例也會相應增加。通過對這些數據進行分析，其結果可以為班輪公司在制定公司經營策略上提供決策支持。

[1]UNCTAD.Review of maritime transport[Z].United Nations Publication，2013.

[2]Li J A，Liu K，Leung S C H，et al.Empty container management in aport with long-run averagecriterion[J].Mathematical and Computer Modelling，2004，40（1/2）：85-100.

[3]Song D P.Characterizing optimal empty container reposition policy in periodic-review shuttle service systems[J].Journal of the Operational Research Society，2007，58（1）：122-133.

[4]Song D P，Earl C F.Optimal empty vehicle repositioning and fleeting-sizing for two-depot service systems[J].European Journal of Operational Research，2008，185（2）：760-777.

[5]Shintani K，Imai A，Nishimura E，et al.The container shipping network design problem with empty container repositioning[J].Transportation Research Part E，2007，43（1）：39-59.

[6]Liu X，Ye H Q，Yuan X M.A tactical planning model for liner shipping companies：managing container flow and ship deployment jointly[R].School of Business，National University of Singapore，2007.

[7]Erera A L，Morales J C，Savelsbergh M.Robust optimization for empty repositioning problems[J].Operations Research，2009，57（2）：468-483.

[8]施欣.集裝箱海運空箱調度優化分析[J].系統工程理論與實踐，2003，23（4）：70-75.

[9]Cheung R K，Chen C A.Two-stage stochastic network model and solution methods for the dynamic empty container allocation problem[J].Transportation Science，1998，32（2）：142-162.

[10]Lam S W，Lee L H，Tang L C.An approximate dynamic programming approach for the empty container allocation problem[J].Transportation Research Part C，2007，15（4）：265-277.

[11]Meng Qiang，Wang Shuaiai.Liner shipping service network design with empty container repositioning[J].Transportation Research Part E：Logistics and Transportation Review，2011，47（5）：695-708.

[12]Crainic T G，Gendreau M，Dejax P.Dynamic and stochastic models for the allocation of empty containers[J].Operations Research，1993，41（1）：102-126.

[13]石玉峰.戰時隨機調運時間路徑優化研究[J].系統工程理論與實踐，2005，25（4）：133-136.

[14]Song Dongping，Dong Jingxin.Long-haul liner service route design with ship deployment and empty container repositioning[J].Transportation Research PartB，2013，55：188-211.

[15]Yin Long，Loo Hay Lee，Ek Peng Chew.The sample averageapproximation method forempty container repositioning with uncertainties[J].European Journal of Operational Research，2012，222（1）：65-75.

[16]Song Dongping，Dong Jingxin.Cargo routing and empty container repositioning in multiple shipping service routes[J].Transportation Research Part B，2012，46（10）：1556-1575.

[17]Meng Qiang，Wang Shuaian，Andersson H，et al.Containership routing and scheduling in liner shipping：overview and future research directions[J].Transportation Science，2014，48（2）：265-280.