考慮船舶航速的船隊(duì)規(guī)劃非線(xiàn)性模型*

楊秋平 謝新連 裴光石

(1.大連海事大學(xué)交通運(yùn)輸管理學(xué)院，遼寧大連116026;2.交通運(yùn)輸部水運(yùn)科學(xué)研究院，北京100088)

船隊(duì)規(guī)劃是一項(xiàng)十分復(fù)雜的系統(tǒng)分析與決策工作，受許多因素的影響，這些影響因素之間往往存在一定的非線(xiàn)性關(guān)系.為了得到更加客觀、可靠的優(yōu)化結(jié)果，考慮非線(xiàn)性因素對(duì)船隊(duì)規(guī)劃決策的影響是十分必要的.船舶航速是船隊(duì)規(guī)劃的影響因素之一，它不僅直接影響到船舶往返航次時(shí)間，而且影響到航次成本的計(jì)算，又由于船舶航速與運(yùn)力配置存在一定的關(guān)系，因此使得船隊(duì)規(guī)劃成為一個(gè)非線(xiàn)性的優(yōu)化問(wèn)題.以往的船隊(duì)規(guī)劃研究忽略了船舶航速的影響，將實(shí)際問(wèn)題簡(jiǎn)化處理為線(xiàn)性模型［1-5］.這類(lèi)模型的成立隱含了一個(gè)假設(shè)，即將船舶航速假設(shè)為常數(shù)，船舶往返航次所需要的時(shí)間和航次成本也是常數(shù).但實(shí)際情況往往并非如此，船舶航速并不是一成不變的［6］.特別是在當(dāng)前的高油價(jià)時(shí)代，飛速增長(zhǎng)的燃料油價(jià)格迫使航運(yùn)企業(yè)努力尋找節(jié)省燃油成本的途徑，普遍使用的方法就是放慢船舶航速.當(dāng)航速變化時(shí)，船舶的往返航次時(shí)間和航次成本就不能再作為定值處理，而應(yīng)是船舶航速的函數(shù).在這種情況下如果仍然套用線(xiàn)性規(guī)劃模型，則求得的最優(yōu)解往往會(huì)偏離實(shí)際情況.為了修正這種偏差，文中在線(xiàn)性規(guī)劃模型的基礎(chǔ)上［7］，考慮船舶航速變化對(duì)船隊(duì)規(guī)劃決策產(chǎn)生的非線(xiàn)性影響，建立了一個(gè)船隊(duì)規(guī)劃非線(xiàn)性模型，并設(shè)計(jì)了模型的求解算法.

1 船隊(duì)規(guī)劃非線(xiàn)性模型

1.1 問(wèn)題描述

以一個(gè)已有船隊(duì)在某一時(shí)刻的狀態(tài)為研究對(duì)象，研究其在復(fù)雜市場(chǎng)環(huán)境下，根據(jù)未來(lái)一段時(shí)間的航線(xiàn)及運(yùn)輸需求預(yù)測(cè)，充分考慮船舶營(yíng)運(yùn)經(jīng)濟(jì)狀況、企業(yè)自身實(shí)力、訂造新船、買(mǎi)賣(mài)二手船和租入、租出船舶等多種實(shí)際可能存在的選擇后，如何逐步調(diào)整船隊(duì)的規(guī)模與結(jié)構(gòu)，制定出合理的船隊(duì)發(fā)展規(guī)劃方案和船舶配線(xiàn)運(yùn)用方案.通過(guò)建立和求解船隊(duì)規(guī)劃數(shù)學(xué)模型，要求對(duì)下列可變因素給出最優(yōu)決策:各年度船舶在各航線(xiàn)上的配置方案;各年度船舶在各航線(xiàn)上的最佳航速;是否購(gòu)買(mǎi)新船，購(gòu)買(mǎi)新船的時(shí)間、船型和數(shù)量;是否購(gòu)買(mǎi)二手船，購(gòu)買(mǎi)二手船的時(shí)間、船型和數(shù)量;是否出售船舶，出售船舶的時(shí)間、船型和數(shù)量;是否租入船舶，租入船舶的時(shí)間、船型、數(shù)量和租期是否租出船舶，租出船舶的時(shí)間、船型、數(shù)量和租期;是否閑置船舶，閑置船舶的船型、數(shù)量.

1.2 船舶航速關(guān)系式構(gòu)建

