基于節(jié)點(diǎn)限制的軸幅式集裝箱海運(yùn)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)

張 祺，彭 云，王文淵，宋向群，郭子堅(jiān)

(大連理工大學(xué) 建設(shè)工程學(xué)部，遼寧 大連 116024)

0 引 言

隨著國際集裝箱運(yùn)輸快速增長和船舶大型化的發(fā)展趨勢，多港掛靠的航線結(jié)構(gòu)在船舶利用率以及運(yùn)輸經(jīng)濟(jì)性方面均存在不足，軸輻式網(wǎng)絡(luò)結(jié)構(gòu)因其規(guī)模經(jīng)濟(jì)效益，已成為班輪公司關(guān)注的焦點(diǎn)[1-2]。如丹麥的馬士基航運(yùn)先后在地中海和東亞地區(qū)完成了軸輻式網(wǎng)絡(luò)的建設(shè)，地中海沿岸的集裝箱經(jīng)過阿爾赫西拉斯港中轉(zhuǎn)，東亞地區(qū)的集裝箱通過髙雄港中轉(zhuǎn)[3]。船舶的大型化必然要求減少掛靠的港口數(shù)量以提高船舶公司的經(jīng)濟(jì)性，集裝箱船在主航線上?？康母劭趯⒃絹碓缴伲劭诘摹皹屑~”特征將更加突出。軸輻式網(wǎng)絡(luò)結(jié)構(gòu)通過集中集裝箱流在樞紐港口，利用大型集裝箱船集中運(yùn)輸，使船隊(duì)和航線產(chǎn)生規(guī)模經(jīng)濟(jì)，降低了集裝箱的單位運(yùn)營成本[4]。因此，如何科學(xué)設(shè)計(jì)集裝箱運(yùn)輸路徑并匹配適宜船型來實(shí)現(xiàn)軸幅式網(wǎng)絡(luò)的經(jīng)濟(jì)效益是船舶公司關(guān)注的重點(diǎn)，也是筆者所要解決的問題。

國內(nèi)外有關(guān)軸幅式集裝箱海運(yùn)網(wǎng)絡(luò)優(yōu)化設(shè)計(jì)的相關(guān)研究較多。如何利用海運(yùn)網(wǎng)絡(luò)，確定樞紐港位置以及適宜的路徑，成為各大班輪公司所面臨的問題[5-7]。吳旗韜等[8]以西北歐36個集裝箱港口為研究對象，研究非容量限制下單配置樞紐中位問題，優(yōu)化航線網(wǎng)絡(luò)中樞紐港個數(shù)和位置。趙宇哲等[3]通過度量集裝箱運(yùn)輸成本、港口掛靠成本、CO2排放成本，結(jié)合集裝箱流量守恒與樞紐港口容量限制兩個約束，構(gòu)建了考慮CO2排放的軸輻式集裝箱海運(yùn)網(wǎng)絡(luò)優(yōu)化模型，并運(yùn)用拉格朗日松弛算法對模型進(jìn)行求解。鐘銘等[2]考慮需求的不確定性，引入風(fēng)險(xiǎn)系數(shù)，建立混合整數(shù)區(qū)間現(xiàn)行規(guī)劃模型，解決軸幅式集裝箱班輪網(wǎng)絡(luò)優(yōu)化問題。M.G.KARLAFTIS等[9]考慮一個樞紐港與幾個支線港組成的軸幅式網(wǎng)絡(luò)，應(yīng)用遺傳算法解決運(yùn)輸時間約束下的集裝箱運(yùn)輸路徑優(yōu)化問題。A.J.BAIRD[10]考慮國際集裝箱中轉(zhuǎn)，解決北歐地區(qū)樞紐港選址優(yōu)化問題。N.AZIZI等[11]考慮樞紐港在突發(fā)事件下的風(fēng)險(xiǎn)成本，以網(wǎng)絡(luò)總運(yùn)輸成本最小為目標(biāo)，解決災(zāi)害發(fā)生下的樞紐港重新選址的問題。以上研究未考慮相應(yīng)航線上航行的船隊(duì)調(diào)度，因此，如何調(diào)度集裝箱船舶并設(shè)計(jì)運(yùn)輸路徑成為各大班輪公司所面臨的另一個問題。班輪集裝箱船舶調(diào)度問題最早由D.I.JARAMILLO等提出，在給定航線的基礎(chǔ)上，應(yīng)用線性規(guī)劃解決船舶數(shù)量和船型的配置問題[12]。Q.MENG等[13]對班輪集裝箱船舶調(diào)度與路徑優(yōu)化問題進(jìn)行綜述，并提出未來研究方向。C.E.M.PLUM等[14]考慮船舶的運(yùn)輸能力建立班輪集裝箱網(wǎng)絡(luò)服務(wù)流模型。M.W.NG[15]考慮運(yùn)輸市場需求的不確定性，建立通用的班輪運(yùn)輸網(wǎng)絡(luò)下集裝箱船舶配置數(shù)學(xué)模型。

