楊華龍，劉英，朱全英，張燕

(大連海事大學(xué)交通運(yùn)輸管理學(xué)院，遼寧大連 116026)

0 引言

集裝箱班輪航線設(shè)計(jì)是班輪公司的重要戰(zhàn)略決策，直接關(guān)系到航線配船和船型選擇，對(duì)班輪公司的運(yùn)營(yíng)成本和效益產(chǎn)生長(zhǎng)遠(yuǎn)的影響.隨著近年來(lái)集裝箱航運(yùn)市場(chǎng)需求的劇烈波動(dòng)和競(jìng)爭(zhēng)的不斷加劇，班輪公司如何依據(jù)運(yùn)營(yíng)區(qū)域內(nèi)貨流需求和港口條件，科學(xué)合理地優(yōu)化設(shè)計(jì)班輪航線，引起業(yè)界和學(xué)界的高度關(guān)注.國(guó)內(nèi)外學(xué)者已進(jìn)行大量的相關(guān)研究，取得許多可喜的成果.AGARWAL等［1]利用時(shí)間網(wǎng)絡(luò)拓展思想探討船隊(duì)規(guī)劃和靠泊順序的綜合航線優(yōu)化問(wèn)題.SHINTANI等［2]考慮靠泊港口選擇、靠泊順序、航速和空箱調(diào)運(yùn)等問(wèn)題，對(duì)集裝箱班輪航線進(jìn)行優(yōu)化設(shè)計(jì).NICKEL 等［3]和 GELAREH 等［4]提出一種選擇樞紐港口模式對(duì)航線網(wǎng)絡(luò)進(jìn)行優(yōu)化.GEIR［5]設(shè)計(jì)一種傳統(tǒng)船舶航線網(wǎng)絡(luò)和“中心-分支”航線網(wǎng)絡(luò)模型.MENG等［6-7]建立多階段船舶艦隊(duì)規(guī)劃模型，并采用動(dòng)態(tài)規(guī)劃的方法進(jìn)行求解.丁明明等［8]針對(duì)上海港、天津港和深圳港3大港口，建立集裝箱出口中轉(zhuǎn)港選擇整數(shù)規(guī)劃數(shù)學(xué)模型.董崗［9]通過(guò)班輪航線、港口評(píng)價(jià)、比例關(guān)系、社會(huì)距離和非對(duì)稱(chēng)層次矩陣對(duì)港口進(jìn)行顧客選擇、聚合鏈接、自我中心和層次結(jié)構(gòu)分析，從而得出東北亞班輪航線的港口發(fā)展格局.吳文一［10]主要考慮系統(tǒng)最優(yōu)情況下運(yùn)輸網(wǎng)絡(luò)的優(yōu)化.陳康等［11]針對(duì)航線網(wǎng)絡(luò)與港口集裝箱貨運(yùn)需求之間具有相互影響的動(dòng)態(tài)反饋關(guān)系，建立航線收益最大化模型.計(jì)明軍等［12]以樞紐港船舶限制時(shí)間和支線船舶容量為基礎(chǔ)，分析軸輻式網(wǎng)絡(luò)運(yùn)輸模式，建立支線集裝箱運(yùn)輸混合整數(shù)規(guī)劃模型.殷允健等［13]考慮船公司與競(jìng)爭(zhēng)對(duì)手運(yùn)營(yíng)策略的動(dòng)態(tài)博弈過(guò)程，對(duì)集裝箱班輪發(fā)船間隔時(shí)間進(jìn)行優(yōu)化，以使船公司獲得最大利益.已有研究大都集中在掛靠港口已明確的條件下對(duì)航線進(jìn)行優(yōu)化設(shè)計(jì)，而對(duì)近洋環(huán)繞模式下如何從候選港口中確定樞紐港和喂給港集合并確定港口掛靠順序、喂給港與樞紐港間如何鏈接等方面的研究還很不充分.

為此，本文結(jié)合近洋環(huán)繞模式班輪干/支線運(yùn)輸特點(diǎn)，在滿(mǎn)足區(qū)域內(nèi)集裝箱貨運(yùn)需求的前提下，以班輪公司收益最大化為目標(biāo)，構(gòu)建班輪航線優(yōu)化設(shè)計(jì)模型，以便從候選港口中確定樞紐港和喂給港集合，確定集裝箱船舶的干線運(yùn)輸航線及掛靠樞紐港順序，并為每個(gè)喂給港確定與其相連的最優(yōu)樞紐港及支線運(yùn)輸航線，從而為班輪公司在近洋區(qū)域內(nèi)整體干/支線航線優(yōu)化設(shè)計(jì)提供決策依據(jù).

