基于節點限制的軸幅式集裝箱海運網絡優化設計

張 祺，彭 云，王文淵，宋向群，郭子堅

(大連理工大學 建設工程學部，遼寧 大連 116024)

0 引 言

隨著國際集裝箱運輸快速增長和船舶大型化的發展趨勢，多港掛靠的航線結構在船舶利用率以及運輸經濟性方面均存在不足，軸輻式網絡結構因其規模經濟效益，已成為班輪公司關注的焦點[1-2]。如丹麥的馬士基航運先后在地中海和東亞地區完成了軸輻式網絡的建設，地中海沿岸的集裝箱經過阿爾赫西拉斯港中轉，東亞地區的集裝箱通過髙雄港中轉[3]。船舶的大型化必然要求減少掛靠的港口數量以提高船舶公司的經濟性，集裝箱船在主航線上停靠的港口將越來越少，港口的“樞紐”特征將更加突出。軸輻式網絡結構通過集中集裝箱流在樞紐港口，利用大型集裝箱船集中運輸，使船隊和航線產生規模經濟，降低了集裝箱的單位運營成本[4]。因此，如何科學設計集裝箱運輸路徑并匹配適宜船型來實現軸幅式網絡的經濟效益是船舶公司關注的重點，也是筆者所要解決的問題。

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

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

1 問題描述

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

圖1 軸幅式集裝箱海運網絡Fig.1 Hub-and-spoke container shipping network

2 模型的構建與求解

2.1 模型假設

集裝箱海運網絡運輸是一個復雜的過程，需對海運網路設計問題作出如下假設：

假設1：集裝箱海運網絡結構相對穩定，不考慮突發事件等不確定性因素的影響；

假設2：模型中不考慮重箱、空箱和租賃箱成本的區別。

假設3：模型中所有起訖港口之間的集裝箱流量為己知，可根據各港口吞吐量及腹地經濟水平進行預測。

假設4：軸幅式集裝箱海運網絡由若干條干線和支線組成，不考慮各國沿海運輸權的限制。

假設5：軸幅式集裝箱海運網絡中各節點均能通過航線相連。

2.2 集裝箱運輸成本分析

海運集裝箱運輸成本是船舶公司在各港口起訖對之間運輸集裝箱的全過程中產生的費用總和，分為船舶成本和港口成本兩部分。船舶成本是指在運輸過程中船舶發生的各項費用，包括經常性維護費用、燃料成本和資本成本；港口成本是指船舶進出港口發生的各種使用費用，包括船舶噸稅、停泊費、引航費、拖輪費、裝卸費等。

2.2.1 船舶成本

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

(1)

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

(2)

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

(3)

2.2.2 港口成本

港口成本包括船舶進港費用(引航費、移泊費、系解纜費、停泊費統稱為進港費用)和裝卸費用，如式(4)。

(4)

2.2.3 海運網絡總成本

(5)

因此，對于集裝箱海運網絡G(N,A)，網絡總運輸成本CT如式(6)。

(6)

2.3 模型構建

建立以海運集裝箱運輸總成本最小為目標的數學模型，模型的目標函數如式(7)。

(8)

(9)

式中：Pi為港口節點i的年極限通過能力。

2.4 模型求解

海運集裝箱網絡的優化模型規模十分龐大，網絡內各港口節點不相互獨立，任一港口節點的變化均會對整個海運網絡產生影響，從而影響模型求解。隨著網絡節點的增多，問題處理規模呈現指數性增長，傳統線性方法幾乎無法求解，因此采用結合混沌優化方法的Q-學習算法求解海運集裝箱運輸路徑優化問題。

(10)

模型的求解可分為兩部分，一部分是運用優化算法計算集裝箱運輸路徑，另一部分是在前一步的基礎上，求解各港口之間的運輸集裝箱的船型服務頻率，最終才能確定當前解對應的運輸成本。混合優化算法流程如圖2，具體流程如下：

圖2 混合優化算法流程Fig. 2 Process of hybrid optimization algorithm

