復(fù)雜情況下大規(guī)模船隊(duì)規(guī)劃模型與求解方法＊

楊秋平 謝新連 裴光石

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

船隊(duì)規(guī)劃是航運(yùn)企業(yè)發(fā)展戰(zhàn)略中的一項(xiàng)重要決策，是決定企業(yè)能否長(zhǎng)期生存發(fā)展的關(guān)鍵問(wèn)題.通過(guò)對(duì)船隊(duì)規(guī)劃及相關(guān)文獻(xiàn)的查閱分析發(fā)現(xiàn)［1－6］，目前傳統(tǒng)船隊(duì)規(guī)劃方法對(duì)于解決變量較少、約束條件較少且變量之間呈線性關(guān)系的船隊(duì)規(guī)劃研究和應(yīng)用比較成熟［7］，但對(duì)于多航線、多型船、大規(guī)模的船隊(duì)規(guī)劃問(wèn)題研究仍不是很理想.因此，船隊(duì)規(guī)劃的研究工作需要進(jìn)一步改進(jìn)和完善.本文針對(duì)船隊(duì)規(guī)劃問(wèn)題規(guī)模大、影響因素復(fù)雜、要求整數(shù)解等一系列特點(diǎn)，提出了復(fù)雜情況下大規(guī)模船隊(duì)規(guī)劃模型與求解算法，為解決這類(lèi)實(shí)際問(wèn)題提供了一種新方法.

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

1.1 問(wèn)題描述

針對(duì)一個(gè)擁有多種類(lèi)型船舶的大型船隊(duì)，以船隊(duì)在某一時(shí)刻的狀態(tài)為起點(diǎn)，根據(jù)未來(lái)一段時(shí)間的航運(yùn)市場(chǎng)行情預(yù)測(cè)研究在復(fù)雜市場(chǎng)環(huán)境下考慮船舶營(yíng)運(yùn)經(jīng)濟(jì)狀態(tài)、企業(yè)投資能力、多種類(lèi)型投資方式等影響因素，如何逐步調(diào)整船隊(duì)的規(guī)模與結(jié)構(gòu)，在適當(dāng)時(shí)機(jī)購(gòu)置船舶、租賃船舶、更新船舶，適應(yīng)港口、航道、貨流新變化的需要，保持足夠的運(yùn)輸能力和競(jìng)爭(zhēng)力.通過(guò)建立船隊(duì)規(guī)劃數(shù)學(xué)模型，解決大型船隊(duì)在不同時(shí)期添置什么類(lèi)型船舶、添置多少、租賃什么類(lèi)型船舶、租賃多少、出售什么類(lèi)型船舶、出售多少以及如何運(yùn)用船舶等動(dòng)態(tài)規(guī)劃問(wèn)題.

1.2 船隊(duì)規(guī)劃模型

1）基本假設(shè) （1）船隊(duì)承擔(dān)運(yùn)輸任務(wù)的網(wǎng)絡(luò)是由若干裝貨港和若干卸貨港組成，通常船舶都能在裝貨港一次裝滿貨物出發(fā)，航行到卸貨港，一次全部卸空貨物，然后空載返回裝貨港再準(zhǔn)備裝貨；（2）研究期（規(guī)劃期）為N，單位為a，為資金結(jié)算的一個(gè)時(shí)間單位；（3）已對(duì)各航線上的貨物運(yùn)輸需求做出預(yù)測(cè)；（4）在研究期內(nèi)共有K種船型可供選擇；（5）船舶買(mǎi)賣(mài)、租賃發(fā)生在年初，退租發(fā)生在年末；（6）考慮到造船周期內(nèi)的預(yù)付資金利息或買(mǎi)船代理費(fèi)等因素，令船舶買(mǎi)入價(jià)格比售價(jià)高一百分比α；（7）考慮到船舶租出時(shí)船東應(yīng)支付給經(jīng)紀(jì)人傭金，令傭金等于所付租金乘以租約規(guī)定的百分比μ；（8）租船業(yè)務(wù)采用期租船形式，租期最少為1a，最長(zhǎng)為整個(gè)研究期；（9）每年?duì)I運(yùn)支出與買(mǎi)船、租賃船支出均發(fā)生在年初，不考慮研究期前的投資費(fèi)用.

2）變量與參數(shù)定義 決策變量xjbht，第t年在h航線上配置的b年建造的j型船的數(shù)量；yjbht，第t年在h航線上配置的b年建造的j型船的年航次數(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ù)Rjbht，在第t年時(shí)b年建造的j型船在h航線上營(yíng)運(yùn)的平均航次毛收益；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à)值；θjht，第t年j型船在h航線上的裝載率；Dj，j型船的額定裝載量；WTht，第t年h航線上的最大貨物運(yùn)輸需求量；tjh，j型船在h航線上的單航次往返時(shí)間；Tj，j型船的年可營(yíng)運(yùn)時(shí)間；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，航線總數(shù)；N，研究期年數(shù)；NT，船舶的壽命期；Rt，第t年?duì)I運(yùn)的航線集合；Φht，第t年可在航線h上營(yíng)運(yùn)的船型集合.

