胡堅堃 彭子良 黃有方

摘要：

為提高班輪公司的資源優(yōu)化能力，解決航線選擇、重箱運輸路徑、空箱調(diào)運路徑、多類型船舶配置以及船速設(shè)定等問題，根據(jù)實際班輪運輸組織方式的特征，構(gòu)建多港掛靠和軸輻式混合網(wǎng)絡(luò)，建立以運營總成本最小為目標的非線性混合整數(shù)規(guī)劃模型。采用大M法把這個非線性模型轉(zhuǎn)換成線性模型后通過CPLEX進行求解，并用中遠集運在亞洲—大洋洲—歐洲區(qū)域的部分航線驗證模型的有效性。通過靈敏度分析發(fā)現(xiàn)：港口裝卸效率的提升對減少班輪公司運營成本效果顯著;船舶的燃油成本與運營成本之間存在著相關(guān)性，故油價的持續(xù)上漲迫使班輪公司選擇降速、配置更多的船舶來降低整體成本。

關(guān)鍵詞：

水路運輸; 船隊運營; 混合整數(shù)規(guī)劃; 班輪網(wǎng)絡(luò); 集裝箱運輸路徑; 空箱調(diào)運

中圖分類號： U692.3

文獻標志碼： A

Abstract：

In order to improve the resource optimization ability of liner companies and solve the issues such as route selection， heavy container shipping route， empty container repositioning， multitype ship configuration and ship speed setting， etc.， according to the characteristics of actual liner transportation organization mode， a multiportcalling and hubandspoke hybrid network is constructed， and a nonlinear mixed integer programming model with the objective of minimum total operating cost is established. The big M method is used to transform the nonlinear model into a linear model， and the CPLEX is used to solve the model. The validity of the model is verified using some routes of COSCO in the AsiaOceaniaEurope region. Through sensitivity analysis， it is found that the improvement of port loading and unloading efficiency has a significant effect on reducing the operating cost of liner companies， and that there is a correlation between fuel cost and operating cost of ships， so the continuous increase of oil price forces the liner companies to reduce speed and deploy more ships to reduce overall cost.

Key words：

waterway transportation; fleet operation; mixedinteger programming; liner network; container transportation route; empty container repositioning

0引言

近年來，班輪運力過剩、燃油價格上漲、船隊配置不合理等問題凸顯。在船隊發(fā)展領(lǐng)域，大多數(shù)國內(nèi)班輪企業(yè)仍然依靠管理者自身經(jīng)驗和常識制定班輪網(wǎng)絡(luò)和船隊調(diào)度決策，缺乏科學(xué)依據(jù)和說服力[1]。在學(xué)術(shù)領(lǐng)域，已有不少學(xué)者開展了相關(guān)研究。在班輪網(wǎng)絡(luò)規(guī)劃方面：CHUANG等[2]綜合考慮重箱運輸和空箱調(diào)運方案，采用了模糊遺傳算法求解需求不確定的多港掛靠網(wǎng)絡(luò)優(yōu)化問題;宋向群等[3]研究了軸輻式運輸網(wǎng)絡(luò)中區(qū)域性網(wǎng)絡(luò)系統(tǒng)的最小費用流問題，設(shè)計了蟻群優(yōu)化算法進行求解;IMAI等[4]對比了軸輻式網(wǎng)絡(luò)和多港掛靠網(wǎng)絡(luò)，以成本最小為目標，探討了不同船型的兩種典型的航線網(wǎng)絡(luò)方案;陳康等[5]考慮了航線網(wǎng)絡(luò)與港口集裝箱貨運需求之間的關(guān)系，以航線收益最大為目標，開發(fā)了基于遺傳算法的啟發(fā)式算法來證明新的集裝箱班輪網(wǎng)絡(luò)優(yōu)化模型能夠有效提高航線運營效率;李建等[6]以每周運營成本最小為目標，設(shè)計了啟發(fā)式算法解決空箱調(diào)運問題，并證明了對考慮空箱調(diào)運的班輪航線進行優(yōu)化可減少班輪公司總成本;吳瓊等[7]以CKYH聯(lián)盟為例，建立了混合整數(shù)規(guī)劃模型，并利用列生成算法和CPLEX提供了一種航運網(wǎng)絡(luò)優(yōu)化的新方法;楊華龍等[8]通過對航線貨流量的分析預(yù)測，對中轉(zhuǎn)制和直航制兩種方案下的班輪航行時間進行了比較，并確定了對應(yīng)的配船數(shù);薛穎霞等[9]考慮了低碳背景下航運網(wǎng)絡(luò)配船總成本和碳排放量，建立了雙目標規(guī)劃模型，實現(xiàn)了班輪公司節(jié)能減排的目的。在班輪船隊調(diào)度方面，要解決的是將不同船型配置到不同的航線上使得收益最大或成本最小。MENG等[10]建立了運輸需求不確定情況下的雙層隨機規(guī)劃模型求解船隊調(diào)度;壽涌毅等[11]在合理配置班輪和不存在時間沖突的條件下建立了01整數(shù)規(guī)劃模型，并利用蟻群算法進行求解;楊立乾[12]考慮了船舶容量和時間限制，構(gòu)建了船舶調(diào)度模型，并利用粒子群算法進行求解;靳志宏等[13]以總航行成本最小為目標函數(shù)，考慮現(xiàn)實因素建立了船隊調(diào)度模型并進行求解;蔡佩林等[14]以中歐航線為例，建立了隨機規(guī)劃模型，并進行敏感度分析，最終得到了合理的船舶調(diào)度方案。

