基于改進(jìn)遺傳算法的遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑優(yōu)化

陳成明虞麗娟李加林+曹守啟夏俊

DOI：10.13340/j.jsmu.2016.04.001

文章編號(hào)：1672-9498（2016）04000106

摘要：為實(shí)現(xiàn)遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑優(yōu)化，提高調(diào)度工作效率，減少船隊(duì)的運(yùn)營(yíng)成本，對(duì)遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑問題建立數(shù)學(xué)模型.運(yùn)用在選擇和交叉策略上改進(jìn)的遺傳算法對(duì)模型進(jìn)行求解.仿真結(jié)果表明，改進(jìn)的遺傳算法能有效解決傳統(tǒng)的遺傳算法易陷入早熟收斂的問題.利用該算法能快速生成具體的調(diào)度方案，且使運(yùn)營(yíng)成本減少，可有效解決遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑問題.

關(guān)鍵詞：

遠(yuǎn)洋漁船船隊(duì)； 數(shù)學(xué)模型； 船隊(duì)調(diào)度； 路徑優(yōu)化； 改進(jìn)遺傳算法

中圖分類號(hào)： U692.4 文獻(xiàn)標(biāo)志碼： A

收稿日期： 20160322

修回日期： 20160504

基金項(xiàng)目：

國(guó)家遠(yuǎn)洋漁業(yè)工程技術(shù)研究中心開放基金（02091305051）；上海市科學(xué)技術(shù)委員會(huì)創(chuàng)新行動(dòng)計(jì)劃（15DZ1202202）

作者簡(jiǎn)介：

陳成明（1978—），漢，安徽蕭縣人，講師，博士，研究方向?yàn)槲锫?lián)網(wǎng)工程、人

因工程，（Email）cmchen@shou.edu.cn

虞麗娟（1963—），漢，浙江義烏人，教授，博導(dǎo)，博士，研究方向?yàn)槲锫?lián)網(wǎng)工程、海洋工程、體育工程和高等教育管理，（Email）ljyu@shou.edu.cn

0引言

遠(yuǎn)洋漁業(yè)資源是人類社會(huì)的寶貴財(cái)富，大力發(fā)展遠(yuǎn)洋漁業(yè)，合理開發(fā)利用遠(yuǎn)洋漁業(yè)資源，有利于緩解我國(guó)人均資源短缺問題，保障優(yōu)質(zhì)動(dòng)物蛋白供給.同時(shí)，發(fā)展遠(yuǎn)洋漁業(yè)不僅能帶動(dòng)船舶及裝備設(shè)計(jì)制造、水產(chǎn)品冷藏加工和物流等相關(guān)產(chǎn)業(yè)的發(fā)展，而且對(duì)建設(shè)現(xiàn)代漁業(yè)、促進(jìn)經(jīng)濟(jì)社會(huì)發(fā)展、增加農(nóng)漁民就業(yè)和收入、調(diào)劑國(guó)內(nèi)市場(chǎng)水產(chǎn)品供給等也具有重要意義[1].

組建遠(yuǎn)洋漁船船隊(duì)會(huì)極大地提升我國(guó)遠(yuǎn)洋漁業(yè)的國(guó)際競(jìng)爭(zhēng)力，我國(guó)很多沿海城市已擁有或正在建設(shè)大規(guī)模的遠(yuǎn)洋捕撈船隊(duì).經(jīng)調(diào)研發(fā)現(xiàn)，目前遠(yuǎn)洋漁船船隊(duì)調(diào)度大多依靠調(diào)度員人工調(diào)度，這種調(diào)度方式不僅效率低且調(diào)度方案缺乏科學(xué)性.在當(dāng)今信息技術(shù)快速發(fā)展的環(huán)境下，如何利用計(jì)算機(jī)技術(shù)實(shí)現(xiàn)遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑優(yōu)化，快速調(diào)整資源配置，提高調(diào)度工作效率，減少船隊(duì)運(yùn)營(yíng)成本，成為許多遠(yuǎn)洋漁業(yè)企業(yè)的重大課題.

目前國(guó)內(nèi)外對(duì)船隊(duì)調(diào)度路徑問題的研究并不多，對(duì)遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑優(yōu)化問題的研究更是少之又少.對(duì)船隊(duì)調(diào)度的研究主要是對(duì)商船船隊(duì)調(diào)度優(yōu)化問題的研究[2].商船多以運(yùn)輸貨物為主，受最大載重量限制，出航一次只能運(yùn)載容量限定的貨物.然而，遠(yuǎn)洋漁船是靠出海捕撈獲得漁獲物的，因?yàn)闈O獲物可以由補(bǔ)給船帶回，所以漁船會(huì)在達(dá)到或超過規(guī)定捕撈任務(wù)量時(shí)返回.遠(yuǎn)洋漁業(yè)企業(yè)捕撈特定魚種會(huì)用專門的船隊(duì)，比如捕撈金槍魚要用金槍魚捕撈船隊(duì).大型漁場(chǎng)內(nèi)有很多捕撈點(diǎn)，這些捕撈點(diǎn)一年中會(huì)有幾個(gè)月的漁汛期，即捕撈帶有時(shí)間窗約束[34]，因此對(duì)商船船隊(duì)調(diào)度問題的研究不適用于遠(yuǎn)洋漁船船隊(duì).對(duì)路徑優(yōu)化問題的研究主要有旅行商問題（Traveling Salesman Problem，TSP）、車輛路徑問題（Vehicle Routing Problem， VRP）等.雖然遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑問題與VRP比較相似，都是按照路徑最優(yōu)原則分配給多目標(biāo)，但與VRP還是有一定區(qū)別的.VRP是送貨問題，車輛受最大載重量限制，根據(jù)客戶需求將定量的貨物送出，送完即可返回；遠(yuǎn)洋漁船船隊(duì)調(diào)度問題是收貨問題，是將魚捕撈到船上儲(chǔ)存起來，部分漁獲物可以由補(bǔ)給船帶回，當(dāng)漁船捕撈總量達(dá)到或超過任務(wù)量時(shí)返回.解決路徑優(yōu)化問題有很多方法，如遺傳算法、蟻群算法、粒子群算法和模擬退火算法[59]，遺傳算法是其中比較常見的方法.