1 問(wèn)題描述

由于班輪運(yùn)輸具有投資大、運(yùn)營(yíng)成本高的特點(diǎn)，為能夠吸引更多的貨主，培養(yǎng)更多的忠誠(chéng)客戶(hù)，班輪公司在其運(yùn)營(yíng)的近洋區(qū)域內(nèi)一般都采用“中心-分支”港的環(huán)繞模式設(shè)計(jì)班輪航線.該模式能解決航線上的貨流不平衡問(wèn)題，提高船舶艙位利用率和集裝箱利用率，其干支線網(wǎng)絡(luò)見(jiàn)圖1.

圖1 干支線網(wǎng)絡(luò)

從圖1可見(jiàn):每個(gè)樞紐港可與多個(gè)喂給港相連，但每個(gè)喂給港僅能連接一個(gè)樞紐港;干線上船舶按一定順序依次掛靠樞紐港，形成一個(gè)有向的閉環(huán).“中心-分支”環(huán)繞模式包含兩種航段:由兩個(gè)樞紐港連接的樞紐航段和由一個(gè)樞紐港與一個(gè)喂給港連接的支線航段.

因此，基于環(huán)繞模式的班輪航線設(shè)計(jì)問(wèn)題可以表述如下:班輪公司在其運(yùn)營(yíng)的近洋區(qū)域內(nèi)，通過(guò)調(diào)查分析所有候選港口之間的集裝箱班輪的航行成本、港口使費(fèi)、集裝箱裝卸成本等，分析預(yù)測(cè)港口間一定時(shí)期內(nèi)集裝箱運(yùn)輸需求量和運(yùn)價(jià)，在滿(mǎn)足集裝箱貨物運(yùn)輸需求的前提下，以班輪公司效益最大化為目標(biāo)，優(yōu)選出合適的樞紐港，以環(huán)繞的形式將各樞紐港連接起來(lái)形成班輪干線運(yùn)輸線路(簡(jiǎn)稱(chēng)直運(yùn)線路);再對(duì)余下的每個(gè)喂給港，選出其最合適的一個(gè)樞紐港，與之相連形成支線運(yùn)輸線路，在這些支線上，班輪公司可另派支線運(yùn)輸船舶承運(yùn)或?qū)⒓b箱貨物轉(zhuǎn)給其他支線船公司承運(yùn)(這里統(tǒng)稱(chēng)為轉(zhuǎn)運(yùn)).最終，班輪公司可通過(guò)直運(yùn)或轉(zhuǎn)運(yùn)方式完成近洋區(qū)域內(nèi)所有港口間的集裝箱貨物運(yùn)輸.

2 模型建立

假設(shè)某班輪公司在覆蓋多個(gè)港口的某近洋區(qū)域內(nèi)經(jīng)營(yíng)班輪運(yùn)輸業(yè)務(wù)，不失一般性，本文引入以下符號(hào):Ω為所有候選港口的集合;Ωm為樞紐港集合;wij為從港口 i到 j的集裝箱運(yùn)輸需求量，i，j∈Ω;Lij為港口i，j對(duì)間的距離;Ct為集裝箱船舶航行時(shí)的單位費(fèi)用(包括船舶航行費(fèi)用和航行期間的船舶成本等);fij為從港口i到j(luò)的集裝箱單位運(yùn)價(jià);λ為轉(zhuǎn)運(yùn)因數(shù)，表示班輪公司需要將支線部分的運(yùn)輸收入支付給支線轉(zhuǎn)運(yùn)公司的比例;tij為船舶從港口i到j(luò)的航行時(shí)間;W為船舶裝載集裝箱容量;Pi為船舶在樞紐港i的掛靠費(fèi)用(包括港口使費(fèi)和?？科陂g的船舶成本等);Sij為船舶從樞紐港i駛向緊鄰的樞紐港j的0-1變量;Xij為將集裝箱貨物從樞紐港i運(yùn)向樞紐港j的0-1變量;Yij為將集裝箱貨物從喂給港i運(yùn)向樞紐港j的0-1變量;Zij為將集裝箱貨物從樞紐港i運(yùn)向喂給港j的0-1變量.

根據(jù)上述問(wèn)題描述，可建立以下基于環(huán)繞模式的近洋班輪航線優(yōu)化設(shè)計(jì)模型M1:

