新建船隊的船隊優(yōu)化模型建立和比較

劉寶濤 王運龍 陳 明

大連理工大學(xué)船舶CAD 工程中心，遼寧大連116024

0 引 言

在已知運輸需求的情況下規(guī)劃新組建船隊的配置和規(guī)模，滿足任務(wù)要求并期望獲得最大收益是航運企業(yè)常需面臨的現(xiàn)實課題。

在有多條航線和多種可用型船且各港口供需量已知的情況下確定船隊的最佳構(gòu)成，關(guān)鍵在于優(yōu)化模型的建立。連續(xù)變量線性規(guī)劃模型和混合整數(shù)線性規(guī)劃模型是解決船隊規(guī)劃問題最常用的模型，具有模型簡單、計算方便的優(yōu)點，但也存在著船舶調(diào)度的現(xiàn)實合理性問題。有些企業(yè)從便于管理的角度出發(fā)，要求單船固定一條航線，此時，就需要采用整數(shù)規(guī)劃模型來解決這一類問題。但整數(shù)規(guī)劃計算復(fù)雜，相關(guān)研究也開展得較少［1］。

本文針對具體的新建船隊的規(guī)劃問題，全面考慮了現(xiàn)役船舶的運輸能力及其營運數(shù)據(jù)等條件，根據(jù)航運企業(yè)不同的需求側(cè)重點，建立了連續(xù)變量線性規(guī)劃模型、混合整數(shù)線性規(guī)劃模型和整數(shù)規(guī)劃模型，均是以船隊必要運費率為目標(biāo)函數(shù)，獲得可信的優(yōu)化結(jié)果。

1 問題描述

船隊承擔(dān)運輸任務(wù)的航區(qū)由一級和二級兩類港組成，貨物由海外先運輸卸載到一級港，然后再向二級港轉(zhuǎn)運。一級港中有若干個港口兼作調(diào)峰港，可通過接收其他一級港送來的貨物來應(yīng)對需求高峰，其關(guān)系如圖1 所示。

圖1 航線示意圖Fig.1 Sailing route diagram

具體條件為：

1）共有K 種船型可供選擇。

2）航區(qū)內(nèi)有G 條可能航線；一級港M 個，其中調(diào)峰港口L 個，非調(diào)峰港不參與調(diào)峰的港口P個；二級港N 個。

3）以預(yù)測的未來某年營運需求為基礎(chǔ)數(shù)據(jù)。

4）假定船舶使用壽命為Y年，折算出的每年的營運費用相同。

同時，要求船隊必須滿足二級港和一級調(diào)峰港的需求，各二級港的需求量和一級港的最大提供量等條件已知。

針對上述問題，建立以Y年內(nèi)的必要運費率為目標(biāo)函數(shù)，考慮運量、時間等約束條件的優(yōu)化模型。必要運費率是確保不虧損的最低單位貨量的運費。若必要運費率低于市場運價，則該方案可以接受。必要運費率越低，方案越具有競爭力，承擔(dān)的風(fēng)險也越小［2］。

2 數(shù)學(xué)模型的建立

2.1 連續(xù)變量的線性規(guī)劃模型

連續(xù)變量的線性規(guī)劃模型，不僅簡單，而且運算方便。此模型有一個假設(shè)前提，即船舶以簡單航次的形式運行，在裝貨港一次性裝滿貨物出發(fā)，航行至卸貨港后一次性卸空貨物。解此模型，當(dāng)求得的某型船在某航線上的配置艘數(shù)是小數(shù)時，說明該船并非全年都在該航線上營運，還有一部分時間在其他航線上營運。而對于每年的建船量而言，則必須圓整為整數(shù)值給出。圓整后的最優(yōu)解值可能會發(fā)生一點變化，但只要目標(biāo)函數(shù)值的變化不大，仍認(rèn)為它是優(yōu)解（或稱其為次優(yōu)解）［3-5］。

模型建立為：

式中，Xtij為從第t個港口裝貨到第i個港口卸貨的航線上第j種船型的數(shù)量；Pj為第j種船型的船價，萬元；Rtij為從第t個港口裝貨到第i個港口卸貨的航線上第j 種船型的年營運費用，萬元；W 為各航線各種船型的年總運量，萬噸；IY為現(xiàn)值因數(shù)。

約束條件如下：

1）港口供需約束。

