航運下行期的航線配船和航次設計優(yōu)化

邵俊崗，薛穎霞

(上海海事大學科學研究院，上海 201306)

0 引言

后金融危機時代，全球經濟持續(xù)低迷，加之歐債危機不斷深化、市場融資環(huán)境日益惡化和船舶供給壓力過大等不利因素的影響，全球航運市場長期在底部振蕩徘徊.航運企業(yè)由于難以吸納充足的貨源，面臨嚴重的運力過剩，大量新船的陸續(xù)交付無疑也使各航運公司的處境更為艱難.合理的航線配船和航次設計可以幫助航運企業(yè)充分利用現(xiàn)有的船舶，以最少的投入或消耗換取最大的產出或效益，對航運公司具有重要的意義.

關于航線配船問題，國內外眾多學者已經進行廣泛的研究，并提出多種解決方案.RONEN［1］根據(jù)貨運狀況提出優(yōu)化給定航線的航線配船方案.謝新連在文獻［2］中建立船隊規(guī)劃線性模型，其目標函數(shù)為船隊營運和造船總費用最小化，并在文獻［3］中對船舶調度、船隊規(guī)劃等問題用線性規(guī)劃、非線性規(guī)劃、動態(tài)規(guī)劃等多種方法進行求解.蘇紹娟［4］建立不確定動態(tài)船隊規(guī)劃的數(shù)學模型.楊秋平等［5］建立考慮船舶航速的船隊規(guī)劃非線性數(shù)學模型.BRONMO等［6］構造一個航線配船的主問題以及一個基于該主問題的子問題.陳穎［7］嘗試將遺傳算法與模擬退火算法相結合，引入班輪配船問題.林珈伊等［8］在線性規(guī)劃的航線配船模型基礎上，建立受船閘時間阻抗變動影響的航線非線性配船模型.目前，國內外關于航運周期的研究還相對較少，STOPFORD［9］將航運市場周期分為波谷期、恢復期、高峰期和下滑期等4個階段，并詳細闡述各階段的特征以及一些影響因素.

上述文獻嘗試用各種方法解決班輪的配船問題，但是并未將航運業(yè)的周期性特征考慮在內.在航運下行期，集裝箱船舶的裝載率普遍下降，而目前大部分關于航線配船的研究并未考慮航運周期性對裝載率的影響.另外，傳統(tǒng)模型對同一航線上同一船型的集裝箱船舶均設置同樣的航次，與現(xiàn)實中班輪公司所采取的措施不符，也使班輪公司的收益難以實現(xiàn)最大化.為彌補傳統(tǒng)航線配船的不足，本文根據(jù)航運下行期的特點，建立關于航線配船和航次設計的整數(shù)規(guī)劃模型，并嘗試用MATLAB編程的遺傳算法對該模型進行求解.

1 航線配船和航次設計模型建立

1.1 問題描述以及模型假設

假設某公司現(xiàn)有m種載質量的集裝箱班輪運營在n條航線上，在裝貨港一次裝載貨出發(fā)，航行到卸貨港之后，一次性卸完貨物.研究階段處于航運下行期，現(xiàn)對該公司的航線配船和班輪航次進行設計，以較低的運營成本完成運輸任務，爭取獲得最大的收益.

為便于研究，本文以1年為規(guī)劃期，并假設:①規(guī)劃期內該公司沒有新的集裝箱班輪交付;②規(guī)劃期內該公司沒有集裝箱班輪退役;③所預測的運量較為準確，且所有運量較為均勻地發(fā)生在1年的各個時期;④采取規(guī)劃期內的平均運價.

1.2 符號說明

假設:某船公司現(xiàn)有的船舶種類集合V={i|i=1，2，…，m};其所經營的航線集合 R={j|j=1，2，…，n};L為1年內航線配船方案的總利潤;船型i的裝載量為Wi，數(shù)量為Si;Hij為i型船在航線j上可以選擇的航次種類數(shù)，例如H12=4為船型1的船舶在航線2上可以選擇4種不同的航次;Pj1為正向航線j上運輸1 TEU的收入，定義為正向航線j上承運1 TEU的運費率;Pj2為反向航線j上運輸1 TEU的收入，定義為反向航線j上承運1 TEU的運費率;Qj1為正向航線j上當年預測的運量;Qj2為反向航線j上當年預測的運量;Ei為i型船當年的閑置費用(被封存的船雖然不再有運營費，但是仍然存在保養(yǎng)費、看管人員工資等費用);Zi為閑置的i型船的數(shù)量;Rj1為正向航線j上最大平均裝載率;Rj2為反向航線j上最大平均裝載率;tijh為i型船在航線j上選擇以第h種航次運營時的年往返航次，例如t111=3為船型為1的船在航線1上以第1種航次運營時的年往返航次為3;Cijh為i型船在航線j上每年完成tijh個往返航次時每個航次的航次成本，包括燃料費、港務費和航次費用等;決策變量xijh為被分配在航線j上每年完成tijh個往返航次的i型船的數(shù)量.

