班輪航線設計與空箱調運研究:箱種代用

張芳軍，鄭建風，任華玲*

(1.北京交通大學交通運輸學院系統科學所，北京100044;2.北京交通大學城市交通復雜系統理論與技術教育部重點實驗室，北京100044)

海洋運輸(簡稱海運)是國際貿易中一個最主要的運輸模式，其年貿易量高于80億噸，占據世界貿易總量的65% ～85%［1］。隨著貨物集裝箱化運輸的飛速發展，班輪運輸已經成為海運中最重要的運輸模式，而班輪航線網絡設計問題和空集裝箱運輸問題也就成為了海運相關研究問題中的兩個重要課題。如何優化設計班輪航線、確定空集裝箱的起終點，以及如何運輸重箱與空箱，將直接影響班輪公司的運輸成本。

在以往的很多研究中，班輪航線網絡設計和空箱調運問題是兩個獨立的研究課題。班輪航線類似于城市交通中的公交線路，很多研究學者在班輪航線網絡設計問題方面做出了很多貢獻。Conley等［2］提出一個線性規劃模型來研究海外到美國內陸的貨物運輸，其中船隊包括了50艘不同類型的船。Lane等［3］研究了澳大利亞和北美西海岸之間的班輪航線設計問題，由于文中只考慮了6個港口，他們利用窮舉法來選擇和優化班輪航線。Rana等［4］討論了針對既定貿易航線的集裝箱班輪船隊配置問題，并假設航線運營者可以放棄那些無法帶來更高收益的貨運需求。Jaramillo等［5］使用了線性規劃方法來探討確定班輪船隊在若干已知航線上的優化配置問題，該模型的特點在于優化船隊配置的同時，還考慮了航線服務頻率(班期)的優化設置問題。Xie等［6］建立了一個考慮船舶折舊和船隊更新因素的中長期船隊規劃優化模型。Fagerholt［7－8］、Sambracos等［9］和Karlaftis等［10］研究了單樞紐或中心(Hub)的班輪航線網絡設計問題，即班輪從樞紐港口出發，訪問幾個其他港口，然后最終回到樞紐港口。該問題可以建模為一個車輛路徑問題(vehicle routing problem，VRP)。Imai等［11－12］研究兩個區域之間的班輪航線網絡設計問題，比較分析了輪輻結構(hub-andspoke)的運輸模式和multi-port-call運輸模式之間的差異。

隨著貨物集裝箱化，空箱調運問題是海運研究中的一個重要問題，同時也是一個研究熱點和難點問題之一。空箱調運問題是由于各個地區的進出口貿易量的不平衡導致的。據統計，2009年亞歐的進出口貿易量［1］從亞洲到歐洲是1.15億TEUs(twenty-foot equivalent units)，而相反方向是0.55億TEUs，從而在亞洲積累了大量的空箱。很明顯，一些地區有很多剩余的空箱，而有些地區卻是欠缺空箱來裝貨和運貨。關于空箱調運問題研究課題中的一個重要難點是，把哪些地區的剩余空箱運輸到哪些欠缺空箱的地方。Crainic等［13－15］把空箱調運問題轉化為一個具有能力限制的多商品流選址問題，并提出了一些精確和啟發式的求解算法，包括分支定界，禁忌搜索等。Choong等［16］研究空箱租賃時間(短期或長期租賃)對空箱管理的影響，提出一個整數規劃模型。Lam等［17］提出一個近似動態規劃的方法來研究空箱調運問題。Dong等［18］研究班輪運輸系統中船隊大小和空箱調運問題，提出一個基于模擬的優化工具。Song等［19］研究班輪航線上的空箱調運，提出了兩種運輸策略。最近，Moon等［20］研究可折疊的集裝箱和普通集裝箱對空箱調運的影響。

