新建船隊的船隊優化模型建立和比較

劉寶濤 王運龍 陳 明

大連理工大學船舶CAD 工程中心，遼寧大連116024

0 引 言

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

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

本文針對具體的新建船隊的規劃問題，全面考慮了現役船舶的運輸能力及其營運數據等條件，根據航運企業不同的需求側重點，建立了連續變量線性規劃模型、混合整數線性規劃模型和整數規劃模型，均是以船隊必要運費率為目標函數，獲得可信的優化結果。

1 問題描述

船隊承擔運輸任務的航區由一級和二級兩類港組成，貨物由海外先運輸卸載到一級港，然后再向二級港轉運。一級港中有若干個港口兼作調峰港，可通過接收其他一級港送來的貨物來應對需求高峰，其關系如圖1 所示。

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

具體條件為：

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

2）航區內有G 條可能航線；一級港M 個，其中調峰港口L 個，非調峰港不參與調峰的港口P個；二級港N 個。

3）以預測的未來某年營運需求為基礎數據。

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

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

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

2 數學模型的建立

2.1 連續變量的線性規劃模型

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

模型建立為：

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

約束條件如下：

1）港口供需約束。

一級非調峰港參與調峰的港口供應約束：

其他一級港的供應約束：

二級港的需求約束：

一級調峰港的需求約束：

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

2）港口時間約束。

一級非調峰港參與調峰的港口的時間約束：

一級非調峰港不參與調峰的港口的時間約束：

二級港的時間約束：

一級調峰港的時間約束：

3）非負性約束。

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

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

2.2 混合整數模型

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

與前一模型的目標函數表達式相同，在原有約束的基礎上加上了每一種船型的船舶數是整數的約束。

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

2.3 整數規劃模型

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

2.3.1 線性整數規劃

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

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

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

如假設利用率系數為0.8，約束變為：

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

然后，再進行優化計算。計算時，可以多試幾個利用率系數，然后比較優化結果并從中找出較好的解。可以認為，這個解是比較優的。

2.3.2 非線性的整數模型

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

所建模型為：

約束條件如下：

1）港口供需約束。

一級非調峰港參與調峰的港口的供應約束：

其他一級港的供應約束：

二級港的需求約束：

一級調峰港的需求約束：

2）港口時間約束。

一級非調峰港參與調峰的港口的時間約束：

一級非調峰港不參與調峰的港口的時間約束：

二級港的時間約束：

一級調峰港的時間約束：

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

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

5）非負性約束。

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

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

3 計算實例

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

3.1 已知條件

1）船型信息。總共有4 種不同艙容的船型可以選擇，分別為（2×104），（3×104），（4×104），（8×104）m3，造價分別假設為48 000 萬 元、61 000 萬元、79 000 萬元和91 000 萬元。

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

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

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

5）單次航行一級港小船的停靠時間，天。

6）單次航行船舶在二級港的停靠時間，天。

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

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

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

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

3.2 計算結果與比較

根據以上信息，可計算出各模型的的結果，如表3 所示。

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

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

表3 不同模型的優化計算結果Tab.3 Computational results by different models

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

4 結 論

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

1）連續變量的線性模型或混合整數線性模型所得到的營運方案的優點是經濟性比較好，缺點是這2 種模型的結果都需要船舶調度，往往需要1 艘船營運于幾條航線，這可能會給航運管理帶來不便，由于一些原因，有些調度可能也不能實現。

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

上述結果對于企業結合具體情況選擇合適的優化模型具有一定的參考價值。

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

［2］謝新連.船隊規劃的動態模型與算法［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］.船舶工程，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］楊秋平，謝新連，蘇晨. 航線配船與船隊規劃模型及算法實現［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］張魯峰，張仁頤.發展我國巨型油船船隊的戰略規劃［J］.上海交通大學學報，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］.中國造船，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］唐煥文，秦學志. 實用最優化方法［M］. 大連：大連理工大學出版社，2004.