一級非調(diào)峰港參與調(diào)峰的港口供應(yīng)約束：

其他一級港的供應(yīng)約束：

二級港的需求約束：

一級調(diào)峰港的需求約束：

在使用其他3 種模型時，需求約束中的“=”改為“≥”。

2）港口時間約束。

一級非調(diào)峰港參與調(diào)峰的港口的時間約束：

一級非調(diào)峰港不參與調(diào)峰的港口的時間約束：

二級港的時間約束：

一級調(diào)峰港的時間約束：

3）非負(fù)性約束。

其中，Vtij為從第t個港口裝貨到第i個港口卸貨的航線上第j 種船型的年營運力，萬噸；Qt為第t個一級港的最大外輸量，萬噸；qi為第i個二級港的需求量，萬噸；gi為第i 個一級調(diào)峰港在需求高峰時的需求量，萬噸；Xtij為從第t 個港口裝貨到第i 個港口卸貨的航線上第j 種船型的年靠港時間，天；Tt為第t 個一級港一年所能提供的最大?？繒r間，天；TTi為第i 個二級港一年所能提供的最大?？繒r間，天。

在該模型中，共有K×(L×(M-L-P)+M×N)個變量。求解后，就可得到最優(yōu)航線和最佳船型。

2.2 混合整數(shù)模型

與連續(xù)變量的線性規(guī)劃模型相比，混合整數(shù)模型增加了所有航線中任意一種船型數(shù)量的和一定是整數(shù)的約束［6］，這使得計算出的船舶數(shù)量一定是整數(shù)，就沒有線性規(guī)劃中的圓整問題了［7-9］。

與前一模型的目標(biāo)函數(shù)表達(dá)式相同，在原有約束的基礎(chǔ)上加上了每一種船型的船舶數(shù)是整數(shù)的約束。

式中，Ij為整數(shù)。與前一模型相比，此模型增加了j個變量和j個約束。

2.3 整數(shù)規(guī)劃模型

與前2 類模型相比，整數(shù)規(guī)劃模型增加了約束，使計算出的每條航線的船舶數(shù)量一定是整數(shù)，即每條船運營1 條航線。下面，將分別討論線性整數(shù)規(guī)劃模型和非線性整數(shù)規(guī)劃模型。

2.3.1 線性整數(shù)規(guī)劃

線性整數(shù)規(guī)劃的目標(biāo)函數(shù)與上面的模型一致，在原有約束的基礎(chǔ)上添加了每條航線上每種類型船的數(shù)量一定為整數(shù)的約束，即Xtij∈{0，1，2，…} 。

此模型得出的結(jié)果并不一定是最優(yōu)解，實際上往往是次優(yōu)解，其原因是，運量和時間約束中的系數(shù)是某船型以簡單航次形式運行1年的年運力和年占港時間。而在實際情況中，船舶的運輸能力往往未被全部利用，即實際上的年運輸量要小于年運力，年實際占港時間也小于年最大占港時間，這就有可能導(dǎo)致某條最優(yōu)的航線被排除。例如，某港口的供應(yīng)約束為：

根據(jù)約束，當(dāng)X111等于1、其他值等于0 時，是不滿足約束的。但實際上，這也能完成運輸任務(wù)，只是船舶的利用率未達(dá)到100%而已，這就有可能排除了較優(yōu)的航線和船型。針對模型的這個缺陷，可以通過在模型約束中添加利用率系數(shù)，進行多次試算來找出一個比較優(yōu)的解。

如假設(shè)利用率系數(shù)為0.8，約束變?yōu)椋?/p>

99×0.8×X11+108×0.8×X12+…≥94

然后，再進行優(yōu)化計算。計算時，可以多試幾個利用率系數(shù)，然后比較優(yōu)化結(jié)果并從中找出較好的解。可以認(rèn)為，這個解是比較優(yōu)的。

2.3.2 非線性的整數(shù)模型