在最近的研究中，有研究學者同時考慮班輪航線網絡設計問題和空箱調運問題。Shintani等［21］提出一個兩階段模型來研究組合的班輪航線網絡設計問題和空箱調運問題，并提出一個遺傳算法來求解該問題?；谝粋€備選的班輪航線集合，Meng等［22］提出一個混合整數規劃模型來求解班輪航線最優挑選和空箱分配。Song等［23］提出了一個長途班輪航線設計問題，主要包含航線設計、船隊分配和空箱調運，并提出了一個三階段的優化方法來解決此問題，以達到班輪運輸成本極小化的目標。

在現實的集裝箱運輸中，由于對各種類貨物的運輸需求，班輪公司經常會使用多種類型集裝箱，從而使得空箱也會存在多種不同的類型。在以往的相關研究中，基本不考慮多類型集裝箱的影響。為了適應裝載不同種類的貨物，出現了許多不同類型的集裝箱，例如雜貨集裝箱、敞頂集裝箱、冷藏集裝箱、散貨集裝箱和罐式集裝箱等。另外，各種類的集裝箱的尺寸也有不同類型，例如20英尺箱(TEU)、40英尺箱(FEU)等。在本文，我們主要考慮集裝箱的尺寸不同對班輪航線設計和空箱調運問題的影響。

假如不同尺寸的空箱是可以相互代用的話，即箱種代用，必然可以大大降低空箱調運量和空箱調運成本。另外，需要指出的是，通用集裝箱(例如雜貨集裝箱)與特種箱或專用集裝箱(例如罐式集裝箱、冷藏集裝箱)之間一般是不能代用的。然而，不同尺寸的通用集裝箱(或專用集裝箱)之間顯然是可以代用的。對于任何一個港口，不同尺寸的集裝箱的裝卸費用和裝卸時間一般都是不同的。當一個港口存在不同尺寸的空箱可供調運時，選擇什么尺寸的空箱調運到什么港口，是一個亟待解決的問題。本論文從減少總費用的角度，來探討和確定各個港口是大箱代替小箱，還是小箱代替大箱，從而可有效減少班輪公司的運輸成本。

本文在綜合研究班輪航線設計和空箱調運的基礎上，探討各港口內部以及港口之間，不同箱種之間的最優代用。從定量的角度，分析了箱種代用對班輪航線設計和空箱調運問題的影響。

1 問題描述和參數說明

1.1 航線與船型

令港口集合為P。班輪公司分配船舶訪問一些港口，形成一條班輪航線。令所有可行的航線集合為R。一般地，我們可以用船舶訪問港口的順序來描述一條航線r∈R，表示如下:

其中，pri表示航線r∈R上訪問的第i個港口，Nr表示航線r∈R上的港口數量。很明顯，一條航線形成一個閉合的環。為了更好地標記航線上訪問的港口，引入函數

其中 mod 表示求余，即當 i=1，2，…，N 時，I(i，Nr)=i;當 i=Nr+1 時，I(Nr+1，Nr)=1。另外，根據實際運營的航線，一個港口也有可能被一個航線訪問很多次。為方便標識訪問的港口，引入Irp表示航線r∈R上的港口p∈P被訪問的位置集合，則有Irp={i|pri=p，i=1，…，Nr}。

一般地，一個班輪公司都擁有不同類型的船舶，令其船舶類型的集合為V。不同的船舶類型，其船速、最大裝載能力和運營費用均不同。對于一條航線r∈R來說，由于受到港口吃水能力等的限制，并不是所有種類的船舶可以被隨意配置的。我們假設在航線r∈R上可配置的船舶類型集合為Vr。根據現實生活中班輪運輸運營現狀，不失一般性，本文假設對于任意一條航線上船舶的發船頻率是按周服務的(weekly service frequency)。

1.2 費用和時間參數描述