在模型M1中:式(1)表示班輪運(yùn)輸總收益最大，即運(yùn)輸總收入減去班輪航行成本和集裝箱轉(zhuǎn)運(yùn)成本后最大;式(2)和(3)表示樞紐港之間連接成環(huán)繞航線，即每個(gè)樞紐港進(jìn)向(Inbound)和去向(Outbound)分別都有且僅有一個(gè)樞紐港與之相連;式(4)表示班輪容量約束，即班輪在干線各航段所裝載的集裝箱總量不能超過(guò)集裝箱船舶的最大裝載容量限制;(5)～(8)為變量的0-1約束.

3 模型求解

模型M1為非線性模型，利用一般算法很難求解，為此本文結(jié)合班輪運(yùn)輸實(shí)際情況設(shè)計(jì)以下求解步驟.

步驟1 假設(shè)班輪公司安排船舶遍歷掛靠所有港口(此時(shí)各港口均為樞紐港)，Ωm=Ω，不存在集裝箱貨物轉(zhuǎn)運(yùn)情況.集裝箱班輪運(yùn)輸成本由干線上船舶航行時(shí)的費(fèi)用和掛靠港口時(shí)的費(fèi)用兩部分組成，這樣原問(wèn)題便可簡(jiǎn)化為求解等價(jià)的運(yùn)輸成本最小化問(wèn)題M2.

在模型M2中:式(9)表示班輪運(yùn)輸總成本最小;式(10)和(11)表示各港口之間連接成環(huán)繞航線;式(12)為班輪容量約束;式(13)為變量的0-1約束.很顯然，模型M2是一個(gè)典型的在完全有向圖中搜索一條具有最小權(quán)值和的Hamilton回路問(wèn)題，亦即旅行商問(wèn)題(Traveling Salesman Problem，TSP).求解模型M2，便可得到初始的班輪運(yùn)輸優(yōu)化航線，即船舶掛靠各港口的順序.計(jì)算模型M2的目標(biāo)函數(shù)便可得到班輪公司一個(gè)航次的總成本，記為C0.此時(shí)班輪公司的航次總收益為

步驟2 計(jì)算與每一樞紐港k相關(guān)的收益為

選取收益最小的一個(gè)港口，記為港口k0，同時(shí)把求解模型M2所得的最優(yōu)航線中與港口k0相連接的進(jìn)向和去向兩個(gè)港口分別記為和.去除港口k0后，將和直接相連接，形成新的環(huán)繞式干線.此時(shí)，令 Ωm=Ωm- { k0}.

步驟3 在Ωm中選取與港口k0距離最近的一個(gè)港口，記為 k′0.將 k0作為喂給港并與相連，形成支線.

步驟4 計(jì)算在新形成的干線和支線網(wǎng)絡(luò)下的班輪運(yùn)營(yíng)費(fèi)用為

比較 C′和 C0.若 C′＜ C0，則令 C0=C′，轉(zhuǎn)入步驟2.

步驟5 確定最終樞紐港集合和喂給港集合，并得到優(yōu)化的班輪航線以及模型M1中的所有決策變量 Sij，Xij，Yij和 Zij的值，從而可根據(jù)模型 M1 中的目標(biāo)函數(shù)求得班輪公司的最終總收益.

4 算例分析

假定某班輪公司在中國(guó)—東南亞近洋區(qū)域內(nèi)的12個(gè)港口間開(kāi)展班輪運(yùn)輸業(yè)務(wù)，選用2 400 TEU的集裝箱船投入干線運(yùn)營(yíng)，支線則采用轉(zhuǎn)租方式.船舶航行時(shí)的單位費(fèi)用為30美元/n mile，船舶掛靠各港口的費(fèi)用均為25 000美元.各港口對(duì)間的集裝箱運(yùn)輸需求量(經(jīng)預(yù)測(cè)所得到的在一定時(shí)期內(nèi)較穩(wěn)定的 需求量)、距離和單位集裝箱運(yùn)價(jià)分別見(jiàn)表1～3.

表1 港口對(duì)間的集裝箱運(yùn)輸需求量 TEU

表2 港口對(duì)間的距離 n mile

表3 港口對(duì)間的單位集裝箱運(yùn)價(jià) 美元/TEU

為求解上述問(wèn)題，本文采用MATLAB語(yǔ)言編程實(shí)現(xiàn)上述算法步驟.當(dāng)所有港口都作為樞紐港時(shí)，由步驟1可得初始優(yōu)化航線，見(jiàn)圖2(a).此時(shí)根據(jù)式(14)可得班輪公司的航次總收益為3 286 665美元.當(dāng)給定轉(zhuǎn)運(yùn)因數(shù)λ=0.95時(shí)，按上述算法步驟進(jìn)行迭代求解，可得最終優(yōu)化航線見(jiàn)圖2(b).

