靳志宏 李 娜 陳 夢(mèng)

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

0 引 言

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

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

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

1 建模條件與符號(hào)說(shuō)明

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

文中的符號(hào)定義如下：

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

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

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

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

目標(biāo)函數(shù)：

約束條件：

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

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

目標(biāo)函數(shù)：

約束條件：

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

3 模擬退火算法求解

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

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

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

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

上行期解的表示形式為

下行期解的表示形式為

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

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

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

3.2 算法流程

用模擬退火算法求解模型的流程見(jiàn)圖1.

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

3.3 參數(shù)試驗(yàn)

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

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

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

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

4.1 小規(guī)模問(wèn)題的算法評(píng)價(jià)

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

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

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

4.2 現(xiàn)實(shí)規(guī)模問(wèn)題的算法評(píng)價(jià)

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

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

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

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

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

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

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

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

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

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

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

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

［6］金 雁，趙 耀.基于蟻群算法的航線配船［J］.計(jì)算機(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.