考慮空箱調運的遠洋班輪航線優(yōu)化

李 建，韓曉龍

(上海海事大學科學研究院， 上海201306)

?

考慮空箱調運的遠洋班輪航線優(yōu)化

李 建，韓曉龍

(上海海事大學科學研究院， 上海201306)

全球集裝箱運輸市場持續(xù)低迷環(huán)境下，各大航運公司不得不采取各種手段來控制成本，提高經營效益。為設計更加合理的運輸航線以節(jié)省班輪公司運營成本，從班輪公司的角度出發(fā)，以新的角度來選擇航線，考慮空箱調運對于航線成本的影響，建立以每周運營總成本最小化為目標的班輪航線優(yōu)化模型，設計了有效的啟發(fā)式算法來解決空箱調運問題；通過在不同地區(qū)設置不同數量的二次掛靠港，計算總成本選出最小的航線結構。并通過美西南航線的案例分析表明，當設置一個位于北美的港口作為二次掛靠港時，可以使得班輪公司周運營成本降低2.52%。說明考慮了空箱調運的遠洋班輪航線的優(yōu)化可為班輪公司節(jié)省可觀的運營成本。

集裝箱；航線；空箱；啟發(fā)式算法

0 引 言

航線設計問題屬于集裝箱班輪公司的戰(zhàn)略問題，班輪公司的所有運輸配置等方案都是基于已有航線進行的。航線的合理性對班輪公司的成本及收益具有至關重要的影響。

因此，近年來關于航線設計相關的研究較多，如：Baird[1]就航線設計問題和班輪班期的設置建立了多目標模型，確定了運輸成本以及庫存持有成本的函數關系；Bronmo等[2]針對傳統的航線網絡，采用啟發(fā)式算法進行求解，建立“中心-分支”結構模型；Hsu等[3]針對軸輻式航線網絡，建立了以運營成本和庫存成本為最小的的雙目標模型，研究直運和轉運問題，求解出最佳航線和相應的船型配置、發(fā)船頻次；Yan等[4]針對集裝箱轉運方案和短期的船舶調度問題，利用拉格朗日松弛、次梯度方法等求解，采用網絡流技術建立了相關模型；Agarwal等[5]針對港口掛靠順序和船隊規(guī)模優(yōu)化問題，采用時間拓撲理論，建立了相關模型；Imai等[6]針對班輪公司，基于環(huán)繞式和單擺式混合結構設計航線，雖考慮了空箱運輸問題，但并未考慮重箱的運輸；Kosmas等[7]利用模擬退火算法對航線運營成本問題進行求解，采用統計學方法對結果進行探討，并將研究散貨和郵輪運輸的思想運用到航線設計中來；郭子堅等[8]針對空重箱的混合運輸問題，建立了海運網絡優(yōu)化模型，優(yōu)化了航線結構、空箱調運方案、班輪服務頻次及船舶配置等問題；計明軍等[9]研究了軸輻式集裝箱運輸網絡，建立了基于混合整數規(guī)劃的支線集裝箱運輸模型，同時在模型中考慮了船舶裝載量和船舶在樞紐港的停泊時間等限制因素；陳康等[10]針對混合型航線結構，采取遺傳算法進行求解，并建立了優(yōu)化航線和空重箱運輸方案的雙層規(guī)劃模型。

由于國際貿易的不平衡，空箱調運成為航運公司不可避免的非生產性經營活動，并在整個運輸成本中占有較高的比重。因此，國內外學者針對空箱調運問題進行了大量研究。如：Moon[11]為了減少各港口集裝箱不平衡的問題，優(yōu)化了空箱的分配，研究的目標是極小化以裝卸成本、運輸成本和持有成本為代表的總成本；Song等[12]研究目的港不確定情況下的空箱流動方向，并采用仿真的技術對空箱調運方案進行評價以論證其有效性；楊洋[13]研究在多式聯運下，運輸過程中相關的班輪公司將空箱無償提供給各方使用，前提是保證重箱的運輸，從而一方面保證空箱的需求，另一方面也優(yōu)化了總成本；韓曉龍等[14]研究了航運公司在新開發(fā)港口的集裝箱空箱的分配問題，并通過分析發(fā)現在融資能力允許的情況下，自購箱是航運公司第一首選，但結合現實情況，自購箱和租箱混合才是基本策略。