遺傳算法是根據(jù)達(dá)爾文的進(jìn)化論提出的類似生物進(jìn)化過程的算法.作為一種智能全局優(yōu)化搜索算法，遺傳算法擁有簡(jiǎn)單通用、魯棒性強(qiáng)、適用于并行處理以及效率高等特點(diǎn).遺傳算法也有缺點(diǎn)，如局部搜索能力差、編碼較難、容易出現(xiàn)早熟現(xiàn)象，需要根據(jù)具體問題調(diào)整選擇、交叉和變異策略，例如：劉芳華等[10]利用改進(jìn)的遺傳算法對(duì)物流配送路徑進(jìn)行優(yōu)化，發(fā)現(xiàn)采用改進(jìn)編碼方案和選擇算子能使遺傳算法有更好的收斂性；廖良才等[11]基于混合遺傳算法對(duì)物流配送車輛調(diào)度優(yōu)化問題進(jìn)行求解，發(fā)現(xiàn)采用遺傳算法與節(jié)約算法相結(jié)合的混合遺傳算法能夠增強(qiáng)局部搜索能力.在對(duì)遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑問題進(jìn)行分析的基礎(chǔ)上，本文采用在選擇和交叉策略上改進(jìn)的遺傳算法（采用帶精英策略的選擇算子和具有自適應(yīng)能力的交叉算子）來解決早熟收斂問題.

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

1.1問題描述

研究遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑問題的目的是使

船隊(duì)的路線調(diào)度方案

運(yùn)營(yíng)成本較小.根據(jù)對(duì)船隊(duì)運(yùn)作具體情況的分析，遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑問題主要有以下特點(diǎn)：

（1）準(zhǔn)時(shí)性.

漁船如果未能在漁汛期到達(dá)捕撈點(diǎn)，若要完成同樣的捕撈任務(wù)，則需投入更多的成本，因此應(yīng)將時(shí)間窗的懲罰成本加入到目標(biāo)函數(shù)中.

（2）路徑最短.

遠(yuǎn)洋漁船調(diào)度要考慮漁船閑置費(fèi)用、漁船啟用成本等，但遠(yuǎn)洋漁船出海捕魚最主要的成本是油耗成本.油耗量與航行距離成正比，因此應(yīng)采用路徑優(yōu)化方法減少船隊(duì)總的航行距離.

（3）漁船資源利用最大化.

要擴(kuò)大遠(yuǎn)洋漁船船隊(duì)的規(guī)模，即要盡可能多地派出漁船出海捕魚，這是因?yàn)闈O船不出海作業(yè)會(huì)產(chǎn)生閑置費(fèi)、折舊費(fèi)、維護(hù)費(fèi)等費(fèi)用，且不會(huì)產(chǎn)生任何經(jīng)濟(jì)效益.目前，遠(yuǎn)洋漁業(yè)資源較為豐富，雖然漁船出海作業(yè)會(huì)有啟用成本，但捕魚收益要遠(yuǎn)大于啟用成本和漁船消耗所造成的成本，因此應(yīng)盡可能多地利用漁船資源.

根據(jù)上述特點(diǎn)，可以將遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑問題描述為：某中心港口擁有相同型號(hào)、捕撈同一魚種的漁船船隊(duì)，漁船被派遣到多個(gè)捕撈點(diǎn)（一個(gè)捕撈點(diǎn)只派遣一艘漁船）進(jìn)行捕撈作業(yè)，漁船完成捕撈任務(wù)量即可返回；根據(jù)魚情信息和往年數(shù)據(jù)，可估計(jì)漁船在某捕撈點(diǎn)的漁獲量，每個(gè)捕撈點(diǎn)會(huì)有漁汛期，漁船應(yīng)盡量在漁汛期內(nèi)到達(dá)捕撈點(diǎn).根據(jù)以上描述可將問題轉(zhuǎn)化為帶時(shí)間窗的遠(yuǎn)洋漁船船隊(duì)調(diào)度路徑優(yōu)化問題，即在滿足漁汛期時(shí)間窗和漁船任務(wù)指標(biāo)的條件下，確定一套從中心港口到漁場(chǎng)各捕撈點(diǎn)的調(diào)度路徑方案，最大限度地減少船隊(duì)的運(yùn)營(yíng)成本.

1.2模型假設(shè)

（1）船隊(duì)的漁船為同一型號(hào)，比如都是捕撈魷魚的或都是捕撈金槍魚的；

（2）根據(jù)魚情信息和往年數(shù)據(jù)，確定漁場(chǎng)的捕撈點(diǎn)；

（3）取漁船航行的平均速度為計(jì)量速度；

（4）只有一個(gè)中心港口，每條航線的開始和結(jié)束位置都在這個(gè)中心港口；

（5）各航線均在較理想狀況下，不考慮天氣、風(fēng)浪等特殊情況.