綜上所述，上述研究中的集裝箱海運(yùn)網(wǎng)絡(luò)優(yōu)化模型可容納網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量一般較小，且對網(wǎng)絡(luò)中的港口節(jié)點(diǎn)并未做任何限制。實(shí)際上，網(wǎng)絡(luò)節(jié)點(diǎn)的通過能力是一定的，達(dá)到這一能力時，本應(yīng)到達(dá)該節(jié)點(diǎn)的集裝箱就會改變路徑。因此，筆者從集裝箱運(yùn)輸?shù)膶?shí)際情況出發(fā)，嘗試將Q-學(xué)習(xí)方法和混沌優(yōu)化這兩種智能優(yōu)化算法應(yīng)用到集裝箱海運(yùn)網(wǎng)絡(luò)的優(yōu)化中，以體現(xiàn)大型集裝箱船舶的規(guī)模效益為前提，以集裝箱運(yùn)輸總成本最小為目標(biāo)，考慮港口通過能力限制，尋找合理的海運(yùn)集裝箱運(yùn)輸路徑并配置適宜船舶，為船舶公司建設(shè)軸幅式海運(yùn)網(wǎng)絡(luò)的經(jīng)營策略及集裝箱港口的宏觀規(guī)劃提供充實(shí)可靠的理論依據(jù)。

1 問題描述

集裝箱海運(yùn)是不同噸級的集裝箱船舶在不同的航線上運(yùn)輸。定義軸幅式集裝箱海運(yùn)網(wǎng)絡(luò)(圖1)為G(N,A)，其中N為港口節(jié)點(diǎn)的集合，A為網(wǎng)絡(luò)中節(jié)點(diǎn)間的弧的集合，也就是港口節(jié)點(diǎn)之間所有的可以相互連接的可行的航線集合。對于任意港口節(jié)點(diǎn)i,j∈N，定義ij∈A為由港口節(jié)點(diǎn)i到港口節(jié)點(diǎn)j的航線，則由港口節(jié)點(diǎn)i到港口節(jié)點(diǎn)j的運(yùn)輸成本可表示為Cij，兩港口間的運(yùn)輸距離可表示為dij。網(wǎng)絡(luò)中任一集裝箱均從起始港出發(fā)，多次經(jīng)過樞紐港口中轉(zhuǎn)，到達(dá)訖點(diǎn)港口，起訖港口間通過支線或干線銜接。如圖1中，假設(shè)某一集裝箱由節(jié)點(diǎn)k起始，經(jīng)過海運(yùn)網(wǎng)絡(luò)，到達(dá)節(jié)點(diǎn)l，則網(wǎng)絡(luò)中可能的一條集裝箱流向?yàn)閗→i→j→l。

圖1 軸幅式集裝箱海運(yùn)網(wǎng)絡(luò)Fig.1 Hub-and-spoke container shipping network

2 模型的構(gòu)建與求解

2.1 模型假設(shè)

集裝箱海運(yùn)網(wǎng)絡(luò)運(yùn)輸是一個復(fù)雜的過程，需對海運(yùn)網(wǎng)路設(shè)計(jì)問題作出如下假設(shè)：