現(xiàn)有的研究對班輪網(wǎng)絡(luò)中航線設(shè)置、船舶配載、船速設(shè)定、集裝箱運輸路徑之間的相互關(guān)聯(lián)性考慮較少。本文借鑒部分現(xiàn)有成果，對多港掛靠和軸輻式混合網(wǎng)絡(luò)中的多類型船舶配置、重箱運輸路徑、空箱調(diào)運路徑、船速控制等問題進行整體優(yōu)化，以成本最小為目標，以船舶容量限制、每周發(fā)船頻率、箱量平衡、滿足運輸需求等為約束條件，建立數(shù)學(xué)模型，設(shè)計相應(yīng)的求解流程，并通過中遠集運的部分實際航線進行驗證和分析。

1問題描述

1.1班輪網(wǎng)絡(luò)

班輪網(wǎng)絡(luò)由港口和航線組成，本文設(shè)定的班輪網(wǎng)絡(luò)為多港掛靠與軸輻式混合運輸網(wǎng)絡(luò)，即保留多港掛靠航線，并允許航線在樞紐港進行中轉(zhuǎn)，見圖1。圖1中：圓形和方形分別代表兩種不同類型的港口，其中圓形代表喂給港，方形代表樞紐港;港口A為港口C、G、F的樞紐港，港口B為港口D、E的樞紐港，集裝箱的中轉(zhuǎn)須通過喂給港所屬的樞紐港完成;航線1、航線2、航線3和航線4均用港口序列表示;船舶在同一條航線上相鄰兩個港口之間的航行路段，稱為航段，例如CG為航線1上的一個航段;每段弧上的數(shù)字為該航段的長度;船舶在同一條航線上任意兩個港口之間的航行路程，稱為航程，例如船舶從港口C到港口F的航行路程為航線1上的一個航程，航程由一個或多個航段組成。

1.2集裝箱運輸路徑