通過(guò)分析船舶航速變化對(duì)船隊(duì)規(guī)劃決策產(chǎn)生的非線(xiàn)性影響，構(gòu)建船舶航速與船舶往返航次時(shí)間、航次成本以及航線(xiàn)配船數(shù)量三者之間的數(shù)學(xué)關(guān)系式.

1.2.1 船舶航速與船舶往返航次時(shí)間的關(guān)系

船舶往返航次時(shí)間為船舶航次航行時(shí)間與船舶在港停泊時(shí)間之和，其表達(dá)式為

式中，Tjht為第t年j型船在h航線(xiàn)上的往返航次時(shí)間為第t年j型船在h航線(xiàn)上的航次航行時(shí)間，為第t年j型船在h航線(xiàn)上的在港停泊時(shí)間.

(1)航次航行時(shí)間

第t年j型船在h航線(xiàn)上的往返航次Tjht航行時(shí)間為h航線(xiàn)的距離Lh與第t年j型船在h航線(xiàn)上的航行速度zjht的商.考慮到船舶壓載時(shí)的航速比滿(mǎn)載時(shí)略快，假設(shè)船舶的壓載航速比滿(mǎn)載航速提高δ倍，則去程時(shí)的航行時(shí)間為，回程時(shí)的航行時(shí)間為，船舶往返航次的總航行時(shí)間為

(2)在港停泊時(shí)間

其中:Dj為j型船的額定裝載量;θjht為第t年j型船在h航線(xiàn)上的裝載率;分別為h航線(xiàn)上裝貨港和卸貨港的作業(yè)效率，t/d.

綜上得出，

1.2.2 船舶航速與航次成本的關(guān)系

航次成本主要包括燃料費(fèi)用、港口費(fèi)用、運(yùn)河費(fèi)用3部分，其表達(dá)式為

式中，Cjbht為在第t年時(shí)b年建造的j型船在h航線(xiàn)上的航次成本為在第t年時(shí)b年建造的j型船在h航線(xiàn)上每航次的燃料費(fèi)用為第 t年 j型船在h航線(xiàn)上每航次的港口裝卸費(fèi)用為第 t年 j型船在h航線(xiàn)上每航次的運(yùn)河費(fèi).

(1)航次燃料費(fèi)用

船舶每天的燃料油費(fèi)用為船舶每天燃料油消耗量與燃料油市場(chǎng)價(jià)格的乘積，其表達(dá)式為

式中，mjbht為在第t年時(shí)b年建造的j型船在h航線(xiàn)上航行時(shí)每天的燃料油消耗量為第t年燃料油的年均市場(chǎng)價(jià)格.

設(shè)船舶航速與燃料油消耗量之間的關(guān)系為mjbht則

式中，ajb為b年建造的j型船燃料油消耗常數(shù)，又稱(chēng)船舶機(jī)能系數(shù)，zjht為第t年j型船在h航線(xiàn)上的航速.

式中，gjbht為在第t年時(shí)b年建造的j型船在h航線(xiàn)上航行時(shí)每天的柴油消耗量，pgt為第t年柴油的年均市場(chǎng)價(jià)格.

(2)港口費(fèi)用

港口費(fèi)用主要包括在港發(fā)生的與貨物相關(guān)的裝卸費(fèi)用和與船舶相關(guān)的各項(xiàng)費(fèi)用，其表達(dá)式為

式中，fh為在h航線(xiàn)上港口平均每噸貨物的裝卸費(fèi)用.

在港發(fā)生的與船舶相關(guān)的費(fèi)用主要包括:船舶噸稅、停泊費(fèi)、引航費(fèi)、拖輪費(fèi)、開(kāi)關(guān)艙費(fèi)等.

綜上得出航次成本的表達(dá)式為

1.2.3 船舶航速與航線(xiàn)配船數(shù)的關(guān)系

航線(xiàn)配船數(shù)與船舶年航次數(shù)之間可通過(guò)往返航次時(shí)間建立如下關(guān)系式:

式中，yjbht為第t年在h航線(xiàn)上配置的b年建造的j型船的年航次數(shù)，Tj為j型船的年可營(yíng)運(yùn)時(shí)間，xjbht為第t年在h航線(xiàn)上配置的b年建造的j型船的數(shù)量.

將式(6)代入式(15)中，得到船舶航速與航線(xiàn)配船數(shù)之間的關(guān)系式如下:

1.3 基本假設(shè)與參數(shù)定義

(1)基本假設(shè)

(2)變量與參數(shù)定義