假設(shè)1：集裝箱海運(yùn)網(wǎng)絡(luò)結(jié)構(gòu)相對穩(wěn)定，不考慮突發(fā)事件等不確定性因素的影響；

假設(shè)2：模型中不考慮重箱、空箱和租賃箱成本的區(qū)別。

假設(shè)3：模型中所有起訖港口之間的集裝箱流量為己知，可根據(jù)各港口吞吐量及腹地經(jīng)濟(jì)水平進(jìn)行預(yù)測。

假設(shè)4：軸幅式集裝箱海運(yùn)網(wǎng)絡(luò)由若干條干線和支線組成，不考慮各國沿海運(yùn)輸權(quán)的限制。

假設(shè)5：軸幅式集裝箱海運(yùn)網(wǎng)絡(luò)中各節(jié)點(diǎn)均能通過航線相連。

2.2 集裝箱運(yùn)輸成本分析

海運(yùn)集裝箱運(yùn)輸成本是船舶公司在各港口起訖對之間運(yùn)輸集裝箱的全過程中產(chǎn)生的費(fèi)用總和，分為船舶成本和港口成本兩部分。船舶成本是指在運(yùn)輸過程中船舶發(fā)生的各項(xiàng)費(fèi)用，包括經(jīng)常性維護(hù)費(fèi)用、燃料成本和資本成本；港口成本是指船舶進(jìn)出港口發(fā)生的各種使用費(fèi)用，包括船舶噸稅、停泊費(fèi)、引航費(fèi)、拖輪費(fèi)、裝卸費(fèi)等。

2.2.1 船舶成本

船舶成本由船公司的租船成本(維護(hù)費(fèi)用及資本成本)和燃料成本兩部分組成，如式(1)。

(1)

船型為m的單艘集裝箱船的租船成本是船舶每天租船成本和運(yùn)輸時間的復(fù)合函數(shù)如式(2)。

(2)

船型為m的集裝箱船的燃油費(fèi)用主要包括燃料消耗費(fèi)用和潤滑油消耗費(fèi)用，如式(3)。

(3)

2.2.2 港口成本

港口成本包括船舶進(jìn)港費(fèi)用(引航費(fèi)、移泊費(fèi)、系解纜費(fèi)、停泊費(fèi)統(tǒng)稱為進(jìn)港費(fèi)用)和裝卸費(fèi)用，如式(4)。

(4)

2.2.3 海運(yùn)網(wǎng)絡(luò)總成本

(5)

因此，對于集裝箱海運(yùn)網(wǎng)絡(luò)G(N,A)，網(wǎng)絡(luò)總運(yùn)輸成本CT如式(6)。

(6)

2.3 模型構(gòu)建

建立以海運(yùn)集裝箱運(yùn)輸總成本最小為目標(biāo)的數(shù)學(xué)模型，模型的目標(biāo)函數(shù)如式(7)。

(8)

(9)

式中：Pi為港口節(jié)點(diǎn)i的年極限通過能力。

2.4 模型求解

海運(yùn)集裝箱網(wǎng)絡(luò)的優(yōu)化模型規(guī)模十分龐大，網(wǎng)絡(luò)內(nèi)各港口節(jié)點(diǎn)不相互獨(dú)立，任一港口節(jié)點(diǎn)的變化均會對整個海運(yùn)網(wǎng)絡(luò)產(chǎn)生影響，從而影響模型求解。隨著網(wǎng)絡(luò)節(jié)點(diǎn)的增多，問題處理規(guī)模呈現(xiàn)指數(shù)性增長，傳統(tǒng)線性方法幾乎無法求解，因此采用結(jié)合混沌優(yōu)化方法的Q-學(xué)習(xí)算法求解海運(yùn)集裝箱運(yùn)輸路徑優(yōu)化問題。

(10)

模型的求解可分為兩部分，一部分是運(yùn)用優(yōu)化算法計(jì)算集裝箱運(yùn)輸路徑，另一部分是在前一步的基礎(chǔ)上，求解各港口之間的運(yùn)輸集裝箱的船型服務(wù)頻率，最終才能確定當(dāng)前解對應(yīng)的運(yùn)輸成本?；旌蟽?yōu)化算法流程如圖2，具體流程如下：

