基于航運周期的班輪航線運力配置優化＊

靳志宏 李 娜 陳 夢

（大連海事大學交通運輸管理學院 大連 116026）

0 引 言

全球經濟危機使國際貿易受到重創，很多船公司吸納不到足夠的貨物，市場上運力過剩，加上航運業的退出機制比較緩慢，全球航運企業無不面臨嚴峻的考驗.在這種形勢下，如何將不同的船舶配置到不同的班輪航線上，對提高船隊運輸經濟效益和整體結構優化尤為重要.介于此，本文根據航運周期內不同階段的市場運力需求情況將航運周期劃分為上行期和下行期.航運上行期市場景氣，運量需求大于運力，運價上仰，班輪公司為獲取更多利潤，鞏固并擴大自己的市場份額，可以向其他船東租進船舶來營運.下行期，船公司可以將一部分船舶閑置，合理的進行封存，避免更大的損失.本文研究的即是處于航運上行期的多航線多船型配船與租船的聯合優化問題；以及處于航運下行期的多船型多航線配船與運力閑置的聯合優化問題.

學術界對航線配船問題進行了多方研究并提出了多種解決方法.謝新連［1］基于線性規劃方法對給定的船隊和運輸任務求解年度最優航線配船.楊華龍等［2］建立了以船公司總凈收益為目標函數的線性規劃模型.李智等［3］利用神經網絡算法求解班輪航線配船問題并進行了仿真計算.趙剛［4］在此基礎上，改進了班輪航線配船模型，并給出了新模型的求解方法及收斂性證明.蘇紹娟等［5］提出了改進的粒子群優化算法.金雁等［6］將航線配船問題轉化為類似的旅行商問題，用蟻群算法求解.Bronmo等［7］構造了一個航線配船主問題和一個基于此主問題的子問題.

上述文獻中設計的航線配船問題均僅考慮單程運輸，且定義在整個航運周期的上行期，均未考慮往返雙向的貨運需求，也未考慮航運周期處于下行期的決策環境的變化.本文針對航運的周期性特征，研究了處于整個航運周期上行期的多航線多船型配船與租船的聯合優化問題、以及處于航運周期下行期的多航線多船型配船與運力閑置的聯合優化問題，且同時考慮了往返雙向的貨運需求.

1 建模條件與符號說明

本文假設以期租的方式租船，待配置船舶的營運性能、技術性能、航線的貨運任務、以及港口條件等都是相適應的，每艘集裝箱船舶在兩港之間往返運輸，不考慮中途掛靠港口或加載集裝箱等因素.

文中的符號定義如下：

航線集合C＝｛j｜j＝1，2，…，n｝；公司現有的船舶種類集合V＝｛i｜i＝1，2，…，m｝；租船市場可供租用的船舶類型集合V′＝｛i｜i＝m＋1，m＋2，…，m＋z｝，即第m＋1至m＋z型船為可租用船舶類型；第i種船舶的數量是Si；Wi是第i種船型的裝載量；參數tij是一艘i型船在第j條航線上一年可完成的最大往返航次數；Kij為一艘i型船舶在第j條航線上完成一個往返航次所花費的成本；T為規劃期；L為船公司規劃期內的利潤；Ri為i型船在規劃期內的期租租金；Ii為i型船在規劃期內的閑置費用；Fi為是每艘i型船在規劃期內的固定成本；Qj1和Qj2分別是第j條航線上規劃期內正、反向貨運量預測值（TEU）；Pj1和Pj2分別為第j條航線上正、反兩向每單位運量（TEU）的運費收入，即運費率.

決策變量xij為分配到第j條航線上的i型船的艘數；zi為i型船的閑置數量.

2 上、下行航運周期的運力配置優化模型

2.1 上行期航線配船與租船聯合優化模型

目標函數：

約束條件：

在上行航運周期中，公司現有的船舶均投入運營，如何分配船舶與固定成本無關.期租租進的船舶只需按期支付租金，固定費用已包含在租金內.因此為避免冗余，模型的目標函數（1）不考慮船舶固定成本，只考慮收益與航次成本和租金的差值利潤.式（2）～（5）是模型的約束條件，式（2）為船舶數量約束，式（3）和式（4）是運力滿足正、反向運量需求.式（5）為變量自身約束.

2.2 下行期航線配船與運力閑置聯合優化模型

目標函數：

約束條件：

在下行期，船舶封存后，固定成本中的營運成本節約了，但發生了諸如港口費、保養費用、看船人員工資等相關成本，在本文統一納入閑置費用Ii.因此下行期的目標函數式（6）需要考慮固定成本和閑置成本.式（7）～（10）對應于（2）～（5），作為相應的下行期約束條件.

3 模擬退火算法求解

航線配船混合整數規劃模型是一個典型的組合優化問題，也是一個NP－hard問題.鑒于此，本文設計了模擬退火算法以求解現實規模問題.

3.1 算法中的若干技術問題

算法中符號定義如下：LL為模擬退火算法目標函數；X為模型的解；T為系統的溫度；ΔL為兩個目標函數的差值；M為充分大的數；δ為任取兩個解的目標函數值之差；lk為模擬退火算法第k次迭代時馬爾科夫鏈的長度；v為算法中的迭代步長.