令集裝箱類型的集合為A。對于任意一條航線r∈R，假設配船v∈Vr。為簡化模型，在不考慮進港托運時間、出港領航時間等相關時間的前提下，那么船舶在這個航線上運營的時間主要包括兩個部分:(1)海上航行時間，記為τsearv(小時)，這個與航線的總距離和船型v∈Vr的航速相關;(2)航線上所有港口的集裝箱裝卸時間，這個與港口的裝卸效率和集裝箱數量相關，令tp，avr(小時)為在航線r∈R上的港口P處理一個船舶v∈Vr所裝載的a∈A型集裝箱所花費的時間。

對于任意一條航線r∈R，假設配船v∈Vr。那么對這個航線上運營的周費用主要可以分為三類:(1)船舶v∈Vr的周固定運營費用，記為cfixv(US$/week)，主要包括船舶造價的貸款、船舶的保險、船舶的維護維修的船員工資等;(2)船舶v∈Vr的油耗，令船舶v∈Vr在航行過程中每小時的油費為cbunkerv(US$/小時);(3)港口的集裝箱裝卸費用，港口的集裝箱裝卸費用與港口裝卸的集裝箱數量和單個集裝箱的裝卸費用相關。令cap(US$)為在港口P處理一個a∈A型集裝箱的費用。

1.3 集裝箱運輸與箱種代運

對于任意給定的集裝箱運輸需求，令naod為從港口o∈P到港口d∈P每周需要運輸的a∈A型集裝箱數量，即O-D(origin-destination)對(o，d)之間的集裝箱需求量?；诤骄€集合，集裝箱完成從起點到終點的運輸，形成一個集裝箱的路徑。集裝箱的路徑可能由若干條航線組成，不同航線之間通過共同的樞紐港進行中轉。

為了描述集裝箱的路徑，借鑒文獻［13］中有關一條航線上的航段(Segment)的概念。令S={＜k，l＞}為既服務于港口k，又服務于港口l的所有航線上的航段集合，且令Sr為航線r∈R上的所有航段集合?；谒锌尚械陌噍喓骄€集合R，令Hod(R)為O-D對(o，d)之間所有可行的路徑集合。Hklod(R)則表示O-D對(o，d)之間所有可行的路徑，并包含航段 ＜k，l＞，且Hklod(R)∈Hod(R)。

為了描述港口p∈P的空箱情況，定義nec，ap為在港口p∈P所剩余的a∈A型空箱，且有

為了描述箱種代用問題，我們引入參數λa(a∈A)表示a∈A型空箱的代用能力。

2 混合整數規劃模型

2.1 模型的假設條件

通過參考班輪運輸的實際運營過程，本文作如下3個假設:

(1)重箱被中轉不能超過2次;

(2)重箱只能在其樞紐港進行中轉;

(3)任意兩個樞紐港之間的集裝箱運輸只能是直航運輸。

2.2 決策變量

在前面所述基礎上，我們定義的決策變量有:

ξrv:為0或1變量，如果給航線r∈R分配船型v∈Vr時為1，否則為0。

mrv:為滿足每周的服務頻率，在航線r∈R上配置的v∈Vr型船的數量。

2.3 數學模型

針對本文研究的問題，本節建立如下的混合整數線性規劃模型

其中，Rp表示服務于港口p∈P的所有航線集合。Rkl表示包含航段 ＜k，l＞的所有航線集合。δklri的取值是0或1，在航線r∈R上，若航段 ＜k，l＞∈Sr包含此航線上的兩個相鄰港口Pri和PrI(i+1，Nr)時為1，否則為0。Capv表示v∈Vr型船的最大裝載能力。

公式(4)為目標函數，即極小化運營費用，由三部分組成，第一部分為運營上的固定費用和燃油費;第二部分為港口重箱處理費用;第三部分為港口空箱處理費用。公式(5)表示需求守恒約束。公式(6)表示航段流與路徑流的關系。公式(7)表示空箱調運平衡約束，以及空箱之間的箱種代用關系。公式(8)說明空箱流守恒約束。公式(9)為船舶運輸能力約束。本文假設為周服務頻率，公式(10)是周服務頻率的一個約束，其中168表示1周的小時數。公式(11)是對配船數量和是否配船的關系約束，其中M表示一個很大的數。公式(12)～(16)均為非負數變量約束。公式(17)為對非負整數變量的一個約束。公式(18)是對0或1變量的一個約束。