可以發(fā)現，在以往的航線設計相關研究中，班輪航線優(yōu)化通常從班期設置、船舶配置、樞紐港選擇等方面著手；主要考慮樞紐港的選擇、港口掛靠順序、船舶的配置等問題，較少考慮空箱調運因素，但由于空箱調運成本在整個集裝箱運輸中占據了超過20%的成本，因此考慮了合理的空箱調運策略的航線設計能夠為班輪公司節(jié)省巨大的成本，具有十分實際的應用價值。本文在優(yōu)化船舶數量和配置的同時，將空箱調運對航線的影響考慮進來，在不同的空箱調運策略下選擇出合適的回程掛靠港。

1 問題描述

一條遠洋航線可以被看作包括了兩個末端港口，即首端港和尾端港，這就包含了兩個方向的港口序列。港口掛靠順序從首端港至尾端港方向，稱之為出境航向，反之則是入境航向?？梢约僭O：若有兩個港口在出入境航向中都作為掛靠港，則兩者在兩次航行的掛靠方向正好相反，且稱此類港口為“二次掛靠港”。圖1中包含兩個二次掛靠港，它們將整個航線分為了3個閉環(huán)。

本文研究的問題是從班輪運輸公司的角度考慮設計一條遠洋運輸航線，目標是服務于兩個不同洲的多個港口，港口的集合用Ω表示，用|Ω|示集合內的元素個數。從給定的港口集合中，根據最短路徑原則及各港口之間的的運輸需求，確定合適的空箱調運策略，并設計有效的啟發(fā)式算法來調配空箱，選出最優(yōu)二次掛靠港，設計出使得每周的運營總成本最小的航線。

圖1 航線運輸結構圖

2 模型建立

假設班輪運輸的成本組成包括：船舶固定成本、燃料成本、港口掛靠費、裝卸費、空重箱持有成本。這里需要指出的是，不同的空箱調運策略其影響并非僅僅表現在某一方面，它對整個航線中的各個環(huán)節(jié)都是有影響的。不同策略使得港口內集裝箱裝卸成本、在港?？繒r間、空重箱運輸時間等都會有所不同。在建立模型時，雖然其中并不會明確寫有空箱調運成本這一項，但是在計算其中的每一項成本時，都需要建立在既有空箱調運策略的基礎上。根據所假設的班輪運輸成本組成建立如下班輪公司每周運營總成本函數見式(1)：

(1)

(2)

(3)

xij≥0,

(4)

其中:n為航線內配置的船舶數量，Cv為每艘船舶的日固定成本，Cf為單位燃料成本，Fs為一艘船舶海上每日燃料消耗量，Cp為港口固定掛靠費用，Ch為每標箱裝卸費用，ts為每周海上航行總時間，tp為每周在港總時間，xij為港口間每周空箱運輸量，yij為港口間每周重箱運輸量，tij為港口間運輸時間，CLI/CEI為單位重箱/空箱每日持有成本，p(i)為掛靠序號為i的港口，N為掛靠港口總次數，θv為船舶運力；決策變量為n，xij，θv。

在式(1)的右邊，第一項表示船舶每周固定成本，第二項表示每周燃料成本，第三項表示每周港口固定掛靠成本，第四項表示每周集裝箱裝卸總成本，第五項表示重箱每周平均持有成本，第六項表示空箱每周平均持有成本。約束方程(2)保證了各港口集裝箱輸入、輸出量平衡，約束方程(3)表示任意航段內集裝箱裝載量不超過船舶運力，約束方程(4)表示任意航段內空箱運輸量為非負。

3 模型求解

在所建立的目標函數中，決策變量為n，xij，θv。該模型的求解思路是先根據最短路徑原則和應用實際確定可能的航線結構，然后根據各港之間的需求確定相應結構下所選船舶船型θv及空箱調運策略xij，在此基礎上，根據航行和在港時間，為保證每周一班的運輸頻次從而決定航線內應配置的船舶數量n，最后便是計算各航線結構對應的總成本，選擇使得每周運營總成本最小的航線結構。

在組成空箱調運的成本當中，占據比例最大的是在港口的集裝箱裝卸成本，這是因為空箱運輸一般都是利用班輪公司自有船舶的過剩運力來實現的。因此，在優(yōu)化空箱調運成本時，應將減少集裝箱裝卸次數作為優(yōu)先優(yōu)化的因素。