航線配船問題的目標函數為求最大值，將其轉化為模擬退火算法的最小值問題：LL＝M－L.

上行期解的表示形式為

下行期解的表示形式為

在下行期解的表示中，設置第j＝0條航線為虛擬航線，閑置的船舶分配到這條航線上，即當j＝0時xij表示的意義為：第i型船閑置的數目.

新解的產生機制是在定義域范圍內，隨機產生一個i和一個j，對應的解分量為x（i，j），然后利用隨機產生裝置產生一個新解x′（i，j），使x′（i，j）∈［x（i，j）－1，x（i，j）＋1］.針對新解x′（i，j）計算新的目標函數值LL′，如果x′（i，j）滿足船舶運力與運量約束條件而且LL′＜LL，則接受新解，若LL′≥LL，則按照概率e（－ΔL／T）接受新解.

初始溫度設為T0＝Mδ.設α是一個介于0與1之間的常數，降溫規則取Tk＋1＝αTk.設β是系數，則馬爾科夫鏈增長的方式為lk＋1＝βlk.當系統溫度小于或等于停止溫度Tf時，算法停止.

3.2 算法流程

用模擬退火算法求解模型的流程見圖1.

圖1 模擬退火算法求解流程圖

3.3 參數試驗

冷卻進度表共有5個參數需要確定，分別為初始溫度的參數M、停止溫度Tf、溫度衰減系數α，以及馬爾可夫鏈長度的初始長度l0和增長系數β.以一個3種船型共20艘船舶6條航線的配船問題為例，針對要試驗的參數選取不同的組合值，分別計算目標函數值，圖2，3中橫坐標分別對應參數的其他4個試驗值.參數的選取原則是選擇能得到質量最優的參數組合，經過試驗發現，在上行期，當M＝20，Tf＝0.1，α＝0.9，β＝1.1，l0＝90時算法可以達到最優；在下行期，當M＝10，Tf＝0.5，α＝0.9，β＝1.15，l0＝90時算法可以達到最優，因此分別將其作為上、下行期航線配船問題的模擬退火算法的參數.

圖2 上行期參數試驗結果

圖3 下行期參數試驗結果

4 班輪航線配船聯合優化問題算例分析

4.1 小規模問題的算法評價

用模擬退火算法對上述小規模航線配船問題進行求解，與Lingo軟件求得的最優解對比，對比結果見表1.

表1 小規模問題與Lingo最優解比較 萬美元

從表中結果可見，在上行期，模擬退火算法的解僅比精確解差2.81%，下行期結果完全相同.從處理的時間上看，模擬退火算法耗時更短.顯示了本文設計的模擬退火算法能較好的收斂到近似最優解.

4.2 現實規模問題的算法評價

為了進一步考查算法的實用性，以某船公司的現實規模的運力配置問題為例進行仿真實驗.該公司擁有6種噸位的集裝箱船舶共100艘，分別是1 500TEU的10艘、1 400TEU的15艘、1 000TEU的20艘、850TEU的17艘、800TEU的20艘、500TEU的18艘，現開辟班輪航線10條，市場上有2種類型可供租用的船舶.

用上述混合整數規劃模型與模擬退火算法求得航線配船結果見表2～3.表中數據代表某一船型在某一航線配置的數量.上行期目標函數值152 208萬美元，下行期目標函數值59 158萬美元.

表2 上行航運周期航線配船結果

表3 下行航運周期航線配船結果

5 結束語

本文基于客觀存在的航運的周期性特征，分別針對處于航運上行期的多航線多船型配船與租船的聯合優化問題、以及處于航運下行期的多航線多船型配船與運力閑置的聯合優化問題，構建了混合整數規劃模型，基于模型特點開發了相應的模擬退火算法，通過小規模問題實驗確定了模型與算法參數，并通過與Lingo最優解的對比，顯示了模型及算法的有效性.同時，大規模現實問題的算例分析也進一步驗證了算法的實用性，可為集裝箱班輪航線運力配置提供決策支持.

進一步的研究將考慮具有中途掛靠港口或者加載集裝箱等因素，即船舶在3個及3個以上港口之間往返運輸的運力配置優化問題.

［1］謝新連.船隊規劃的動態模型與算法［J］.中國造船，1992（3）：102－130.

［2］楊華龍，鐘 銘.集裝箱班輪航線配船優化決策研究［J］.大連海事大學學報，1996，22（3）：51－54.

［3］李 智，陳明昭，董治德.基于神經網絡的班輪航線配船優化方法［J］.交通與計算機，2001，18（90）：34－36.

［4］趙 剛.班輪航線配船模型的分析與改進［J］.系統工程學報，1997，12（1）：80－86.

［5］蘇紹娟，王麗錚，王呈方.不確定性航線配船數學模型建模方法［J］.航海工程，2007，36（4）：99－103.

［6］金 雁，趙 耀.基于蟻群算法的航線配船［J］.計算機工程與應用，2007，43（25）：231－233.

［7］Br?nmo G，Nygreen B，Lysgaard J.Column generation approaches to ship scheduling with flexible cargo sizes［J］.European Journal of Operational Research，2010，200（1）：139－150.