通過建立非線性的數(shù)學(xué)模型，可以避免線性整數(shù)優(yōu)化模型的缺陷，具體做法是，將單船年營運費用分為固定費用C1和變動費用C2，固定費用是1年中不變的費用，比如年船員費用、保險費、港口管理費等；變動費用包括燃油費、拖航費等隨航次數(shù)變化而變動的費用。可以假設(shè)從第t 個裝貨港出發(fā)的第i 條航線第j種船型船的實際年運量（變量）為Qtij，然后，根據(jù)這條航線上此種船的航次運貨量（已知）來確定航次數(shù)，因此，變動費用可表示為實際年運量的函數(shù)。通過整理發(fā)現(xiàn)，該函數(shù)關(guān)系是一次的，即C2=f(Qtij)。然后，便可得出從第t 個港口裝貨到第i 個港口卸貨的航線上第j種船型的單船年實際費用C0=C1+C2=F(Qtij)，是Qtij的一次函數(shù)。

所建模型為：

約束條件如下：

1）港口供需約束。

一級非調(diào)峰港參與調(diào)峰的港口的供應(yīng)約束：

其他一級港的供應(yīng)約束：

二級港的需求約束：

一級調(diào)峰港的需求約束：

2）港口時間約束。

一級非調(diào)峰港參與調(diào)峰的港口的時間約束：

一級非調(diào)峰港不參與調(diào)峰的港口的時間約束：

二級港的時間約束：

一級調(diào)峰港的時間約束：

3）變量關(guān)系，單船的實際運量和實際的占港時間也是線性關(guān)系。

4）每條航線上的每種船型必須為整數(shù)，即Xtij∈{0，1，2，…} 。

5）非負(fù)性約束。

其中，Qtij為從第t 個港口裝貨到第i 個港口卸貨的航線上第j種船型的實際年運量，萬噸；TItij為從第t個港口裝貨到第i個港口卸貨的航線上第j 種船型的年實際靠港時間，天；Qt為第t 個一級港的最大外輸量，萬噸；qi為第i 個二級港的需求量，萬噸；gi為第i 個一級調(diào)峰港在需求高峰時的需求量，萬噸；Tt為第t 個一級港一年所能提供的最大?？繒r間，天；TTi為第i 個二級港一年所能提供的最大?？繒r間，天。

在該模型中，共有3×K×（L×（M-L-P）+M×N）個變量。該模型求解的是一個非線性約束優(yōu)化問題，這種問題的解法是人們最為關(guān)心的，因此研究的人較多，提供的方法也較多，但目前尚沒有一種對一切問題都普遍有效的算法，而且求得的解也多是局部最優(yōu)解。但本模型的結(jié)果依然具有重要的參考作用［10］。

3 計算實例

某公司現(xiàn)在要組建運輸船隊，有6 個一級港，（其中1 個調(diào)峰港），4 個二級港。其中，有3 個一級港有余量向調(diào)峰港運輸，分別為一級港1、一級港2、一級港5。共有4 種船型，港口供需量、運距、各船型、年運力、航運量、航次占港時間均已知，試確定某一年的最佳航線最佳船型。

3.1 已知條件

1）船型信息?？偣灿? 種不同艙容的船型可以選擇，分別為（2×104），（3×104），（4×104），（8×104）m3，造價分別假設(shè)為48 000 萬 元、61 000 萬元、79 000 萬元和91 000 萬元。

2）航線運距（n mile），如表1 所示。

3）各航線各船型年營運費用，萬元。

4）各航線各船型單船年運力，萬噸。

5）單次航行一級港小船的?？繒r間，天。

6）單次航行船舶在二級港的?？繒r間，天。

7）各港口需求量、供應(yīng)量（萬噸）和營運時間（天）如表2 所示。

限于篇幅，不一一列出第3）～6）的信息表格。

表1 航線運距Tab.1 Sailing distances among different ports

表2 港口需求信息Tab.2 Demand information from each port

3.2 計算結(jié)果與比較

根據(jù)以上信息，可計算出各模型的的結(jié)果，如表3 所示。

線性模型得到的最優(yōu)值為Z=46.5 元/t；混合整數(shù)線性模型得到的最優(yōu)值為Z=58 元/t，其中4種不同艙容的船的數(shù)量分別為I1=1，I2=0，I3=0，I4=2；線性整數(shù)模型得到的最優(yōu)值為Z=85.3 元/t；非線性整數(shù)模型得到的最優(yōu)值為Z=90.1 元/t。

根據(jù)上述結(jié)果可以看出，最優(yōu)的航線距離往往比較短，最佳的船型往往比較大。這樣的結(jié)果是合理的，此外，4種優(yōu)化模型的建模也比較方便。