在某個航段中，若船上的重箱裝載率是整個航行途中最高的，則將該航段記為δ。若航線為多閉環(huán)航線結構，且空箱調運滿足每個港口的空重箱流量平衡，則有推論：每個閉環(huán)內不同航段的集裝箱總裝載量相同，不同閉環(huán)的航段集裝箱裝載總量不一定相等；空箱調運策略可以由每個港口的凈進口量來確定，且每個航段的集裝箱總裝載量等于重箱裝載量最大航段的重箱裝載量。為解決空箱調運問題，設計了有效的啟發(fā)式算法，為了敘述簡便，首先引入如下符號：

LVi(EVi):船舶由i港開往i+1港的過程中船上所裝載的重箱(空箱)量;

LUi(EUi):船舶在i港時卸下的重箱(空箱)量;

LLi(ELi):船舶在i港時裝運的重箱(空箱)量;

LFi(EFi):船舶由i港開往i+1港的過程中船上的重箱(空箱)裝載量;

TFi:船舶由i港開往i+1港的過程中船上集裝箱總的裝載量。

若p(j)是二次掛靠港，j則是其中的一次掛靠序號，我們將另外的一次掛靠序號表示為j′，那么則有：p(j)′=p(j),j≠j′.用TVj:=LVj+EVj表示船舶在航段j[即p(j)開往p(j+1)]航行過程中的集裝箱總量,EVj′表示船舶在航段j時裝載空箱數量的最小值；假設首端港在航線的最左端。

步驟1 先確定在未考慮空箱調運時的重箱相關數據：yij,LVj。

步驟2 基于LVj和輸入輸出量平衡來求出最小空箱流量：

①數據初始化：令EVj′=0；

②平衡任意港口p(j)集裝箱輸入輸出量：

若p(j)不是二次掛靠港，則EVj′=max{EVj′,LVj-1-LVj};

若p(j)是二次掛靠港，則平衡輸入和輸出p(j)的集裝箱量，即：航段j的空箱量[從p(j)運出至p(j+1)]，以及航段j′-1的空箱量[從p(j′-1)運進至p(j′)=p(j)]；

EVj=max{0,LVj′-1-LVj};EVj′-1′=max{EVj′-1′,LVj-LVj′-1}。

步驟3 基于LVj和EVj來求出每個閉環(huán)內的TVj(注意：除了兩端的閉環(huán)內均只有一個二次掛靠港以外，其他閉環(huán)內都含有兩個二次掛靠港)。

若某閉環(huán)內有兩個二次掛靠港p(j)和p(k),且j

若p(j)是最左端閉環(huán)內的二次掛靠港且j

若p(j)是最右端閉環(huán)內的二次掛靠港且j>j′,則：