圖2 初始和最終優(yōu)化航線

由此可得，班輪公司的優(yōu)化航次總收益為3 335 742.5美元.與初始優(yōu)化航線方案相比，班輪公司收益可增加49 077.5美元.

5 結(jié)束語(yǔ)

本文基于環(huán)繞模式的近洋集裝箱班輪航線優(yōu)化設(shè)計(jì)問(wèn)題，以班輪公司收益最大化為目標(biāo)，在假定一定時(shí)期內(nèi)集裝箱運(yùn)輸需求比較穩(wěn)定的情形下，構(gòu)建班輪航線優(yōu)化模型，設(shè)計(jì)模型的求解算法，以便從區(qū)域內(nèi)候選港口中確定樞紐港和喂給港集合，確定集裝箱船舶的干線運(yùn)輸航線及掛靠樞紐港順序，并為每個(gè)喂給港確定與其相連的最優(yōu)樞紐港及支線運(yùn)輸航線.算例分析表明，本文構(gòu)建的模型和算法簡(jiǎn)便易行，而且經(jīng)過(guò)優(yōu)化后的航線可為班輪公司減少運(yùn)營(yíng)費(fèi)用，同時(shí)也能大大提高班輪公司的航次總收益.

考慮到區(qū)域內(nèi)集裝箱運(yùn)輸需求的不確定性和市場(chǎng)競(jìng)爭(zhēng)性等因素，下一步應(yīng)在考慮班輪航次周期時(shí)間約束、需求不確定以及航運(yùn)競(jìng)爭(zhēng)條件下，進(jìn)行集裝箱班輪航線的優(yōu)化設(shè)計(jì).

［1]AGARWAL R，ERGUN ?.Ship scheduling and network design for cargo routing in liner shipping［J].Transportation Science，2008，42(2):175-196.

［2]SHINTANI K，IMAI A，NISHIMURA E，et al.The container shipping network design problem with empty container repositioning［J].Transportation Research Part E:Logistics＆ Transportation Review，2007，43(1):39-59.

［3]NICKEL S，PISINGER D.Liner shipping hub network design in a competitive environment［J].Transportation Research Part E:Logistics＆ Transportation Review，2010，46(6):991-1004.

［4]GELAREH S，MENG Qiang.A novel modeling approach for the fleet deployment problem within a short-term planning horizon［J].Transportation Research Part E:Logistics＆ Transportation Review，2010，46(1):76-89.

［5]GEIR B.A multi-start local search heuristic for ship scheduling:a computational study［J].Computers ＆ Operations Res，2007，34(3):900-917.

［6]MENG Qiang，WANG Tingsong.A chance constrained programming model for short-term liner ship fleet planning problems［J].OR Spectrum，2010，37(4):329-446.

［7]MENG Qiang，WANG Tingsong，WANG Shuai’an.Short-term liner ship fleet planning with container transshipment and uncertain container shipment demand［J].Eur J Operational Res，2012，223(1):96-105.

［8]丁明明，梁承姬.中國(guó)內(nèi)陸集裝箱出口中轉(zhuǎn)港選擇模型［J].上海海事大學(xué)學(xué)報(bào)，2012，33(4):39-44.

［9]董崗.基于班輪航線的東北亞港口發(fā)展格局［J].上海海事大學(xué)學(xué)報(bào)，2010，31(2):1-6，17.

［10]吳文一.港口對(duì)區(qū)域經(jīng)濟(jì)推動(dòng)作用研究［J].交通企業(yè)管理，2008(2):54-55.

［11]陳康，楊忠振.港口和航線互動(dòng)的集裝箱航線優(yōu)化模型［J].中國(guó)航海，2012，35(4):104-109.

［12]計(jì)明軍，陳哲，王清斌.集裝箱船舶支線運(yùn)輸航線優(yōu)化算法［J].交通運(yùn)輸工程學(xué)報(bào)，2011，11(4):68-75.

［13]殷允健，趙剛.集裝箱班輪發(fā)船間隔時(shí)間動(dòng)態(tài)博弈模型及其應(yīng)用——以應(yīng)對(duì)“天天馬士基”為例［J].上海海事大學(xué)學(xué)報(bào)，2012，33(4):52-56，63.