決策變量如下:ojbt，第t年閑置b年建造的j型船的數(shù)量;sjbt，第t年購(gòu)買(mǎi)b年建造的j型船的數(shù)量;wjbt，第t年出售b年建造的j型船的數(shù)量;ujbdt，第t年租入b年建造的j型船的數(shù)量，租期為d年;vjbdt，第t年租出b年建造的j型船的數(shù)量，租期為d年.

參數(shù)如下:Hjht，第t年 j型船在h航線(xiàn)上的運(yùn)價(jià);Pjbdt，第t年租賃租期為d年的b年建造的j型船的租金;Ejbt，在第t年時(shí)b年建造的j型船的售價(jià);Fjbt，在第t年時(shí)b年建造的j型船的年度閑置費(fèi)用;Ajb，在研究期之初船隊(duì)中擁有的b年建造的j型船的數(shù)量;Wjb，b年建造的j型船在研究期末的回收價(jià)值;WTht，第t年h航線(xiàn)上的最大貨物運(yùn)輸需求量;Qjbt，在研究期之初擁有的需于第t年末退租的b年建造的j型租賃船的數(shù)量;Mt，第t年船舶融資限額;Njbt，第t年市場(chǎng)上可供租賃的b年建造的j型船的數(shù)量;B0，在研究期之初船隊(duì)中擁有的最老船舶的建造時(shí)間，B0≤0;i0，考慮資金時(shí)間價(jià)值的折現(xiàn)率;α，買(mǎi)船代理費(fèi)占售價(jià)的百分比;μ，船舶租出的傭金占租金的百分比;β，對(duì)研究期末船隊(duì)實(shí)物價(jià)值的重視程度系數(shù)，0≤β≤1;K，船型總數(shù);G，航線(xiàn)總數(shù);N，研究期年數(shù);NT，船舶的壽命期;Rt，第t年?duì)I運(yùn)的航線(xiàn)集合;Φht，第t年可在航線(xiàn)h上營(yíng)運(yùn)的船型集合.

1.4 船隊(duì)規(guī)劃數(shù)學(xué)模型

船隊(duì)規(guī)劃的非線(xiàn)性模型如下.

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

約束條件:

sjbt，wjbt，vjbdt，ujbdt≥0 且取整，

2 算法求解

上述模型是一個(gè)混合整數(shù)非線(xiàn)性規(guī)劃(MINLP)模型，它同時(shí)包含整數(shù)型變量和連續(xù)型變量，且目標(biāo)函數(shù)和約束條件均具有非線(xiàn)性.針對(duì)模型的這些特點(diǎn)，文中對(duì)標(biāo)準(zhǔn)粒子群優(yōu)化算法進(jìn)行改進(jìn)，利用基于可行性規(guī)則的更新策略，結(jié)合模擬退火(SA)的局部搜索技術(shù)，提出一種混合粒子群優(yōu)化(HPSO)算法用于求解該模型.

(1)混合粒子群優(yōu)化算法的設(shè)計(jì)思想

(a)pi(t)不可行，而zi(t+1)可行;

(b)pi(t)和zi(t+1)均可行，且F(zi(t+1))＜f(pi(t));

(c)pi(t)和zi(t+1)均不可行，且viol(zi(t+1))＜viol(pi(t)).

由于在HPSO算法中采用了基于可行性規(guī)則的更新策略，種群會(huì)過(guò)早集中到幾個(gè)可行解附近，從而陷入局部最優(yōu).為了幫助種群跳出局部最優(yōu)值，采用結(jié)合SA的局部搜索技術(shù)對(duì)第t代種群的最優(yōu)位置pg進(jìn)行更新［11］.從pi中選取一個(gè)位置p'g來(lái)代替更新公式中的pg，則HPSO的速度更新公式為

將SA算法中計(jì)算溫度T時(shí)pi相對(duì)pg的突跳概率 e－［F(pi)－F(pg)］/T作為 pi的適配值，則 pi替代 pg的概率為

式中，F(xiàn)(x)為目標(biāo)函數(shù);n為種群大小.

初溫和退火采用如下方式:

式中:F(pg)為初始種群中最佳粒子的目標(biāo)值，λ為退溫常數(shù).

(2)混合粒子群優(yōu)化算法的步驟

混合粒子群優(yōu)化算法的步驟如下:

3 仿真計(jì)算與分析