TVj=max{LVm+EVm′|j≤m

步驟4 調整最小空箱運輸量值：對于任意j,EVj′=max{EVj′,TVj-LVj}。

步驟5 計算每個航段的實際空箱運輸量，從δ航段開始進行迭代,將所有二次掛靠港都標記為待處理港口：

①對于航段k=δ,設置EVδ=0,令k=k+1;

②令j=kmodn,使得0≤j

③若p(j)是非二次掛靠港，令EVj=LVj-1+EVj-1-LVj;

④若p(j)是待處理的二次掛靠港，則

首先計算出境航行時從p(j)運出的空箱量，即：EVj′=LVj-1+EVj-1-LVj′;

然后，根據其空箱的凈進口量或凈剩余量來確定EVj的值:

若p(j)是有空箱剩余的二次掛靠港，則:EVj=max{EVj′，EVj-1},這樣船就不會在p(j)時又卸下空箱;

若p(j)是空箱量不足的二次掛靠港，則:EVj=max{EVj′,EVj-1+NetImport};

最后，滿足船舶裝載能力約束：EVj=min{EVj,θv-LVj};

⑤將p(j)標記為已處理港口;

⑥令k=k+1若k<δ+N,執(zhí)行步驟5-② ;否則，執(zhí)行步驟6(此步驟確保了船舶運力滿足約束條件，在一個并沒有空箱需求量的二次掛靠港，依然會有卸下空箱的可能)。

步驟6 計算每個港口空箱的裝卸量，對于每個j，令ELj=max{0,EVj-EVj-1}且EUi=max{0,EVj-1-EVj}。

步驟7 求解具體空箱調運數據：

①從航段k=δ開始;

②令j=kmodn,使得0≤j

③令m=j+1;

④若ELj≤0,執(zhí)行步驟7-⑥；

⑤若EUm>0,xjm=min{ELi,EUm},ELi=ELi-xjm,EUm=EUm-xjm;m=m+1,執(zhí)行步驟7-④；

⑥k=k+1;若k<δ+N，執(zhí)行步驟7-②；否則，執(zhí)行步驟8。

步驟8 輸出{yij,xij}；結束。

以上算法的優(yōu)點表現在兩個方面：第一，在最小化空箱裝卸次數和空箱流量后即可直接得到最優(yōu)或接近最優(yōu)的調運策略；第二，該算法滿足約束(3)，運用時不用首先確定船舶數量和航速。

4 算例分析

以某班輪運輸公司經營的一條美西南航線為例，航線內共8個港口(其中亞洲5個，北美洲3個)，該航線目前的掛靠順序是：新加坡—香港—鹽田—寧波—上?！餮艌D—奧克蘭—長灘(—新加坡),無二次掛靠港。港口對間的距離以及需求量分別由表1及表2給出。

表1 港口對間的距離

表2 港口對間的每周需求量 標箱

假定同一地區(qū)/洲的港口之間沒有需求量,各港口空箱來源均只由系統內部港口提供(也就是保證每個港口的集裝箱輸入和輸出平衡),設定參數：各港口掛靠費相同，為平均2 000美元/次，船速為15 n mile/h，單位燃料費用600美元/噸，海上每日燃料消耗量為300噸，重箱持有成本25美元/d，空箱持有成本10美元/d，進港等待和離港時間均為2 h，裝卸效率各港相同，為200個/h，集裝箱裝卸費100美元/TEU。

當亞洲港口所有重箱均裝載完畢并開始運往北美時，航段內重箱運輸量達到最大值，為10 800 TEU，因此選定船舶船型θv=11 000 TEU, 設定一艘11 000 TEU型船舶的每日固定成本為25 000美元/d。使用MATLAB編程軟件進行計算，表3給出了相關計算結果。

表3中,λ,μ分別表示在北美洲和亞洲設定的二次掛靠港數量，因為亞洲和北美洲港口數量分別為5個和3個，同時首端港和尾端港又不會作為二次掛靠港，因此λ的可能值為0，1，2；μ的可能值為0，1，2，3，4。Q則表示每種結構下的不同掛靠方式的航線數量，表3中其他數據選擇的是這些不同掛靠方式中使得每周運營總成本最小的一組。T是一個航次的航行總時間(d)，n則是根據航行總時間和為保證每周一班發(fā)船頻次而確定的船舶數量。C為計算出來的每周運營總成本(單位：萬美元)，最小值為 1 635.55萬美元，而原始航線則為1 677.83萬美元，優(yōu)化后的周運營總成本可節(jié)省42.28萬美元，節(jié)省幅度為2.52%。圖2和圖3分別是原始航線和優(yōu)化航線的各航段空重箱裝載情況。

圖2 原始航線空重箱裝載量

圖3 優(yōu)化后航線空重箱裝載量

從圖2和圖3中可以看到，在保證每個港口的集裝箱輸入和輸出平衡的約束條件下，原始航線每個航段內集裝箱裝載總量始終與最大重箱裝載量相等，為10 800 TEU；而優(yōu)化后的航線中，僅有奧克蘭被掛靠了兩次，根據航線結構設定可知有一個二次掛靠港的航線含有兩個閉環(huán)，兩個閉環(huán)內的集裝箱裝載總量分別為10 800 TEU(即閉環(huán)：新加坡—香港—鹽田—寧波—上?！餮艌D—奧克蘭—新加坡)和6 328 TEU(即閉環(huán)：奧克蘭—長灘—奧克蘭)；這也同時證明了“3 模型求解” 部分所述所述的對于港口集裝箱輸入輸出平衡條件下的推論，即：航線內每個閉環(huán)內不同航段的裝載總量是相等的，而不同閉環(huán)的航段并不一定相等。

5 結 論

實驗結果表明，本文建立的模型在應用中是簡便可行的；優(yōu)化后的航線含有一個二次掛靠港，為奧克蘭，對應的航線掛靠順序為：新加坡—香港—鹽田—寧波—上?！餮艌D—奧克蘭—長灘—奧克蘭—新加坡；設定船型θv=11 000 TEU，優(yōu)化后的航線運營成本相比初始航線每周運營總成本節(jié)省2.52%。本文采用二次回程掛靠港的選擇來設計航線結構，大大降低了計算量，為今后以新的角度來設計航線提供參考。下一步研究的目標是將船速、班期設置等問題進行優(yōu)化也考慮到模型中來，以及考慮沿途掛靠港口涉及3個不同大陸的復雜情況。

[1] BAIRD A.Optimizing the container transshipment hub location[J]. Journal of transport geography, 2006,14：195-214.

[2] BRONMO G，CHRISTIANSEN M，FAGERHOLT K，et al.A multi-start local search heuristic for ship scheduling——a computational study[J]. Computers and Operations Research, 2007,34(3): 900-917.

[3] HSU C, HSIEH Y.Routing ship size and sailing frequency decision-making for a maritime hub-and-spoke container network[J]. Mathematical and Computer Modeling, 2007,45(7/8):899-916.

[4] YAN S, CHEN C, LIN S.Ship scheduling and container shipment planning for liners in short-term operations[J]. Journal of Marine Science and Technology, 2009,14(4):417-435.

[5] AGARWAL R, ERGUN O.Ship scheduling and network design for cargo routing in liner shipping[J]. Transportation Science, 2008,42(2): 175-196.

[6] IMAI A, SHINTANI K, PAPADIMITRIOU S.Multi-port vs.Hub-and-Spoke port calls by containerships[J]. Transportation Research Part E: Logistics and Transportation Review, 2009,45(5):740-757.

[7] KOSMAS O T, VIACHOS D S.Simulated annealing for optimal ship routing[J]. Computers and Operations Research, 2008,35(3):576-581.

[8] 郭子堅,王文淵,唐國磊,等.空重箱混合運輸條件下集裝箱海運網絡優(yōu)化研究[J]. 武漢理工大學學報(交通科學與工程版)，2013,37(2):343-347.

[9] 計明軍，陳哲，王清斌.集裝箱船舶支線運輸航線優(yōu)化算法[J]. 交通運輸工程學報，2011,11(4)：68-75.

[10]陳康，郭利泉，楊忠振.基于混合航線結構的集裝箱航線與空重箱運輸綜合優(yōu)化模型[J]. 系統工程理論與實踐，2014,34(1):122-128.

[11]MOON I K, NGOC A D D, HUR Y S.Positioning empty containers among multiple ports with leasing and purchasing considerations[J]. OR Spectrum, 2010,32(3): 765-786.

[12]SONG D P, DONG J X.Effectiveness of an empty container repositioning policy with flexible destination ports[J]. Transport Policy, 2011,18(1): 92-101.

[13]楊洋.基于集裝箱資源共享的班輪公司空箱調運優(yōu)化模型[J]. 東華大學學報(自然科學版)，2010,36(5): 581-587.

[14]韓曉龍, 種道坤.船公司在新港口上的空箱分配策略[J]. 廣西大學學報(自然科學版)，2016,41(3):738-744.

(責任編輯 梁 健)

The overseas liner route optimization with considering empty container repositioning

LI Jian, HAN Xiao-long

(Scientific Research Institute，Shanghai Maritime University，Shanghai 201306，China)

The global container transportation market has been relatively downturn, many shipping companies have to take different measures to reduce their operation costs in order to maintain the normal operation of the company. In order to design an optimal shipping route and to reduce the operating costs, a new perspective of selecting route, and considering empty container transportation for the cost impact is proposed and a mathematical model from shipping company’s point of view, which aims to minimize the total weekly operating costs, is established. And also, an efficient heuristic algorism to optimize the empty container repositioning is designed. Deploying different number of berthed twice ports in each area, the total costs with corresponding shipping route to find the minimal one are calculated. Case study of Southwest America line shows that when setting one berthed twice port located in North America it can help shipping company to reduce week operating costs by 2.52%. It can be found an optimized overseas liner route by considering empty container repositioning can help shipping companies saving a lot of operating costs.

container; shipping route; empty container; heuristic algorism

2016-06-23；

2016-07-21

國家自然科學基金資助項目(71301101)；上海市科委工程中心能力提升項目(14DZ2280200)

韓曉龍(1980—)，男，上海市人，上海海事大學副教授，博士;E-mail:superhxl@hotmail.com。

李建，韓曉龍.考慮空箱調運的遠洋班輪航線優(yōu)化[J].廣西大學學報(自然科學版)，2016，41(5)：1449-1456.

10.13624/j.cnki.issn.1001-7445.2016.1449

U695.22

A

1001-7445(2016)05-1449-08