圖2 混合優(yōu)化算法流程Fig. 2 Process of hybrid optimization algorithm

Step1:確定集裝箱海運(yùn)網(wǎng)絡(luò)規(guī)模，預(yù)測集裝箱重箱OD量，初始化Q表、混沌變量；

Step2:選擇中轉(zhuǎn)港，確定模型的一個可行解；

Step3:驗(yàn)證各港口的吞吐量是否在極限通過能力的容許范圍內(nèi)，若在，進(jìn)行下一步，否則，超限的路徑的回報(bào)r取-|rn-1|，執(zhí)行Step 7；

Step4:根據(jù)可行解確定每兩個節(jié)點(diǎn)間的集裝箱流量；

Step5:根據(jù)每兩節(jié)點(diǎn)間的實(shí)際箱流量確定成本最低的船型與頻率組合；

Step6:根據(jù)式(10)計(jì)算該可行解的總運(yùn)輸成本，計(jì)算回報(bào)r；

Step7:更新Q表，并驗(yàn)證Q值是否收斂，若是，尋優(yōu)結(jié)束，輸出當(dāng)前最優(yōu)解，否則返回Step 2；

3 實(shí)例分析

為了研究環(huán)渤海地區(qū)港口的外貿(mào)集裝箱運(yùn)輸路徑，筆者從位于三大國際干線(東亞-北美-歐洲)的港口中選擇與環(huán)渤海地區(qū)主要集裝箱港口(大連港、天津港、青島港)貿(mào)易交流比較頻繁的周邊及跨洋港口作為港口節(jié)點(diǎn)集合，組成具有15個港口的海運(yùn)集裝箱網(wǎng)絡(luò)，定義港口代號如表1。

表1 外貿(mào)港口集裝箱運(yùn)輸網(wǎng)絡(luò)節(jié)點(diǎn)

3.1 模型輸入?yún)?shù)

環(huán)渤海地區(qū)外貿(mào)集裝箱運(yùn)輸網(wǎng)絡(luò)采用7種船型，分別為1 000TEU，2 500TEU，3 500TEU，5 000TEU，6 000TEU，7 500TEU，10 000TEU。

根據(jù)國際主干線運(yùn)價水平、Drewry集裝箱市場季度報(bào)告、中華人民共和國港口收費(fèi)規(guī)則等確定本研究各項(xiàng)成本參數(shù)。集裝箱海運(yùn)運(yùn)費(fèi)相關(guān)參數(shù)及數(shù)據(jù)參考CI-Online 集裝箱在線、BLM-Shipping軟件等。根據(jù)運(yùn)輸網(wǎng)絡(luò)中涉及的各國或地區(qū)2010—2014年連續(xù)5年的外貿(mào)進(jìn)出口量，運(yùn)用時間序列法，預(yù)測得到2016年上述地區(qū)間的外貿(mào)進(jìn)出口額。再按照MFD(macroscopic fundamental diagrams)法得到上述各港口間的集裝箱OD量，如表2。

3.2 結(jié)果分析

采用C++語言編寫優(yōu)化程序，并在VC++6.0環(huán)境下通過編譯運(yùn)行，其混合優(yōu)化算法收斂速度見圖3。

將集裝箱運(yùn)輸網(wǎng)絡(luò)有向圖、各港口間2016年集裝箱OD量預(yù)測值、各成本參數(shù)及各港口間的實(shí)際海運(yùn)距離等輸入數(shù)據(jù)代入模型算法程序中進(jìn)行優(yōu)化計(jì)算，分別運(yùn)用混合優(yōu)化、混沌優(yōu)化、Q-學(xué)習(xí)算法求解模型計(jì)算結(jié)果如表3。

表2 2016年15個港口的集裝箱OD預(yù)測

表3 港口集裝箱運(yùn)輸網(wǎng)絡(luò)綜合成本優(yōu)化結(jié)果