3 算例分析

在數值分析中，我們考慮亞洲－歐洲－大洋洲航線網絡上一些典型的港口，如圖1所示。對于船舶的類型，本文考慮3種不同的船型，與船型相關的一些參數如表1所示。針對集裝箱的類型，本文側重考慮2種:20英尺箱(TEU)和40英尺箱(FEU)。很明顯，在空箱調運中，我們可以假設一個40英尺空箱可以代替兩個20英尺空箱。在占用船舶空間(或容量)上，一個40英尺箱類似于兩個20英尺箱。對于求解模型(4)～(18)所需的O-D集裝箱需求量，是由一個國際班輪公司提供的。為了安全和保密起見，本文對這個O-D集裝箱需求量進行了一定的修改，并且20英尺箱和40英尺箱的比例是隨機給出的。為了給出合理的班輪航線集合，可以參考各大國際班輪公司(例如美國總統班輪、馬士基班輪等)的網站。

圖1 亞洲－歐洲－大洋洲航線網絡上一些典型的港口Fig.1 Some typical ports in Asia-Europe-Oceania shipping network

為了探討引入箱種代用的影響效果，我們同樣也考慮不同箱種不能代用的情況。很顯然，如果不同箱種不能代用，那么我們應將約束條件(7)進行如下修改:

公式(19)表明，對于各種類型的空集裝箱都得滿足空箱調運平衡。

表1 各種船型及其相關參數Table 1 Various ship types and their related parameters

表2 兩種情況的結果比較Table 2 Results comparison between two cases

從表2中可以看出，通過箱種代用的手段，每周在班輪運營和集裝箱運輸方面的總費用可以降低大約2.7%，即0.19×106美元。通過實際裝或卸的空箱量可以看出，當箱種不代用時，20英尺空箱和40英尺空箱都需要完成調運和裝卸，從而滿足約束條件(19);當箱種可以代用時，實際完成裝卸任務的只有40英尺空箱，那是因為1個40英尺空箱的裝卸時間和費用一般要小于2個20英尺空箱的裝卸時間和費用。對于一些港口，由于裝卸機械的影響，當1個40英尺空箱的裝卸時間和費用大于或等于2個20英尺空箱的裝卸時間和費用時，很顯然我們可以得到不一樣的結果，在本文沒有一一列出。另外，表2中也給出了發生中轉的空箱數量，可以發現，兩種情況下需要中轉的空箱量相當。通過裝(卸)空箱總量、實際裝(卸)的空箱量和中轉空箱量的數據可以看出，當箱種不代用時，中轉空箱量都是通過一次中轉完成運輸的。從箱種代用的比例44.7%可知，發生箱種代用的空箱數量是很大的。另外，當箱種可代用時，發生虛擬裝卸的空箱量是201TEUs，這個數沒有在表2中列出，但是這個數已經包含在箱種代用裝卸空箱量里面。

4 結語

通過引入多種類型集裝箱，本文研究了考慮箱種代用條件下的班輪航線網絡設計和空箱調運問題。為了求解這個問題，我們提出了一個混合整數線性規劃模型。該模型可以通過CPLEX等常用的數學規劃軟件進行有效的求解。最后，通過亞洲－歐洲－大洋洲航線網絡上集裝箱運輸的情況，對我們提出的模型進行了驗證，并分析了空箱中轉和箱種代用的情況。研究表明，通過箱種代用的手段，可以有效降低班輪公司的運輸成本。

下面兩個方面需要我們未來進一步地研究:

(1)本文假設班輪航線的候選集合，如何有效地產生合理的班輪航線網絡是一個很重要的研究課題;