3）數(shù)學(xué)模型 針對(duì)上述問(wèn)題，以追求研究期內(nèi)船隊(duì)現(xiàn)金流量的折現(xiàn)值最大為目標(biāo)函數(shù)，建立船隊(duì)規(guī)劃數(shù)學(xué)模型（P1）如下.

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

約束條件：

其中，式（1）為目標(biāo)函數(shù)，它等于各年度收入的現(xiàn)值減去各年度支出的現(xiàn)值加上研究期末剩余回收部分的現(xiàn)值；式（2）為營(yíng)運(yùn)時(shí)間約束；式（3）為載貨能力上限約束；式（4）為船舶數(shù)量約束；式（5）為船舶融資約束；式（6）為船舶租入數(shù)量約束；式（7）為船舶出售與租出數(shù)量約束；式（8）為新船出售數(shù)量約束；式（9）為新船租出數(shù)量約束；式（10）為船齡約束；式（11）為航線與船型相容性約束；式（12）～（13）為變量約束.

2 求解方法

該模型是一個(gè)大規(guī)?；旌险麛?shù)船隊(duì)規(guī)劃模型.模型涉及到的變量和約束條件較復(fù)雜，當(dāng)問(wèn)題規(guī)模較大、航線數(shù)、船型數(shù)較多的復(fù)雜情況下，將很難在短時(shí)間內(nèi)求得全局最優(yōu)解.為了提高優(yōu)化計(jì)算的收斂性且不破壞所求解的精度，采用Benders分解算法來(lái)求解大規(guī)模船隊(duì)規(guī)劃問(wèn)題，將非常復(fù)雜的優(yōu)化問(wèn)題分解為較為簡(jiǎn)單的問(wèn)題來(lái)處理［8－10］.Benders分解算法的計(jì)算步驟如下.

步驟1初始化參數(shù).設(shè)原問(wèn)題的上、下界分別為：UB＝ ＋∞，LB＝－∞；上下界的容許誤差為ε＝10－5；設(shè)定迭代計(jì)數(shù)變量m＝0，最大迭代次數(shù)為M＝105.

步驟2利用分枝定界算法求解原問(wèn)題的松弛主問(wèn)題（MEP1），若此問(wèn)題有最優(yōu)解，將求出的目標(biāo)函數(shù)值ZU作為新的上界UB，令UB＝min｛ZU，UB｝，并將求解出的變量值固定，代入子問(wèn)題對(duì)應(yīng)的對(duì)偶問(wèn)題中，轉(zhuǎn)向步驟3；若此問(wèn)題為無(wú)界解，則任選一組可行解，轉(zhuǎn)向步驟3；若此問(wèn)題無(wú)解則算法停止，原問(wèn)題無(wú)解.

步驟3對(duì)子問(wèn)題對(duì)應(yīng)的對(duì)偶問(wèn)題進(jìn)行求解，其求解的結(jié)果將會(huì)有兩種情況：無(wú)界或存在最優(yōu)解.若所求對(duì)偶問(wèn)題無(wú)界，應(yīng)對(duì)松弛的主問(wèn)題增加約束條件即添加割平面去掉不可行解，令m＝m＋1，轉(zhuǎn)向步驟1；否則轉(zhuǎn)向步驟4.

步驟4若所有的對(duì)偶子問(wèn)題都可求得最優(yōu)解，將其對(duì)偶解記為＾Uht，＾Vjt，＾Cjht目標(biāo)函數(shù)記為

令LB＝max｛ZL，LB｝，轉(zhuǎn)向步驟5.

步驟5檢驗(yàn)收斂性，若UB－LB＜ε或m＞M，算法停止；否則，令m＝m＋1，對(duì)主問(wèn)題添加割平面：

然后轉(zhuǎn)向步驟1.

3 實(shí)例分析

以我國(guó)某大型航運(yùn)企業(yè)原油運(yùn)輸船隊(duì)為例，該公司計(jì)劃未來(lái)每年投入1.5億美元用于船隊(duì)的建設(shè).規(guī)劃期初船隊(duì)的詳細(xì)資料如表1所列，各型船的年最大營(yíng)運(yùn)時(shí)間為345d，壽命期限為20a，由于水深限制，VLCC型油輪不適于在東南亞航線航行.為提高船隊(duì)的整體技術(shù)性能，規(guī)定每年購(gòu)置船舶的船齡不超過(guò)5a；考慮到租船市場(chǎng)的實(shí)際情況，假設(shè)市場(chǎng)上每年每型船的租賃上限為10艘.通過(guò)預(yù)測(cè)得到各年各航線的運(yùn)輸需求量如表2所列，由于篇幅有限，其他數(shù)據(jù)未列出.計(jì)算參數(shù)值如下：i0＝8%，α＝3%，μ＝1.25%，β＝1.