以某航運(yùn)公司在未來(lái)兩年內(nèi)的船隊(duì)規(guī)劃問(wèn)題為例，其基本情況見(jiàn)表1－7.假設(shè)該公司擁有2種船型的船隊(duì)，各型船的年可營(yíng)運(yùn)時(shí)間為345 d，壽命期限為20a;規(guī)定新購(gòu)置船舶的船齡不允許超過(guò)3a;各年各型船的租賃上限為10艘.研究期內(nèi)營(yíng)運(yùn)2條航線(xiàn)，各年各型船在各航線(xiàn)的平均裝載率為97%;研究期內(nèi)各年的計(jì)劃融資額為25000萬(wàn)美元.根據(jù)每年各航線(xiàn)上的貨運(yùn)量預(yù)測(cè)結(jié)果，求出船隊(duì)在未來(lái)兩年內(nèi)的最優(yōu)建設(shè)和船舶調(diào)配方案.取i0=8%，α=3%，β=1，μ=1.25%，δ=5%.

根據(jù)上述參數(shù)，利用HPSO算法對(duì)模型進(jìn)行求解，得到船隊(duì)規(guī)劃的優(yōu)化結(jié)果如表8、9所示.

從優(yōu)化結(jié)果可以看出，考慮船舶航速影響的船隊(duì)規(guī)劃非線(xiàn)性模型不僅可以求解出船隊(duì)發(fā)展方案和航線(xiàn)配船方案，而且可以計(jì)算出船舶每年在各航線(xiàn)上航行的最佳航速.該模型較全面地考慮了影響船舶營(yíng)運(yùn)成本的主要因素，如:燃料費(fèi)、運(yùn)河費(fèi)、港口使費(fèi)等，反映了船舶航速變化對(duì)船隊(duì)規(guī)劃產(chǎn)生的非線(xiàn)性影響，優(yōu)化結(jié)果更加符合船隊(duì)營(yíng)運(yùn)的實(shí)際情況.

為了進(jìn)一步驗(yàn)證非線(xiàn)性模型的優(yōu)勢(shì)，文中根據(jù)所給參數(shù)，利用線(xiàn)性規(guī)劃模型［7］對(duì)該算例進(jìn)行計(jì)算，得到船隊(duì)規(guī)劃的優(yōu)化結(jié)果如表10、11所示.

將非線(xiàn)性模型與線(xiàn)性規(guī)劃模型的優(yōu)化結(jié)果進(jìn)行對(duì)比發(fā)現(xiàn):非線(xiàn)性模型求出的目標(biāo)函數(shù)值與線(xiàn)性規(guī)劃模型相比增加了2.63%;非線(xiàn)性模型與線(xiàn)性規(guī)劃模型求出的船舶調(diào)配優(yōu)化方案均可以實(shí)現(xiàn)全部的貨物運(yùn)輸需求任務(wù)，線(xiàn)性規(guī)劃模型的方案閑置了部分船舶，而非線(xiàn)性模型的方案各年各型船的閑置數(shù)量均為0，提高了船舶的利用率.因此，考慮船舶航速影響的船隊(duì)規(guī)劃非線(xiàn)性模型的優(yōu)化結(jié)果比線(xiàn)性規(guī)劃模型更客觀、更科學(xué).

表1 研究期前船隊(duì)構(gòu)成狀況Table 1 Fleet composition at beginning of the research horizon

表2 各型船在各航線(xiàn)上的往返航次時(shí)間Table 2 Round voyage time of various types of ships on each route d

表3 各型船在各航線(xiàn)上的航次毛收益Table 3 Voyage gross profit of various types of ships on each route

表4 各年各航線(xiàn)的運(yùn)輸需求量Table 4 Transport demand on each route per year萬(wàn)t

表5 各年各型船的售價(jià)、租金、閑置費(fèi)用Table 5 Prices，rents and lay-up costs of various types of ships per year

表6 各型船的燃料油消耗常數(shù)Table 6 Constants of fuel consumption for various types of ships

表7 其他模型參數(shù)Table 7 Other parameters of model

表8 最優(yōu)船隊(duì)發(fā)展策略1)Table 8 Optimal fleet development strategy

表9 最優(yōu)船舶調(diào)配方案Table 9 Optimal ship deployment scheme

表10 船隊(duì)發(fā)展優(yōu)化策略1)Table 10 Optimized fleet development strategy

表11 船舶調(diào)配優(yōu)化方案Table 11 Optimized ship deployment scheme

4 結(jié)語(yǔ)