Step1:確定集裝箱海運網絡規模，預測集裝箱重箱OD量，初始化Q表、混沌變量；

Step2:選擇中轉港，確定模型的一個可行解；

Step3:驗證各港口的吞吐量是否在極限通過能力的容許范圍內，若在，進行下一步，否則，超限的路徑的回報r取-|rn-1|，執行Step 7；

Step4:根據可行解確定每兩個節點間的集裝箱流量；

Step5:根據每兩節點間的實際箱流量確定成本最低的船型與頻率組合；

Step6:根據式(10)計算該可行解的總運輸成本，計算回報r；

Step7:更新Q表，并驗證Q值是否收斂，若是，尋優結束，輸出當前最優解，否則返回Step 2；

3 實例分析

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

表1 外貿港口集裝箱運輸網絡節點

3.1 模型輸入參數

環渤海地區外貿集裝箱運輸網絡采用7種船型，分別為1 000TEU，2 500TEU，3 500TEU，5 000TEU，6 000TEU，7 500TEU，10 000TEU。

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

3.2 結果分析

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

將集裝箱運輸網絡有向圖、各港口間2016年集裝箱OD量預測值、各成本參數及各港口間的實際海運距離等輸入數據代入模型算法程序中進行優化計算，分別運用混合優化、混沌優化、Q-學習算法求解模型計算結果如表3。

表2 2016年15個港口的集裝箱OD預測

表3 港口集裝箱運輸網絡綜合成本優化結果

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

混合優化算法求得的集裝箱運輸路徑選擇方案如表4。由表4可以看出，大部分箱量都選擇直達的方式運輸，但距離較遠且OD量不大的起訖時間會選擇中轉的方式運輸。同時，網絡中運營的船舶仍以中小型集裝箱為主，大型集裝箱僅用于遠距離運輸，這是因為大型集裝箱船舶在沒有一定的箱量集中時無法體現其規模效益。各噸級船舶在網絡中所占比重分別為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%。在優化過程中，由于大連港吞吐量大于設計通過能力，出現集裝箱放棄在大連港裝卸的現象。本案例采用的通過能力限制條件為設計通過能力，所以實際當中大連港還可以裝卸這批箱量。

表4 基于混合優化的集裝箱運輸路徑優化結果

注：—為直運模式。

4 結 論

著力解決了軸幅式海運集裝箱網絡運輸路徑優化與船舶配置的復雜性難題，在分析集裝箱運輸成本構成的基礎上，構建以各集裝箱港口為網絡節點，考慮各節點能力約束限制，基于網絡綜合運輸費用最低的海運集裝箱網絡運輸路徑優化非線性數學模型。通過算法之間的比較分析，驗證混合優化算法的優越性以及對大規模優化問題的適用性。研究結果表明：

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

2)采用混合優化算法得到的最優運輸路徑下的總成本比直達方式運輸的總成本降低了10%。距離較遠且OD量不大的起訖對間會選擇中轉的方式運輸以減少運營成本。網絡中運營的船舶仍以中小型集裝箱為主，大型集裝箱僅用于遠距離運輸。

3)本模型可檢驗某港口的設計通過能力是否符合海運網絡對該節點的要求。例如，在優化過程中，大連港由于發生吞吐量大于設計通過能力而使集裝箱放棄在大連港裝卸的現象，因此，2016年，大連港應該進一步擴大港口規模，以承接來自全球的集裝箱。

[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] 鐘銘，管峰，余璇，等. 集裝箱班輪軸幅式網絡區間模型[J]. 大連海事大學學報， 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排放的軸-轄式集裝箱海運網絡設計[J]. 系統工程學報， 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] 林天倚.考慮擁堵與環境成本的軸輻式集裝箱海運網絡樞紐港選擇[D].上海：上海交通大學，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] 吳旗韜, 張虹鷗, 葉玉瑤,等, 基于軸輻網絡模型的中歐集裝箱航線優化[J]. 中山大學學報(自然科學版), 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.