復雜情況下大規模船隊規劃模型與求解方法＊

楊秋平 謝新連 裴光石

（交通運輸部水運科學研究院1） 北京 100088） （大連海事大學交通運輸管理學院2） 大連 116026）

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

1 船隊規劃數學模型

1.1 問題描述

針對一個擁有多種類型船舶的大型船隊，以船隊在某一時刻的狀態為起點，根據未來一段時間的航運市場行情預測研究在復雜市場環境下考慮船舶營運經濟狀態、企業投資能力、多種類型投資方式等影響因素，如何逐步調整船隊的規模與結構，在適當時機購置船舶、租賃船舶、更新船舶，適應港口、航道、貨流新變化的需要，保持足夠的運輸能力和競爭力.通過建立船隊規劃數學模型，解決大型船隊在不同時期添置什么類型船舶、添置多少、租賃什么類型船舶、租賃多少、出售什么類型船舶、出售多少以及如何運用船舶等動態規劃問題.

1.2 船隊規劃模型

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

2）變量與參數定義 決策變量xjbht，第t年在h航線上配置的b年建造的j型船的數量；yjbht，第t年在h航線上配置的b年建造的j型船的年航次數；ojbt，第t年閑置b年建造的j型船的數量；sjbt，第t年購買b年建造的j型船的數量；wjbt，第t年出售b年建造的j型船的數量；ujbdt，第t年租入b年建造的j型船的數量，租期為d年；vjbdt，第t年租出b年建造的j型船的數量，租期為d年.

參數Rjbht，在第t年時b年建造的j型船在h航線上營運的平均航次毛收益；Pjbdt，第t年租賃租期為d年的b年建造的j型船的租金；Ejbt，在第t年時b年建造的j型船的售價；Fjbt，在第t年時b年建造的j型船的年度閑置費用；Ajb，在研究期之初船隊中擁有的b年建造的j型船的數量；Wjb，b年建造的j型船在研究期末的回收價值；θjht，第t年j型船在h航線上的裝載率；Dj，j型船的額定裝載量；WTht，第t年h航線上的最大貨物運輸需求量；tjh，j型船在h航線上的單航次往返時間；Tj，j型船的年可營運時間；Qjbt，在研究期之初擁有的需于第t年末退租的b年建造的j型租賃船的數量；Mt，第t年船舶融資限額；Njbt，第t年市場上可供租賃的b年建造的j型船的數量；B0，在研究期之初船隊中擁有的最老船舶的建造時間（B0≤0）；i0，考慮資金時間價值的折現率；α，買船代理費占售價的百分比；μ，船舶租出的傭金占租金的百分比；β，對研究期末船隊實物價值的重視程度系數（0≤β≤1）；K，船型總數；G，航線總數；N，研究期年數；NT，船舶的壽命期；Rt，第t年營運的航線集合；Φht，第t年可在航線h上營運的船型集合.

3）數學模型 針對上述問題，以追求研究期內船隊現金流量的折現值最大為目標函數，建立船隊規劃數學模型（P1）如下.

目標函數：

約束條件：

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

2 求解方法

該模型是一個大規模混合整數船隊規劃模型.模型涉及到的變量和約束條件較復雜，當問題規模較大、航線數、船型數較多的復雜情況下，將很難在短時間內求得全局最優解.為了提高優化計算的收斂性且不破壞所求解的精度，采用Benders分解算法來求解大規模船隊規劃問題，將非常復雜的優化問題分解為較為簡單的問題來處理［8－10］.Benders分解算法的計算步驟如下.

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

步驟2利用分枝定界算法求解原問題的松弛主問題（MEP1），若此問題有最優解，將求出的目標函數值ZU作為新的上界UB，令UB＝min｛ZU，UB｝，并將求解出的變量值固定，代入子問題對應的對偶問題中，轉向步驟3；若此問題為無界解，則任選一組可行解，轉向步驟3；若此問題無解則算法停止，原問題無解.

步驟3對子問題對應的對偶問題進行求解，其求解的結果將會有兩種情況：無界或存在最優解.若所求對偶問題無界，應對松弛的主問題增加約束條件即添加割平面去掉不可行解，令m＝m＋1，轉向步驟1；否則轉向步驟4.

步驟4若所有的對偶子問題都可求得最優解，將其對偶解記為＾Uht，＾Vjt，＾Cjht目標函數記為

令LB＝max｛ZL，LB｝，轉向步驟5.

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

然后轉向步驟1.

3 實例分析

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

根據以上給出的計算參數，利用Benders分解算法對該公司的大型船隊規劃問題進行求解，得到優化結果如下：規劃期內船隊現金流量的折現值為378 789.39萬美元.各年度船舶購置和租入方案見表3，各年度船舶租出方案見表4.各年度船舶調配方案見表5.

表1 研究期前船隊構成

表2 各年各航線的運輸需求量 萬t

表3 船舶購置和租入優化方案

表4 船舶租出優化方案

表5 船舶調配優化方案

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

4 結束語

本文針對復雜情況下在多航線上、由多種類型船舶構成的大型船隊規劃問題進行了研究.在綜合考慮訂造新船、買賣二手船和租賃船舶等多種可能存在的實際情況，以及船舶營運經濟狀態、企業投資能力等影響因素的基礎上，建立了船隊規劃混合整數規劃模型.以我國某大型航運企業原油運輸船隊作為研究的基礎原型進行實證分析，驗證所提出的模型及算法對于大規模實際問題的應用效果.結果表明，該方法實現了多航線、多型船、大規模混合整數船隊規劃問題的優化求解，可為大型航運企業進行船隊規劃決策提供支持.

［1］Christiansen M，Fagerholt 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］楊秋平，謝新連，趙家保.船隊規劃研究現狀與動態［J］.交通運輸工程學報，2010，10（4）：85－90.

［4］謝新連，李樹范，紀卓尚.船隊規劃的線性模型研究與應用［J］.中國造船，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］楊秋平，謝新連.多種類型投資的船隊規劃模型［J］.上海海事大學學報，2010，31（1）：61－66.

［8］黃紅選，韓繼業.數學規劃［M］.北京：清華大學出版社，2006.

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

［10］楊秋平.船隊規劃數學建模及算法研究［D］.大連：大連海事大學交通運輸管理學院，2010.