在班輪網(wǎng)絡(luò)中存在大量的重箱運輸需求，單位重箱運輸需求包括啟運港、目的港和運輸量。對于單位重箱運輸需求，多條運輸路徑均可以滿足。假設(shè)圖1的網(wǎng)絡(luò)中有一個從港口C到港口E重箱運輸需求，則共存在5條運輸路徑：（1）通過航線2從港口C直達港口E，航程為5 037.50 n mile;（2）通過航線1從港口C直達港口E，航程為5 738.89 n mile;（3）通過航線3從港口C到港口B，在港口B中轉(zhuǎn)后，通過航線4到達港口E，航程為6 995.82 n mile;（4）通過航線2從港口C到達港口B，在港口B中轉(zhuǎn)后，通過航線4到達港口E，航程為14 513.34 n mile;（5）通過航線3從港口C到達港口B，在港口B中轉(zhuǎn)后，通過航線2到達港口E，航程9 386.03 n mile。運輸路徑1為最短路徑，但班輪公司為了均衡運輸和充分利用船舶負載，可能將一部分重箱通過其他路徑運輸，這就需要更長的航程和時間，從而會降低班輪公司的服務(wù)質(zhì)量，最終導(dǎo)致客戶的流失。本文設(shè)置閾值為1.5，即若備選運輸路徑的長度是最短路徑長度的1.5倍以上，則該備選運輸路徑不可行。在上述5條運輸路徑中，最短的航程為5 037.5 n mile，則允許的最長的航程為7 556.25 n mile，故路徑4、5不可行。

由于貿(mào)易的不平衡，各港口會出現(xiàn)空箱缺少或多余的情況?？障溥\輸不同于重箱運輸，它沒有明確的運輸出發(fā)地和目的地，只需滿足網(wǎng)絡(luò)中各港口的空箱需求和運輸過程中船舶的容量限制，本文中不考慮有空箱與重箱比例約束的船舶積載規(guī)則。

1.3船速和配船

班輪公司的船隊中有不同類型的船舶，本文以不同的容量代表不同的船舶類型，不同的船舶類型有不同的速度區(qū)間以及相應(yīng)速度下的油耗率。假設(shè)發(fā)船頻率為每周一次，即每條航線上，在每周的同一時刻從同一港口發(fā)船掛靠航線上的其他港口，則一個航次所需的時間為168×航線上所配的船數(shù)（單位為h，一周為168 h）。一般而言，船速越快，油耗越多，燃油成本越高，但是完成一個航次所需的時間越短，因此可通過減少在這條航線上配置的船舶數(shù)量來降低船舶的運行費用（包括保險、船員工資、維修費等）。

1.4系統(tǒng)流程框架

集裝箱班輪網(wǎng)絡(luò)設(shè)計和運輸路徑優(yōu)化的求解流程見圖2。已知數(shù)據(jù)為港口數(shù)據(jù)（包括港口類型和喂給港分配）、重箱運輸需求（包括啟運港、目的港和運輸量）、航線數(shù)據(jù)（包括港口掛靠順序和航段的長度）和船舶數(shù)據(jù)（包括船舶類型、每周運維費和油耗率）;航段集合由航線數(shù)據(jù)計算得到;港口空箱需求由港口數(shù)據(jù)和重箱運輸需求計算得到;可行重箱運輸路徑由重箱運輸需求、航線數(shù)據(jù)和設(shè)定的運輸效率值計算得到;航程集合由可行重箱運輸路徑計算得到;船隊配置、船速設(shè)定、運輸路徑上分配的箱量等為決策變量;總成本由空箱裝卸費、重箱裝卸費和船舶航行費構(gòu)成。由此，建立統(tǒng)一的規(guī)劃模型進行求解。

班輪公司的航運網(wǎng)絡(luò)有多條航線，每條航線上需要配置足夠多的船舶，以便提供具有一定頻率的運輸服務(wù)。班輪運輸路徑、航線配船數(shù)量、船速、空箱運輸數(shù)量等通常會直接影響班輪公司總成本。根據(jù)船隊運力和各港口集裝箱運輸需求確定各航線上船舶類型、配船數(shù)量、最佳船速等并最小化班輪公司運營成本是本文要解決的問題。

2建模與求解

2.1變量和參數(shù)定義