1.3 模型構建與解釋

1.3.1 模型構建

在航運下行期，由于貨運需求下降，大多數(shù)航線的裝載率普遍下降，班輪公司多采取降低航速、減少年航次等措施降低運營成本，這時在同一航線上同一型號的船舶每年可能會完成不同的航次.本文所建立的模型加入對裝載率的考慮，并設定在同一航線上同一船型可以選擇不同的航次(此時單位航次成本因航速的變化而發(fā)生變化)，更符合航運下行期的特點.其目標函數(shù)為

1.3.2 模型解釋

該模型對集裝箱正向運輸和反向運輸采用不同的運價和運量，這樣的處理更符合實際.式(1)表示在規(guī)劃期內航線配船方案的總利潤最大.式(2)是對船舶數(shù)量的約束，即所有航線上某種船型船舶的總數(shù)與該船型閑置船舶的數(shù)量之和必須等于該船型船舶的總數(shù).式(3)和(4)是對船舶最大平均裝載率的約束，即在航運低迷期適度減少航次可以在一定程度上提高船舶的平均裝載率，但是船舶的裝載率仍會保持在一定的范圍內，過高的平均裝載率不符合航運下行期的實際情況.式(5)是對決策變量的非負性以及整數(shù)約束.

2 算法實現(xiàn)

2.1 遺傳算法原理

遺傳算法(Genetic Algorithm，GA)是模擬達爾文適者生存、優(yōu)勝劣汰的生物進化論的自然選擇原理和遺傳學的生物進化過程而演化出的搜索最優(yōu)解的方法，是一種新型全局優(yōu)化搜索算法，由美國密歇根大學的HOLLAND教授于1975年首先提出.GA能有效解決許多由經典數(shù)學方法無法解決的復雜的、大規(guī)模的難題.GA一般流程見圖1.

圖1 GA流程圖

2.2 遺傳算法設計

2.2.1 染色體設計

由于航線配船問題所涉及的因素較多(包括航線、航次、船舶數(shù)量等)，較為復雜，本文采用浮點數(shù)編碼方式代替?zhèn)鹘y(tǒng)的二進制編碼.將1年內在某條航線上以某種年往返航次進行運營的某種船型的船舶總數(shù)作為一個基因位，見圖2.例如:第1個基因位代表在航線1上以第1種年往返航次運營的船型1的船舶數(shù)量，第2個基因位代表在航線1上以第2種年往返航次運營的船型1的船舶數(shù)量，其余基因位的含義依此類推.

圖2 染色體結構示意

為便于對原模型進行GA編程，需要對決策變量的表示方式進行一定的變化，現(xiàn)以船型1的分配為例進行說明.原模型中的x111，x112和x113(在航線1上分別以第1，2，3種年往返航次進行運營的第1種船舶的數(shù)量)在編程中分別用x1，x2和x3表示，其他船型船舶數(shù)量變化方式依此類推.

2.2.2 產生初始種群

為保持種群的多樣性和解的質量，采用隨機方式產生初始種群.一般而言，種群規(guī)模通常為個體編碼長度的一個線性倍數(shù)，通常在n與2n之間.本文建議在試驗中調整種群數(shù)量以便取得較好的計算效果.

2.2.3 適應度函數(shù)

采用MATLAB對遺傳算法編程，適應度函數(shù)為f(x)=cmax－L，其中cmax是根據(jù)多次試驗的收斂結果確定的.

2.2.4 選擇操作

選擇過程是根據(jù)個體的適應度從種群中選擇個體復制到中間代，直至達到種群規(guī)模的過程.選擇目的是將最優(yōu)個體直接保留到下一代中，使種群得到進化.GA中有多種選擇操作方法，本文采用最常用的輪盤賭方法進行選擇操作.

2.2.5 交叉操作

交叉過程是利用隨機概率將種群各個體之間的信息進行相互交換從而產生新染色體的過程.交叉的目的是增加種群的多樣性.交叉運算是GA不同于其他進化算法的重要特征，它在GA中起關鍵作用，是產生新個體的主要方法.交叉操作的種類很多，本文采用兩點交叉的方式，隨機將中間代的染色體兩兩配對.