根據(jù)以上給出的計(jì)算參數(shù)，利用Benders分解算法對(duì)該公司的大型船隊(duì)規(guī)劃問(wèn)題進(jìn)行求解，得到優(yōu)化結(jié)果如下：規(guī)劃期內(nèi)船隊(duì)現(xiàn)金流量的折現(xiàn)值為378 789.39萬(wàn)美元.各年度船舶購(gòu)置和租入方案見(jiàn)表3，各年度船舶租出方案見(jiàn)表4.各年度船舶調(diào)配方案見(jiàn)表5.

表1 研究期前船隊(duì)構(gòu)成

表2 各年各航線的運(yùn)輸需求量 萬(wàn)t

表3 船舶購(gòu)置和租入優(yōu)化方案

表4 船舶租出優(yōu)化方案

表5 船舶調(diào)配優(yōu)化方案

從上述優(yōu)化方案可知，該公司的油輪船隊(duì)運(yùn)力相對(duì)于未來(lái)5a各航線上的原油進(jìn)口量來(lái)說(shuō)是充足的.為了充分使用船舶資源、降低閑置成本、提高經(jīng)濟(jì)效益，將自有船舶租出也是公司采用的主要經(jīng)營(yíng)策略之一.從船隊(duì)運(yùn)力的配置上看，由于原油進(jìn)口航線大多數(shù)為遠(yuǎn)洋航線，多傾向于采用大型船舶，以VLCC型油輪為運(yùn)輸主力，其他船型的油輪作為補(bǔ)充.

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

本文針對(duì)復(fù)雜情況下在多航線上、由多種類(lèi)型船舶構(gòu)成的大型船隊(duì)規(guī)劃問(wèn)題進(jìn)行了研究.在綜合考慮訂造新船、買(mǎi)賣(mài)二手船和租賃船舶等多種可能存在的實(shí)際情況，以及船舶營(yíng)運(yùn)經(jīng)濟(jì)狀態(tài)、企業(yè)投資能力等影響因素的基礎(chǔ)上，建立了船隊(duì)規(guī)劃混合整數(shù)規(guī)劃模型.以我國(guó)某大型航運(yùn)企業(yè)原油運(yùn)輸船隊(duì)作為研究的基礎(chǔ)原型進(jìn)行實(shí)證分析，驗(yàn)證所提出的模型及算法對(duì)于大規(guī)模實(shí)際問(wèn)題的應(yīng)用效果.結(jié)果表明，該方法實(shí)現(xiàn)了多航線、多型船、大規(guī)模混合整數(shù)船隊(duì)規(guī)劃問(wèn)題的優(yōu)化求解，可為大型航運(yùn)企業(yè)進(jìn)行船隊(duì)規(guī)劃決策提供支持.

［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］Christiansen M.Maritime Transportation.Handbook in OR ＆ MS，2007，14（6）：189－284.

［3］楊秋平，謝新連，趙家保.船隊(duì)規(guī)劃研究現(xiàn)狀與動(dòng)態(tài)［J］.交通運(yùn)輸工程學(xué)報(bào)，2010，10（4）：85－90.

［4］謝新連，李樹(shù)范，紀(jì)卓尚.船隊(duì)規(guī)劃的線性模型研究與應(yīng)用［J］.中國(guó)造船，1989（3）：59－66.

［5］Xie X，Ji Z，Yang Y.Nonlinear programming for fleet planning［J］.International Shipbuilding Progress，1993，421：93－103.

［6］Cho S C，Perakis A N.Optimal liner fleet routeing strategies.Maritime Policy and Management［J］，1996，23（3）：249－259.

［7］楊秋平，謝新連.多種類(lèi)型投資的船隊(duì)規(guī)劃模型［J］.上海海事大學(xué)學(xué)報(bào)，2010，31（1）：61－66.

［8］黃紅選，韓繼業(yè).數(shù)學(xué)規(guī)劃［M］.北京：清華大學(xué)出版社，2006.

［9］邴鳳山，劉振宏.一種數(shù)學(xué)規(guī)劃的分解算法（續(xù)篇）［J］.水電能源科學(xué)，1998，16（2）：43－48.

［10］楊秋平.船隊(duì)規(guī)劃數(shù)學(xué)建模及算法研究［D］.大連：大連海事大學(xué)交通運(yùn)輸管理學(xué)院，2010.