集合：港口集合為P，港口p∈P;航線集合為R，航線r∈R;航段集合為L，航段l∈L;航程集合為S，航程s∈S;航線r上的航程集合為Sr;集裝箱港口重箱運輸需求集合為O，具體港口需求o∈O;船舶類型集合為V，船舶類型v∈V; v型船的可行速度集合為Fv，船速f∈Fv;船舶可行運輸路徑集合為E，具體可行運輸路徑e∈E;集裝箱港口重箱運輸需求o的可行運輸路徑集合為Eo;包含航程s的可行運輸路徑集合為Es。

已知變量或計算可得變量：gr為航線r的長度;w（r）為航線r上的港口數(shù)量;δrsl表示在航線r上的航程s是否包含航段l，若包含則取1，否則取0;no為集裝箱港口重箱運輸需求o的運輸量;hp為港口p由于貿(mào)易不平衡產(chǎn)生的空箱量;uv為v型船的容量;Cvf為v型船船速為f時的油耗率。

參數(shù)：α為每噸燃油的價格;β為每個重箱的裝卸費;β～為每個空箱的裝卸費;γ為港口裝卸單位集裝箱所需時間;χv為v型船每周的運行費用。

決策變量：xrv，若v型船配置在航線r上，則xrv取1，否則取0;xrvf，若配置在航線r上的v型船船速為f，則xrvf取1，否則取0;ys為通過航程s運輸?shù)闹叵淞?ye為在可行運輸路徑e上分配的重箱量;rp為在航線r上的港口p裝載的空箱量;z～rp為在航線r上的港口p卸載的空箱量;arli為通過航線r上第i個航段運輸?shù)目障淞?Nr為在航線r上配置的船舶數(shù)量。

2.2優(yōu)化模型

以班輪公司每周的總成本最小為目標建立模型：

min FF=r∈Rv∈V（χvNrxrv）+

r∈Rv∈Vf∈Fv（αCvfgrf-1xrvf）+

2βs∈Sys+β～r∈Rp∈r（rp+z～rp）

（1）

式（1）為目標函數(shù)，包含了非線性項Nrxrv。采用大M法，令prv=Nrxrv（表示航線r上配置的v型船的數(shù)量），通過等價變換，上述模型轉(zhuǎn)化為混合整數(shù)線性規(guī)劃模型：

min F|F=r∈Rv∈V（χvprv）+

r∈Rv∈Vf∈Fv（αCvfgrf-1xrvf）+

2βs∈Sys+β～r∈Rp∈r（rp+z～rp）

（2）

s. t.

Nr≤prv+M（1-xrv）（3）

Nr=v∈Vprv（4）

v∈Vxrv≤1（5）

f∈Fvxrvf=xrv（6）

no=e∈Eoye（7）

ys=e∈Esye（8）

hp=r∈R（rp-z～rp）（9）

2γs∈Srys+γp∈P（rp+z～rp）+

v∈Vf∈Fv（grf-1xrvf）≤168Nr

（10）

arli+rp（i+1）-z～rp（i+1）=arl（i+1），

i=1，2，…，w（r）-1

（11）

arlw（r）+rp1-z～rp1=arl1（12）

s∈Srδrslys+arl≤v∈Vuvxrv（13）

ys，ye，rp，z～rp≥0 （14）

Nr∈Z+∪{0} （15）

式（2）為等價目標函數(shù)，由4部分組成，分別為船舶運行費、燃油費、重箱裝卸費和空箱裝卸費;式（3）和（4）保證目標式的變換是等價的;式（3）保證一條航線上只能配置一種類型的船舶，其中M表示一個足夠大的數(shù);式（4）表示航線r上配置的船舶數(shù)量;式（5）保證每條航線上配置一種類型的船舶或者取消運營;式（6）保證每艘船在航線上以某一固定速度航行;式（7）使得每個重箱運輸需求都得到滿足;式（8）指出每個航程上通過的箱量等于所有包含該航程的運輸路徑上運輸箱量的總和;式（9）確保每個港口的空箱需求得到滿足;式（10）保證每周的發(fā)船頻率，不等號左邊3項分別是重箱裝卸時間、空箱裝卸時間和航行時間，不等號右邊是一個航次所需的最長時間;式（11）和（12）保證每個港口的空箱進出量保持平衡;式（13）是船舶的容量限制，左邊2項分別是重箱量和空箱量;式（14）和（15）為非負和整數(shù)的約束。

