基于航運周期的班輪航線運力配置優(yōu)化＊

靳志宏 李 娜 陳 夢

（大連海事大學(xué)交通運輸管理學(xué)院 大連 116026）

0 引 言

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

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

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

1 建模條件與符號說明

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

文中的符號定義如下：

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

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

2 上、下行航運周期的運力配置優(yōu)化模型

2.1 上行期航線配船與租船聯(lián)合優(yōu)化模型

目標函數(shù)：

約束條件：

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

2.2 下行期航線配船與運力閑置聯(lián)合優(yōu)化模型

目標函數(shù)：

約束條件：

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

3 模擬退火算法求解

航線配船混合整數(shù)規(guī)劃模型是一個典型的組合優(yōu)化問題，也是一個NP－h(huán)ard問題.鑒于此，本文設(shè)計了模擬退火算法以求解現(xiàn)實規(guī)模問題.

3.1 算法中的若干技術(shù)問題

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

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

上行期解的表示形式為

下行期解的表示形式為

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

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

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

3.2 算法流程

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

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

3.3 參數(shù)試驗

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

圖2 上行期參數(shù)試驗結(jié)果

圖3 下行期參數(shù)試驗結(jié)果

4 班輪航線配船聯(lián)合優(yōu)化問題算例分析

4.1 小規(guī)模問題的算法評價

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

表1 小規(guī)模問題與Lingo最優(yōu)解比較 萬美元

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

4.2 現(xiàn)實規(guī)模問題的算法評價

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

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

表2 上行航運周期航線配船結(jié)果

表3 下行航運周期航線配船結(jié)果

5 結(jié)束語

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

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

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

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

［3］李 智，陳明昭，董治德.基于神經(jīng)網(wǎng)絡(luò)的班輪航線配船優(yōu)化方法［J］.交通與計算機，2001，18（90）：34－36.

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

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

［6］金 雁，趙 耀.基于蟻群算法的航線配船［J］.計算機工程與應(yīng)用，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.