(2)一般來說，集裝箱需求是不確定的，具有一定的波動性。研究集裝箱需求不確定性下的班輪航線網絡優化、船型分配和空箱調運問題具有更加重要的意義。

［1］UNCTAD.Review of Maritime Transportation 2010［EB/OL］.［2013 －11 －03］.http://www.unctad.org/en/docs/rmt2010_en.pdf.

［2］CONLEY J H，FARNSWORTH R S，KOENIGSBERG E，et al.A linear programming approach to the total movement of a homogeneous product［J］.Transportation Science，1968，2:289 －302.

［3］LANE D E，HEAVER T D，Uyeno D.Planning and scheduling for efficiency in liner shipping［J］.Maritime Policy and Management，1987，14(2):109 －125.

［4］RANA K，VICKSON R G.Routing container ships using Lagrangean relaxation and decomposition［J］.Transportation Science，1991，25(3):201－214.

［5］JARAMILLO D I，PERAKIS A N.Fleet deployment optimization for liner shipping Part 2:Implementation and results［J］.Maritime Policy and Management，1991，18(4):235－262.

［6］XIE X L，WANG T F，CHEN D S.A dynamic model and algorithm for fleet planning［J］.Maritime Policy and Management，2000，27(1):53－63.

［7］FAGERHOLT K.Optimal fleet design in a ship routing problem［J］.International Transactions in Operational Research，1999，6(5):453－464.

［8］FAGERHOLT K.Designing optimal routes in a liner shipping problem［J］.Maritime Policy and Management，2004，31(4):259－268.

［9］SAMBRACOS E，PARAVANTIS J A，TARANTILIS C D，et al.Dispatching of small containers via coastal freight liners:The case of the Aegean Sea［J］.European Journal of Operational Research，2004，152:365 －381.

［10］KARLAFTIS M G，KEPAPTSOGLOU K，SAMBRACOS E.Containership routing with time deadlines and simultaneous deliveries and pick －ups［J］.Transportation Research Part E，2009，45(1):210 －221.

［11］IMAI A，NISHIMURA E，PAPADIMITRIOU S，et al.The economic viability of container mega-ships［J］.Transportation Research Part E，2006，42(1):21－41.

［12］IMAI A，SHINTANI K，PAPADIMITRIOU S.Multi-port vs Hub-and-Spoke port calls by containerships［J］.Transportation Research Part E，2009，45(5):740－757.

［13］CRAINIC T G，DEJAX P，DELORME L.Models for multimode multicommodity location problems with interdepot balancing requirements［J］.Annals of Operations Research，1989，18(1):279 － 302.

［14］CRAINIC T G，GENDREAU M，SORIANO P，et al.A Tabu search procedure for multicommodity location/allocation with balancing requirements［J］.Annals of Operations Research，1993，41(4):359 － 383.

［15］CRAINIC T G，GENDREAU M，Dejax P.Dynamic and stochastic models for the allocation of empty containers［J］.Operations Research，1993，41(13):102 －126.

［16］CHOONG S T，COLE M H，Kutanoglu E.Empty container management for intermodal transportation networks［J］.Transportation Research Part E，2002，38(6):423 －438.

［17］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.

［18］DONG J X，SONG D P.Container fleet sizing and empty repositioning in liner shipping systems［J］.Transportation Research Part E，2009，45:860 －877.

［19］SONG D P，DONG J X.Flow balancing － based empty container repositioning in typical shipping service routes［J］.Maritimes Economics and Logistics，2011，13(17):61 －77.

［20］MOON I，NGOC A-D D，Konings R.Foldable and standard containers in empty container repositioning［J］.Transportation Research Part E，2013，49(1):107 －124.

［21］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:39－59.

［22］MENG Q，WANG S.Liner shipping service network design with empty container repositioning［J］.Transportation Research Part E，2011，47(5):695－708.

［23］SONG D P，DONG J X.Long-haul liner service route design with ship deployment and empty container repositioning ［J］.Transportation Research Part B，2013，55:188－211.