3模擬計算和結(jié)果分析

3.1計算環(huán)境與參數(shù)

以中遠集運在亞洲—大洋洲—歐洲區(qū)域掛靠港口相對集中的部分航線為實例，對上述模型和求解方法進行驗證。該班輪網(wǎng)絡(luò)包含22個港口和12條航線。船隊中有容量為3 000 TEU、5 000 TEU和10 000 TEU等3種類型的船舶，不同類型的船舶在不同船速下的油耗率不同。運算環(huán)境為：CPU，Intel i5 2.53 GHz; RAM，3GB。

3.2計算結(jié)果

隨機生成200個重箱運輸需求，每個需求的運輸量在100～300 TEU范圍內(nèi)，油價為300美元/t，裝卸單位空箱的費用為40美元，裝卸單位重箱的費用為60美元，港口裝卸單位集裝箱所需時間為0.01 h。通過大M法將模型轉(zhuǎn)化為線性規(guī)劃模型，并利用CPLEX進行求解，具體優(yōu)化結(jié)果見表1。由表1可得每條航線上配置的船舶類型、船舶數(shù)量、船速、運行時間及時間分布，其中原航線4上的運輸任務(wù)可通過其他航線進行運輸。

3.3靈敏度分析

3.3.1港口裝卸速度

在油價和單位集裝箱裝卸費用不變的前提下，分析港口裝卸單位集裝箱所需時間（取0.01、0.02和0.03 h等3個值，相應(yīng)的港口裝卸速度分別為100、50和 33.33 TEU/h）對船隊運行成本和船舶配置數(shù)量的影響，見圖3和4。分析結(jié)果如下：（1）港口裝卸速度的提升使得裝卸時間在航行周期中占的

比例有明顯的降低。（2）港口裝卸速度的提升對集裝箱運輸路徑基本沒有影響，這是因為空箱和重箱的裝卸費基本沒有變化。（3）裝卸時間的減少使得整個航行周期縮短，需要配置的船舶數(shù)量減少，船隊運行總成本從1 629美元降到1 444美元，成本降低幅度比較明顯。

圖3港口裝卸速度對船隊運行成本的影響

圖4港口裝卸速度對船舶配置數(shù)量的影響

3.3.2油價

在港口裝卸單位集裝箱所需時間和裝卸費不變的前提下，分析油價（分別為300、400、500、600美元/t）對船隊運行成本和船舶配置數(shù)量的影響，見圖5和6。分析結(jié)果如下：（1）油價的上升對集裝箱運輸路徑基本沒有影響，這是因為空箱和重箱的裝卸費基本沒有變化。（2）油價的上升直接造成了船舶燃油費的上升。（3）油價的上升迫使船舶選擇低速航行以減少燃油費，但是會延長整個航行周期，需要配置的船舶數(shù)量會增多，這意味著一部分燃油費被轉(zhuǎn)嫁至船舶運行費，從而達到整體最優(yōu)。

4結(jié)論

本文通過模擬班輪企業(yè)運營環(huán)境中的班輪網(wǎng)絡(luò)特征，創(chuàng)新性地將航線選擇、重箱運輸路徑、空箱調(diào)運路徑、船舶配置方案、最優(yōu)船速這5個要素進行了整體優(yōu)化，建立了非線性混合整數(shù)規(guī)劃模型，用大M法將該非線性模型等價轉(zhuǎn)化為線性模型后用CPLEX進行求解，并用中遠集運的部分航線對模型

和算法進行驗證。通過分析發(fā)現(xiàn)：港口裝卸效率的提升對減少整體成本效果顯著;船舶的燃油成本與運行成本存在著相關(guān)性，故油價的持續(xù)上漲迫使班輪公司選擇降速、配置更多的船舶使整體成本降低。