2.2.6 變異操作

變異運算是GA中產生新個體的輔助方法，它能決定GA的局部搜索能力，同時能保持種群的多樣性.交叉運算和變異運算在GA中相互配合，共同完成對搜索空間的全局搜索和局部搜索.本文采用單點變異的方法進行新的航線配船選擇，得到新的染色體.

2.2.7 終止準則

采用最大代終止法，即計算在迭代代數(shù)達到所給定的最大遺傳代數(shù)時停止，輸出所得到的最優(yōu)解.

3 算例驗證與分析

為驗證所建模型的有效性，用GA對一個算例進行求解.某公司擁有3種裝載能力的集裝箱船，分別為1686 TEU，1250 TEU，850 TEU，共有4 條集裝箱航線，船舶參數(shù)及其年閑置費用見表1.根據(jù)所預測的運量需求(見表2)，將不同船型的船舶配置在這4條航線上以求獲得最大的經濟效益.因為可獲得數(shù)據(jù)有限，對于船型相同、在同一航線上年航次不同的船舶采用同樣的單位航次成本.各船型在各航線上的單位航次成本，最大、最小年航次和最大平均裝載率分別見表3～5.各航線集裝箱運價見表6.

表1 船舶參數(shù)及其年閑置費用

表3 各船型在各航線上的單位航次成本 萬美元

表4 各船型在各航線上的最大、最小年航次 次

經過反復試驗，在設定該GA的種群規(guī)模為72，最大遺傳代數(shù)為100，交叉概率為0.7500，變異概率為0.0078時效果較好.該GA可在遺傳代數(shù)為50左右時給出最優(yōu)解，所得到的最大利潤穩(wěn)定在1.56億美元左右.最終用GA所得到的航線配船的最優(yōu)解見表7，其總利潤為15703.20萬美元.

表5 各航線最大平均裝載率 %

表6 各航線集裝箱運價 萬美元/TEU

表7 航線配船GA最優(yōu)解

表7中括號里的數(shù)字表示航次，括號前的數(shù)字表示在該航線上以括號中的年往返航次運營的該船型船舶的數(shù)量.如“1(8)，1(9)”表示航線1上應分配2艘第1種型號的船舶，其中1艘每年運營8個航次，另外1艘每年運營9個航次.最后一列代表各船型閑置船舶的數(shù)量.

運用 LINGO求解該模型，得到的最優(yōu)解是15728.20萬美元，GA所得到的最大利潤與之僅相差0.159%左右，這證明本文所設計的算法能較好地收斂到近似最優(yōu)解，且耗時更短.由以上結果可以看出，通過合理優(yōu)化班輪公司的航線配船和航次設計方案可以實現(xiàn)收益的最大化.

4 結束語

在現(xiàn)有航線配船模型的基礎上，結合現(xiàn)階段航運下行期的特點，建立混合整數(shù)規(guī)劃模型，對航線配船和班輪航次進行優(yōu)化設計，并運用GA對該模型進行求解，最后將其結果與LINGO計算結果進行比較，驗證該模型的可行性和該算法的有效性.因此，本文對班輪公司根據(jù)航運下行期的特點設計航線配船方案具有重要的參考意義.

［1］RONEN D.Cargo ships routing and scheduling:survey of models and problems［J］.Eur J Operational Res，1983，78(5):46-49.

［2］謝新連.船隊規(guī)劃的線性模型研究與應用［J］.中國造船，1989(3):59-66.

［3］謝新連.船舶調度與船隊規(guī)劃方法［M］.北京:人民交通出版社，1997:75-86.

［4］蘇紹娟.不確定動態(tài)船隊規(guī)劃的數(shù)學模型研究［J］.中國航海，2008，31(2):158-161.

［5］楊秋平，謝新連，裴光石.考慮船舶航速的船隊規(guī)劃非線性模型［J］.華南理工大學學報:自然科學版，2011，39(10):119-126.

［6］BRONMO G，NYGREEN B，LYSGAARD J.Column generation approaches to ship scheduling with flexible cargo sizes［J］.Eur J Operational Res，2010，200(1):139-150.

［7］陳穎.基于混合遺傳-模擬退火算法的集裝箱班輪配船模型［J］.集裝箱化，2011，32(7):18-20.

［8］林珈伊，陶桂蘭.船閘阻抗影響下的內河航線非線性配船模型［J］.上海海事大學學報，2012，33(2):14-17.

［9］STOPFORD M.Maritime economics［M］.3rd ed.Taylor＆ Francis，2008:93-103.