班輪航線設(shè)計(jì)與空箱調(diào)運(yùn)研究:箱種代用

張芳軍，鄭建風(fēng)，任華玲*

(1.北京交通大學(xué)交通運(yùn)輸學(xué)院系統(tǒng)科學(xué)所，北京100044;2.北京交通大學(xué)城市交通復(fù)雜系統(tǒng)理論與技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京100044)

海洋運(yùn)輸(簡稱海運(yùn))是國際貿(mào)易中一個(gè)最主要的運(yùn)輸模式，其年貿(mào)易量高于80億噸，占據(jù)世界貿(mào)易總量的65% ～85%［1］。隨著貨物集裝箱化運(yùn)輸?shù)娘w速發(fā)展，班輪運(yùn)輸已經(jīng)成為海運(yùn)中最重要的運(yùn)輸模式，而班輪航線網(wǎng)絡(luò)設(shè)計(jì)問題和空集裝箱運(yùn)輸問題也就成為了海運(yùn)相關(guān)研究問題中的兩個(gè)重要課題。如何優(yōu)化設(shè)計(jì)班輪航線、確定空集裝箱的起終點(diǎn)，以及如何運(yùn)輸重箱與空箱，將直接影響班輪公司的運(yùn)輸成本。

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

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

在最近的研究中，有研究學(xué)者同時(shí)考慮班輪航線網(wǎng)絡(luò)設(shè)計(jì)問題和空箱調(diào)運(yùn)問題。Shintani等［21］提出一個(gè)兩階段模型來研究組合的班輪航線網(wǎng)絡(luò)設(shè)計(jì)問題和空箱調(diào)運(yùn)問題，并提出一個(gè)遺傳算法來求解該問題?；谝粋€(gè)備選的班輪航線集合，Meng等［22］提出一個(gè)混合整數(shù)規(guī)劃模型來求解班輪航線最優(yōu)挑選和空箱分配。Song等［23］提出了一個(gè)長途班輪航線設(shè)計(jì)問題，主要包含航線設(shè)計(jì)、船隊(duì)分配和空箱調(diào)運(yùn)，并提出了一個(gè)三階段的優(yōu)化方法來解決此問題，以達(dá)到班輪運(yùn)輸成本極小化的目標(biāo)。

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

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

本文在綜合研究班輪航線設(shè)計(jì)和空箱調(diào)運(yùn)的基礎(chǔ)上，探討各港口內(nèi)部以及港口之間，不同箱種之間的最優(yōu)代用。從定量的角度，分析了箱種代用對班輪航線設(shè)計(jì)和空箱調(diào)運(yùn)問題的影響。

1 問題描述和參數(shù)說明

1.1 航線與船型

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

其中，pri表示航線r∈R上訪問的第i個(gè)港口，Nr表示航線r∈R上的港口數(shù)量。很明顯，一條航線形成一個(gè)閉合的環(huán)。為了更好地標(biāo)記航線上訪問的港口，引入函數(shù)

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

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

1.2 費(fèi)用和時(shí)間參數(shù)描述

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

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

1.3 集裝箱運(yùn)輸與箱種代運(yùn)

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

為了描述集裝箱的路徑，借鑒文獻(xiàn)［13］中有關(guān)一條航線上的航段(Segment)的概念。令S={＜k，l＞}為既服務(wù)于港口k，又服務(wù)于港口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型空箱，且有

為了描述箱種代用問題，我們引入?yún)?shù)λa(a∈A)表示a∈A型空箱的代用能力。

2 混合整數(shù)規(guī)劃模型

2.1 模型的假設(shè)條件

通過參考班輪運(yùn)輸?shù)膶?shí)際運(yùn)營過程，本文作如下3個(gè)假設(shè):

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

(2)重箱只能在其樞紐港進(jìn)行中轉(zhuǎn);

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

2.2 決策變量

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

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

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

2.3 數(shù)學(xué)模型

針對本文研究的問題，本節(jié)建立如下的混合整數(shù)線性規(guī)劃模型

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

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

3 算例分析

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

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

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

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

表1 各種船型及其相關(guān)參數(shù)Table 1 Various ship types and their related parameters

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

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

4 結(jié)語

通過引入多種類型集裝箱，本文研究了考慮箱種代用條件下的班輪航線網(wǎng)絡(luò)設(shè)計(jì)和空箱調(diào)運(yùn)問題。為了求解這個(gè)問題，我們提出了一個(gè)混合整數(shù)線性規(guī)劃模型。該模型可以通過CPLEX等常用的數(shù)學(xué)規(guī)劃軟件進(jìn)行有效的求解。最后，通過亞洲－歐洲－大洋洲航線網(wǎng)絡(luò)上集裝箱運(yùn)輸?shù)那闆r，對我們提出的模型進(jìn)行了驗(yàn)證，并分析了空箱中轉(zhuǎn)和箱種代用的情況。研究表明，通過箱種代用的手段，可以有效降低班輪公司的運(yùn)輸成本。

下面兩個(gè)方面需要我們未來進(jìn)一步地研究:

(1)本文假設(shè)班輪航線的候選集合，如何有效地產(chǎn)生合理的班輪航線網(wǎng)絡(luò)是一個(gè)很重要的研究課題;

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

［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，F(xiàn)ARNSWORTH 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.