表3 不同模型的優(yōu)化計算結(jié)果Tab.3 Computational results by different models

比較4 個模型的最優(yōu)值可以看出，線性規(guī)劃最優(yōu)值最?。▓A整前），但其船舶數(shù)目不是整數(shù)，需要圓整；而線性混合整數(shù)規(guī)劃的結(jié)果雖然不需要圓整，但線性規(guī)劃與線性混合整數(shù)規(guī)劃都存在調(diào)度管理的問題；對于整數(shù)規(guī)劃模型的結(jié)果，船舶數(shù)目肯定是整數(shù)，且每條船只在單一航線上行駛，不存在上述模型的問題，但最優(yōu)值比較大。從中可以看出，船舶調(diào)度管理與經(jīng)濟性之間存在著矛盾，至于選哪種新組建船隊的模型，應(yīng)根據(jù)企業(yè)的實際情況決定。

4 結(jié) 論

本文以一個具體的新組建船隊問題建立了4種優(yōu)化模型，得出以下結(jié)論：

1）連續(xù)變量的線性模型或混合整數(shù)線性模型所得到的營運方案的優(yōu)點是經(jīng)濟性比較好，缺點是這2 種模型的結(jié)果都需要船舶調(diào)度，往往需要1 艘船營運于幾條航線，這可能會給航運管理帶來不便，由于一些原因，有些調(diào)度可能也不能實現(xiàn)。

2）整數(shù)模型得到的方案的優(yōu)點是營運方案為單船單航線，管理方便，缺點是經(jīng)濟性比前2 種模型的營運方案差。此外，值得說明的是，對于本文所建的整數(shù)模型，往往只能得到局部最優(yōu)解，但經(jīng)過對線性整數(shù)模型的多次試算并與非線性整數(shù)規(guī)劃模型的結(jié)果進行比較取優(yōu)，依然能夠得到較好的結(jié)果。

上述結(jié)果對于企業(yè)結(jié)合具體情況選擇合適的優(yōu)化模型具有一定的參考價值。

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

［2］謝新連.船隊規(guī)劃的動態(tài)模型與算法［J］.中國造船，1992，45（3）：102-110.XIE X L.A dynamic model and algorithm for fleet plan?ning［J］.Shipbuiding of China，1992，45（3）：102-110.

［3］紀(jì)卓尚，謝新連，李樹范. 沿海原油運輸船隊規(guī)劃［J］.船舶工程，1993，15（2）：17-21.JI Z S，XIE X L，LI S F.A theoretical study on the plan?ning of Chinese coastal crude oil carrier fleet［J］. Ship Engineering，1993，15（2）：17-21.

［4］楊秋平，謝新連，蘇晨. 航線配船與船隊規(guī)劃模型及算法實現(xiàn)［J］.中國航海，2009，32（1）：91-95.YANG Q P，XIE X L，SU C. Model of ship routing and fleet planning and its algorithm［J］. Navigation of Chi?na，2009，32（1）：91-95.

［5］張魯峰，張仁頤.發(fā)展我國巨型油船船隊的戰(zhàn)略規(guī)劃［J］.上海交通大學(xué)學(xué)報，2001，35（12）：1873-1876.ZHANG L F，ZHANG R Y. Strategic scheme for VLCC fleet development of China［J］. Journal of Shanghai Ji?ao Tong University，2001，35（12）：1873-1876.

［6］謝新連，李樹范，紀(jì)卓尚，等.船隊規(guī)劃的線性模型研究與應(yīng)用［J］.中國造船，1989，42（3）：61-68.XIE X L，LI S F，JI Z S，et al. Study and application on-the linear model of fleet planning［J］. Shipbuilding of China，1989，42（3）：61-68.

［7］JARAMILLO D I，PERAKIS A N.Fleet deployment op?timization for liner shipping part II：implementation and results［J］. Maritime Policy and Management，1991，18（4）：235-262.

［8］CHO S C，PERAKIS A N. Optimal liner fleet routeing strategies［J］. Maritime Policy and Management，1996，23（3）：249-259.

［9］PERAKIS A N，BREMER W M. An operational tanker scheduling optimization system：background，current practice and model formulation［J］.Maritime Policy and Management，1992，19（3）：177-187.

［10］唐煥文，秦學(xué)志. 實用最優(yōu)化方法［M］. 大連：大連理工大學(xué)出版社，2004.