圖3 混合優(yōu)化算法收斂速度Fig. 3 Convergence velocity of hybrid optimization algorithm

混合優(yōu)化算法求得的集裝箱運(yùn)輸路徑選擇方案如表4。由表4可以看出，大部分箱量都選擇直達(dá)的方式運(yùn)輸，但距離較遠(yuǎn)且OD量不大的起訖時間會選擇中轉(zhuǎn)的方式運(yùn)輸。同時，網(wǎng)絡(luò)中運(yùn)營的船舶仍以中小型集裝箱為主，大型集裝箱僅用于遠(yuǎn)距離運(yùn)輸，這是因?yàn)榇笮图b箱船舶在沒有一定的箱量集中時無法體現(xiàn)其規(guī)模效益。各噸級船舶在網(wǎng)絡(luò)中所占比重分別為1 000TEU占10.82%，2 500TEU占16.35%，3 500TEU占22.43%，5 000TEU占25.96%，6 000TEU占11.96%，7 500TEU占7.78%，10 000TEU占4.70%。在優(yōu)化過程中，由于大連港吞吐量大于設(shè)計(jì)通過能力，出現(xiàn)集裝箱放棄在大連港裝卸的現(xiàn)象。本案例采用的通過能力限制條件為設(shè)計(jì)通過能力，所以實(shí)際當(dāng)中大連港還可以裝卸這批箱量。

表4 基于混合優(yōu)化的集裝箱運(yùn)輸路徑優(yōu)化結(jié)果

注：—為直運(yùn)模式。

4 結(jié) 論

著力解決了軸幅式海運(yùn)集裝箱網(wǎng)絡(luò)運(yùn)輸路徑優(yōu)化與船舶配置的復(fù)雜性難題，在分析集裝箱運(yùn)輸成本構(gòu)成的基礎(chǔ)上，構(gòu)建以各集裝箱港口為網(wǎng)絡(luò)節(jié)點(diǎn)，考慮各節(jié)點(diǎn)能力約束限制，基于網(wǎng)絡(luò)綜合運(yùn)輸費(fèi)用最低的海運(yùn)集裝箱網(wǎng)絡(luò)運(yùn)輸路徑優(yōu)化非線性數(shù)學(xué)模型。通過算法之間的比較分析，驗(yàn)證混合優(yōu)化算法的優(yōu)越性以及對大規(guī)模優(yōu)化問題的適用性。研究結(jié)果表明：

1)混合優(yōu)化算法可以有效的求解海運(yùn)集裝箱系統(tǒng)優(yōu)化這一組合優(yōu)化問題，混合優(yōu)化算法比單純的Q-學(xué)習(xí)算法收斂速度慢是由于混沌搜索的隨機(jī)性所致，而其結(jié)果較為精確是由于混沌搜索的遍歷性在起作用。因此，對于要求在短時間內(nèi)做出決策的實(shí)時決策，宜采用Q-學(xué)習(xí)算法，而對優(yōu)化結(jié)果要求嚴(yán)格的優(yōu)化決策，應(yīng)采用混合優(yōu)化算法。

2)采用混合優(yōu)化算法得到的最優(yōu)運(yùn)輸路徑下的總成本比直達(dá)方式運(yùn)輸?shù)目偝杀窘档土?0%。距離較遠(yuǎn)且OD量不大的起訖對間會選擇中轉(zhuǎn)的方式運(yùn)輸以減少運(yùn)營成本。網(wǎng)絡(luò)中運(yùn)營的船舶仍以中小型集裝箱為主，大型集裝箱僅用于遠(yuǎn)距離運(yùn)輸。

3)本模型可檢驗(yàn)?zāi)掣劭诘脑O(shè)計(jì)通過能力是否符合海運(yùn)網(wǎng)絡(luò)對該節(jié)點(diǎn)的要求。例如，在優(yōu)化過程中，大連港由于發(fā)生吞吐量大于設(shè)計(jì)通過能力而使集裝箱放棄在大連港裝卸的現(xiàn)象，因此，2016年，大連港應(yīng)該進(jìn)一步擴(kuò)大港口規(guī)模，以承接來自全球的集裝箱。

