劉寶濤 王運(yùn)龍 陳 明

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

0 引 言

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

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

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

1 問題描述

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

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

具體條件為：

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

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

3）以預(yù)測(cè)的未來某年?duì)I運(yùn)需求為基礎(chǔ)數(shù)據(jù)。

4）假定船舶使用壽命為Y年，折算出的每年的營(yíng)運(yùn)費(fèi)用相同。

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

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

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

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

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

模型建立為：

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

約束條件如下：

1）港口供需約束。

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

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

二級(jí)港的需求約束：

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

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

2）港口時(shí)間約束。

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

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

二級(jí)港的時(shí)間約束：

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

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

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

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

2.2 混合整數(shù)模型

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

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

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

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

與前2 類模型相比，整數(shù)規(guī)劃模型增加了約束，使計(jì)算出的每條航線的船舶數(shù)量一定是整數(shù)，即每條船運(yùn)營(yíng)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)解，實(shí)際上往往是次優(yōu)解，其原因是，運(yùn)量和時(shí)間約束中的系數(shù)是某船型以簡(jiǎn)單航次形式運(yùn)行1年的年運(yùn)力和年占港時(shí)間。而在實(shí)際情況中，船舶的運(yùn)輸能力往往未被全部利用，即實(shí)際上的年運(yùn)輸量要小于年運(yùn)力，年實(shí)際占港時(shí)間也小于年最大占港時(shí)間，這就有可能導(dǎo)致某條最優(yōu)的航線被排除。例如，某港口的供應(yīng)約束為：

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

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

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

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

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

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

所建模型為：

約束條件如下：

1）港口供需約束。

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

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

二級(jí)港的需求約束：

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

2）港口時(shí)間約束。

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

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

二級(jí)港的時(shí)間約束：

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

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

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

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

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

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

3 計(jì)算實(shí)例

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

3.1 已知條件

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

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

3）各航線各船型年?duì)I運(yùn)費(fèi)用，萬元。

4）各航線各船型單船年運(yùn)力，萬噸。

5）單次航行一級(jí)港小船的停靠時(shí)間，天。

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

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

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

表1 航線運(yùn)距Tab.1 Sailing distances among different ports

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

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

根據(jù)以上信息，可計(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)化計(jì)算結(jié)果Tab.3 Computational results by different models

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

4 結(jié) 論

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

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

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

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

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

［2］謝新連.船隊(duì)規(guī)劃的動(dòng)態(tài)模型與算法［J］.中國(guó)造船，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ì)卓尚，謝新連，李樹范. 沿海原油運(yùn)輸船隊(duì)規(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］楊秋平，謝新連，蘇晨. 航線配船與船隊(duì)規(guī)劃模型及算法實(shí)現(xiàn)［J］.中國(guó)航海，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ā)展我國(guó)巨型油船船隊(duì)的戰(zhàn)略規(guī)劃［J］.上海交通大學(xué)學(xué)報(bào)，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ì)卓尚，等.船隊(duì)規(guī)劃的線性模型研究與應(yīng)用［J］.中國(guó)造船，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é)志. 實(shí)用最優(yōu)化方法［M］. 大連：大連理工大學(xué)出版社，2004.