海運過程中產(chǎn)生的碳排放是造成環(huán)境污染的重要原因。碳排放量的產(chǎn)生跟油耗量有關(guān)，油耗量又與船速密切相關(guān)，但是從油價敏感度分析結(jié)果看，盡管油價從300美元/t上漲到600美元/t，但是船舶的配置數(shù)量沒有明顯的增多，這意味著船速沒有明顯的下降，故通過純市場調(diào)控進行節(jié)能減排收效甚微，如何制定有效的政策措施是下一步努力的方向。

參考文獻：

[1]楊秋平， 謝新連， 趙家保. 船隊規(guī)劃研究現(xiàn)狀與動態(tài)[J]. 交通運輸工程學(xué)報， 2010， 10（4）： 8590.

[2]CHUANG T N， LIN C T， KUNG J Y， et al. Planning the route of container ships： a fuzzy genetic approach[J]. Expert Systems with Applications， 2010， 37（4）： 29482956. DOI： 10.1016/j.eswa.2009.09.040.

[3]宋向群， 張鵬， 郭子堅. 基于蟻群算法的港口集裝箱運輸網(wǎng)絡(luò)徑流優(yōu)化[J]. 大連理工大學(xué)學(xué)報， 2007， 47（6）： 853857.

[4]IMAI A， SHINTANI K， PAPADIMITRIOUS S. Multiport vs.HubandSpoke port calls by containerships[J]. Transportation Research Part E： Logistics and Transportation Review， 2009， 45（5）： 740757. DOI： 10.1016/j.tre.2009.01.002.

[5]陳康， 楊忠振. 港口和航線互動的集裝箱航線優(yōu)化模型[J]. 中國航海， 2012， 35（4）： 104109.

[6]李建， 韓曉龍. 考慮空箱調(diào)運的遠洋班輪航線優(yōu)化[J]. 廣西大學(xué)學(xué)報（自然科學(xué)版）， 2016， 41（5）： 14491456. DOI： 10.13624/j.cnki.issn.10017445.2016.1449.

[7]吳瓊， 鄭士源， 朱太球. 基于列生成算法的集裝箱班輪運輸網(wǎng)絡(luò)優(yōu)化[J]. 上海海事大學(xué)學(xué)報， 2014， 35（1）： 2934. DOI： 10.13340/j.jsmu.2014.01.007.

[8]楊華龍， 陳曉東. 大陸北方/臺灣班輪航線方案優(yōu)化研究[J]. 系統(tǒng)工程理論與實踐， 2001（3）： 112115.

[9]薛穎霞， 邵俊崗. 低碳經(jīng)濟背景下班輪航線配船[J]. 中國航海， 2014， 37（4）： 115119.

[10]MENG Qiang， WANG Tingsong， WANG Shuaian. Shortterm liner ship fleet planning with container transshipment and uncertain container shipment demand[J]. European Journal of Operational Research， 2012， 223（1）： 96105.

[11]壽涌毅， 賴昌濤， 呂如福. 班輪船舶調(diào)度多目標優(yōu)化模型與蟻群算法[J]. 交通運輸工程學(xué)報， 2011， 11（4）： 8488.

[12]楊立乾. 基于軸輻式網(wǎng)絡(luò)的集裝箱支線運輸多船型船舶調(diào)度模型[J]. 中國管理科學(xué)， 2015， 23（S1）： 860864.

[13]靳志宏， 解玉真， 李陽， 等. 集裝箱支線運輸船舶調(diào)度優(yōu)化問題[J]. 中國航海， 2008， 31（4）： 415419.

[14]蔡佩林， 曾艷英， 涂建軍. 基于機會約束規(guī)劃的集裝箱船舶調(diào)度研究[J]. 物流技術(shù)， 2013， 32（13）： 303306. DOI： 10.3969/j.issn.1005152X.2013.07.098.

（編輯趙勉）