[1] IMAI A, SHINTANI K, PAPADIMITRIOU S. Multi-port vs. Hub-and-Spoke port calls by containerships[J].TransportationResearchPartELogistics&TransportationReview, 2009, 45(5): 740-757.

[2] 鐘銘，管峰，余璇，等. 集裝箱班輪軸幅式網(wǎng)絡(luò)區(qū)間模型[J]. 大連海事大學(xué)學(xué)報(bào)， 2014, 40(4): 50-54.

ZHONG Ming, GUAN Feng, YU Xuan, et al. Research on the interval programming for hub-spoke network designing[J].JournalofDalianMaritimeUniversity, 2014, 40(4): 50-54.

[3] 趙宇哲，段浩，匡海波. 考慮CO2排放的軸-轄式集裝箱海運(yùn)網(wǎng)絡(luò)設(shè)計(jì)[J]. 系統(tǒng)工程學(xué)報(bào)， 2015, 30(3): 383-393.

ZHAO Yuzhe, DUAN Hao, KUANG Haibo. Hub-and-spoke container shipping network design based on CO2 emissions[J].JournalofSystemsEngineering, 2015, 30(3): 383-393.

[4] 林天倚.考慮擁堵與環(huán)境成本的軸輻式集裝箱海運(yùn)網(wǎng)絡(luò)樞紐港選擇[D].上海：上海交通大學(xué)，2013.

LIN Tianqi.HubLocationProblemofHub-and-spokeNetworkofLinerShippingServicewithCongestionandEnvironmentalCost[D]. Shanghai: Shanghai Jiao Tong University，2013.

[5] HSIEH S H, CHANG F R. Applications of the hub-and-spoke network model in routing liner ships[J].TransportPlanningJournal, 2001, 30: 871-890.

[6] ALUMUR S, KARA B Y. Network hub location problems: The state of the art[J].EuropeanJournalofOperationalResearch, 2008, 190(1): 1-21.

[7] CETINER S, SEPIL C, SüRAL H. Hubbing and routing in postal delivery systems.[J].AnnalsofOperationsResearch, 2010, 181(1): 109-124.

[8] 吳旗韜, 張虹鷗, 葉玉瑤,等, 基于軸輻網(wǎng)絡(luò)模型的中歐集裝箱航線優(yōu)化[J]. 中山大學(xué)學(xué)報(bào)(自然科學(xué)版), 2012, 51(6): 131-138.

WU Qitao, ZHANG Hongou, YE Yuyao, et al.The Hub-and-spoke container liner route between China and Northwest European[J].ACTAScientriarumNaturaliumUniversiatisSunyatseni, 2012, 51(6): 131-138.

[9] KARLAFTIS M G, KEPAPTSOGLOU K, SAMBRACOS E. Containership routing with time deadlines and simultaneous deliveries and pick-ups[J].TransportationResearchPartELogistics&TransportationReview, 2009, 45(1): 210-221.

[10] BAIRD A J. Optimizing the container transshipment hub location in northern Europe[J].JournalofTransportGeography, 2006, 14(3):195-214.

[11] AZIZI N, CHAUHAN S, SALHI S, et al. The impact of hub failure in hub-and-spoke networks[J].Computers&OperationsResearch, 2016, 65(C):174-188.

[12] JARAMILLO D I, PERAKIS A N. Fleet deployment optimization for liner shipping Part 2 implementation and results[J].MaritimePolicy&Management, 1991, 18(4), 235-262.

[13] MENG Q, WANG S, ANDERSSON H, et al. Containership routing and scheduling in liner shipping: overview and future research directions[J].TransportationScience, 2014, 48(2): 265-280.

[14] PLUM C E M, PISINGER D, SIGURD M M. A service flow model for the liner shipping network design problem[J].EuropeanJournalofOperationalResearch, 2014, 235(2): 378-386.

[15] NG M W. Container vessel fleet deployment for liner shipping with stochastic dependencies in shipping demand[J].TransportationResearchPartBMethodological, 2015, 74: 79-87.