考慮到船舶航速在決定運(yùn)力配置與費(fèi)用方面的重要作用，以及船舶往返航次時(shí)間和航次成本因船舶航速的變化而不能作為常量處理所引起的非線(xiàn)性影響，推導(dǎo)了船舶航速與船舶往返航次時(shí)間、航次成本及航線(xiàn)配船數(shù)之間的數(shù)學(xué)關(guān)系式，建立了船隊(duì)規(guī)劃非線(xiàn)性模型.針對(duì)模型非線(xiàn)性和混合整數(shù)解的特點(diǎn)，設(shè)計(jì)了混合粒子群優(yōu)化算法進(jìn)行求解.通過(guò)仿真實(shí)驗(yàn)將非線(xiàn)性模型與線(xiàn)性模型的優(yōu)化結(jié)果進(jìn)行比較分析.結(jié)果表明，非線(xiàn)性模型可以同時(shí)決策船隊(duì)投資、航線(xiàn)配船、船舶航速問(wèn)題，其優(yōu)化結(jié)果更符合實(shí)際情況.

實(shí)際上，船隊(duì)規(guī)劃的非線(xiàn)性影響因素不僅僅是船舶航速，許多因素都會(huì)在不同程度上產(chǎn)生非線(xiàn)性的影響，因此分析和評(píng)價(jià)非線(xiàn)性因素對(duì)船隊(duì)規(guī)劃的影響程度將是今后進(jìn)一步研究的方向.

［1］Christiansen M，F(xiàn)agerholt K，Ronen D.Ship routing and scheduling:status and perspectives［J］.Transportation Science，2004，38(1):1-18.

［2］楊秋平，謝新連，趙家保.船隊(duì)規(guī)劃研究現(xiàn)狀與動(dòng)態(tài)［J］.交通運(yùn)輸工程學(xué)報(bào)，2010，10(4):85-90.Yang Qiu-ping，Xie Xin-lian，Zhao Jia-bao.Research status and prospect of ship fleet planning［J］.Journal of Traffic and Transportation Engineering，2010，10(4):85-90.

［3］謝新連，李樹(shù)范，紀(jì)卓尚.船隊(duì)規(guī)劃的線(xiàn)性模型研究與應(yīng)用［J］.中國(guó)造船，1989(3):59-66.Xie Xin-lian，Li Su-fan，Ji Zhuo-shang.Study and application on the linear model of fleet planning［ J］.Shipbuilding of China，1989(3):59-66.

［4］Xie X，Ji Z，Yang Y.Nonlinear programming for fleet planning［J］.International Shipbuilding Progress，1993，40(421):93-103.

［5］楊秋平，謝新連，蘇晨.需求不確定下船隊(duì)規(guī)劃決策的魯棒優(yōu)化模型［J］.華南理工大學(xué)學(xué)報(bào):自然科學(xué)版，2010，38(3):82-88.Yang Qiu-ping，Xie Xin-lian，Su Chen.Robust optimization model for fleet planning under demand uncertainty［J］.Journal of South China University of Technology:Natural Science Edition，2010，38(3):82-88.

［6］謝新連.船舶調(diào)度與船隊(duì)規(guī)劃方法［M］.北京:人民交通出版社，2000.

［7］楊秋平，謝新連.多種類(lèi)型投資的船隊(duì)規(guī)劃模型［J］.上海海事大學(xué)學(xué)報(bào)，2010，31(1):61-66.Yang Qiu-ping，Xie Xin-lian.Fleet planning model based on multi-type of investment［J］.Journal of Shanghai Maritime University，2010，31(1):61-66.

［8］祁輝，熊鷹，周樹(shù)民.基于粒子群算法的整數(shù)規(guī)劃問(wèn)題的求解算法［J］.江漢大學(xué)學(xué)報(bào):自然科學(xué)版，2009，37(1):26-29.Qi Hui，Xiong Ying，Zhou Shu-min.Solution to integer programming problem based on particle swarm optimization ［J］.Journal of Jianghan University:Natural Science，2009，37(1):26-29.

［9］譚瑛，高慧敏，曾建潮.求解整數(shù)規(guī)劃問(wèn)題的微粒群算法 ［J］.系統(tǒng)工程理論與實(shí)踐，2004，24(5):126-129.Tan Ying，Gao Hui-min，Zeng Jian-chao.Particle swarm optimization for integer programming［J］.System Engineering Theory Practice，2004，24(5):126-129.

［10］王凌，劉波.微粒群優(yōu)化與調(diào)度算法［M］.北京:清華大學(xué)出版社，2008.

［11］龔純，王正林.精通MATLAB最優(yōu)化計(jì)算［M］.北京:電子工業(yè)出版社，2009.