避風(fēng)型漁港規(guī)劃問(wèn)題的啟發(fā)式算法研究

于紅馮艷紅李放孫庚欒曙光

(1.大連海洋大學(xué)信息工程學(xué)院,遼寧大連116023;2.大連海洋大學(xué)海洋與土木工程學(xué)院,遼寧大連116023)

避風(fēng)型漁港規(guī)劃問(wèn)題的啟發(fā)式算法研究

于紅1,馮艷紅1,李放2,孫庚1,欒曙光2

(1.大連海洋大學(xué)信息工程學(xué)院,遼寧大連116023;2.大連海洋大學(xué)海洋與土木工程學(xué)院,遼寧大連116023)

避風(fēng)型漁港的合理規(guī)劃對(duì)減少臺(tái)風(fēng)造成漁業(yè)的損失具有重要意義。建立了中國(guó)東南沿海避風(fēng)型漁港規(guī)劃問(wèn)題的數(shù)學(xué)模型,并對(duì)該模型的復(fù)雜度進(jìn)行了分析,利用漁船就近避風(fēng)的原則,提出了一種優(yōu)先考慮最短回港時(shí)間的啟發(fā)式算法,并用中國(guó)東南沿海實(shí)際的漁港及漁船數(shù)據(jù)進(jìn)行了計(jì)算,用調(diào)研數(shù)據(jù)對(duì)算法的運(yùn)行效果進(jìn)行了評(píng)估。試驗(yàn)結(jié)果表明,本算法具有較好的準(zhǔn)確度。

避風(fēng)型漁港;漁港規(guī)劃;啟發(fā)式算法

臺(tái)風(fēng)和強(qiáng)風(fēng)是影響漁業(yè)生產(chǎn)安全的重要因素之一,中國(guó)東南沿海是受臺(tái)風(fēng)和強(qiáng)風(fēng)影響最嚴(yán)重的地區(qū),1990—2010年,平均每年約4個(gè)臺(tái)風(fēng)登陸中國(guó)東南沿海,其中1個(gè)屬于破壞力較強(qiáng)的強(qiáng)臺(tái)風(fēng)及超強(qiáng)臺(tái)風(fēng),給國(guó)家的漁業(yè)生產(chǎn)造成了巨大的損失。為了降低臺(tái)風(fēng)和強(qiáng)風(fēng)帶來(lái)的損失,漁船需要在臺(tái)風(fēng)和強(qiáng)風(fēng)到來(lái)前找到合理的避風(fēng)場(chǎng)所,目前中國(guó)東南五省的漁港或避風(fēng)錨地可以為45%的漁船提供安全避風(fēng)場(chǎng)所[1],覆蓋面偏低。農(nóng)業(yè)部漁業(yè)局在“十二五”漁港建設(shè)與發(fā)展規(guī)劃中,將漁港防災(zāi)減災(zāi)作為漁業(yè)可持續(xù)發(fā)展的重中之重,擬新建、擴(kuò)建一批避風(fēng)型漁港和避風(fēng)錨地,以保證為70%的漁船提供安全避風(fēng)場(chǎng)所?？茖W(xué)地規(guī)劃漁港布局,使盡可能多的漁船能夠在最短的時(shí)間內(nèi)到達(dá)港內(nèi)避風(fēng),最大限度地減少臺(tái)風(fēng)和強(qiáng)風(fēng)給漁業(yè)生產(chǎn)帶來(lái)的損失,是目前亟待解決的問(wèn)題。

1 問(wèn)題描述與避風(fēng)型漁港的規(guī)劃模型

1.1 避風(fēng)型漁港規(guī)劃的主要因素

臺(tái)風(fēng)和強(qiáng)風(fēng)到來(lái)前,漁船一般分布在漁場(chǎng)中捕魚作業(yè),出于安全和經(jīng)濟(jì)的原因,在接到臺(tái)風(fēng)和強(qiáng)風(fēng)預(yù)報(bào)時(shí),漁船會(huì)選擇離自己最近的漁港避風(fēng)。避風(fēng)型漁港的規(guī)劃問(wèn)題描述為:有n個(gè)位置可以建設(shè)漁港 (包括已建漁港和備選港址),總共有m條漁船分布在各個(gè)漁場(chǎng),要從n個(gè)可建漁港中選擇n′個(gè)漁港,使得建設(shè)這n′個(gè)漁港之后,所有m條漁船中b%(b為常數(shù))的漁船到達(dá)建設(shè)的n′個(gè)漁港中避風(fēng),總避風(fēng)成本最小。

避風(fēng)型漁港規(guī)劃要考慮的因素包括:漁港的位置、漁港的容量、漁船的位置、漁船的速度、漁船的自持力等,避風(fēng)型漁港規(guī)劃問(wèn)題的總目標(biāo)就是能夠讓盡可能多的漁船以最小的成本在最短的時(shí)間內(nèi)回港避風(fēng),即避風(fēng)漁船的總航行距離或航行時(shí)間最短。

1.2 避風(fēng)型漁港布局的數(shù)學(xué)模型

設(shè)xj(j=1,2,…,n)表示漁港pj(j=1, 2,…,n)是否被選中,yij(i=1,2,…,m;j= 1,2,…,n)表示漁船si(i=1,2,…,m)是否進(jìn)漁港pj(j=1,2,…,n)避風(fēng),tij(i=1,2,…,m;j=1,2,…,n)表示漁船si從其作業(yè)位置到達(dá)漁港pj所用的時(shí)間,漁港pj的容量為cpj,避風(fēng)型漁港規(guī)劃問(wèn)題的目標(biāo)是避風(fēng)漁船總航行時(shí)間最短,因?yàn)槊織l漁船最終只能進(jìn)入一個(gè)漁港避風(fēng),漁港pj只能為cpj條漁船避風(fēng)。因此,目標(biāo)函數(shù)及約束條件如下:

2 漁港規(guī)劃的啟發(fā)式算法

2.1 問(wèn)題及背景分析

按照問(wèn)題的描述,本算法是在已知漁船數(shù)量、每條漁船位置、每條漁船航速、每條漁船類型、漁港數(shù)量 (包括已建和未建)、每個(gè)漁港位置、每個(gè)漁港類型、每個(gè)漁港容量的基礎(chǔ)上,根據(jù)漁船避風(fēng)的實(shí)際需求,計(jì)算在保證70%的漁船避風(fēng)的情況下,建設(shè)哪些漁港成本最小。從問(wèn)題的實(shí)際需求和所建立的數(shù)學(xué)模型可以看出,避風(fēng)型漁港合理規(guī)劃問(wèn)題屬于二級(jí)0-1規(guī)劃問(wèn)題,漁港選擇是一個(gè)0-1規(guī)劃問(wèn)題,規(guī)劃的目標(biāo)函數(shù)為所給出的漁港選擇方案的漁船進(jìn)港避風(fēng)成本最小,而對(duì)于任何一種漁港選擇方案,其漁船進(jìn)港避風(fēng)的成本計(jì)算均為一個(gè)0 -1背包問(wèn)題,因此,本研究中建立的模型是一個(gè)多級(jí)組合優(yōu)化問(wèn)題,屬于復(fù)雜的組合優(yōu)化問(wèn)題。其中涉及到兩組決策變量:漁港的選擇向量X和漁船進(jìn)港避風(fēng)矩陣Y,模型的最終目標(biāo)是求出一組使得整個(gè)目標(biāo)函數(shù)值最小的決策變量X;而計(jì)算決策變量X的代價(jià)需要求解使得該方案的目標(biāo)函數(shù)值最小的決策變量Y。組合優(yōu)化問(wèn)題理論上已經(jīng)被證明屬于NP-Hard問(wèn)題,到目前為止,找不到求解這類問(wèn)題最優(yōu)解的多項(xiàng)式時(shí)間算法,而解決這類問(wèn)題最有效的算法是啟發(fā)式算法 (Heuristic Algorithm)[2-4],比較典型的算法策略包括蟻群算法[2-3]、遺傳算法[4]、禁忌搜索算法[5]和模擬退火算法[6]等。為此,本研究中作者利用問(wèn)題的背景知識(shí),提出了解決該問(wèn)題的啟發(fā)式算法。

確定求解該問(wèn)題的算法,首先要考慮漁船避風(fēng)的實(shí)際運(yùn)行情況。避風(fēng)型漁港規(guī)劃建設(shè)的基本原則是在臺(tái)風(fēng)來(lái)臨時(shí)盡可能減少臺(tái)風(fēng)所帶來(lái)的損失,讓盡可能多的漁船能夠進(jìn)入離自己作業(yè)區(qū)最近的漁港避風(fēng)。由于實(shí)際運(yùn)行過(guò)程中采用就近避風(fēng)的原則,因此,在建立避風(fēng)型漁港規(guī)劃模型時(shí)也模擬臺(tái)風(fēng)到來(lái)時(shí)的實(shí)際運(yùn)行模式,即漁船總是選擇離自己最近的漁港避風(fēng)。

2.2 算法的基本思想

本研究中采用啟發(fā)式搜索策略進(jìn)行解空間的搜索。算法的基本思想是:根據(jù)漁船和漁港的位置,計(jì)算每條漁船到達(dá)其自持力范圍內(nèi)每個(gè)漁港的時(shí)間,按照航行時(shí)間 (每個(gè)航行時(shí)間關(guān)聯(lián)一個(gè)漁船和一個(gè)漁港)由小到大排序,構(gòu)成航行序列 (航行時(shí)間、漁船、漁港);依次從航行序列中取出漁船和漁港,如果漁船未找到合適的漁港且被選擇的漁港有空位,則該船進(jìn)入該港;否則從航行序列中找下一組漁船和漁港,直到70%的漁船找到避風(fēng)港;此時(shí)查看所有漁港的進(jìn)船情況,如果備選漁港的進(jìn)船數(shù)超過(guò)容量的50%,就認(rèn)為在該地區(qū)周圍需要建設(shè)避風(fēng)漁港。

在實(shí)際運(yùn)行過(guò)程中,中型船和大型船需要到一級(jí)漁港和中心漁港避風(fēng),而小型船可以到一級(jí)以下的漁港避風(fēng)。如果完全按照就近避風(fēng)原則,小型船離港較近,航行時(shí)間較短,中型船和大型船離港較遠(yuǎn),航行時(shí)間較長(zhǎng),小型船將會(huì)先到達(dá)漁港,進(jìn)而占滿中心漁港和一級(jí)漁港,導(dǎo)致最需要進(jìn)港避風(fēng)的中型船和大型船無(wú)處避風(fēng)。因此,本算法考慮漁船進(jìn)港避風(fēng)的實(shí)際情況,在中心漁港和一級(jí)漁港的規(guī)劃過(guò)程中優(yōu)先考慮中型船和大型船,在中型船和大型船均已進(jìn)港避風(fēng)的情況下,再允許小型船進(jìn)入中心漁港和一級(jí)漁港避風(fēng)。

2.3 算法描述

簡(jiǎn)單的漁港規(guī)劃啟發(fā)式算法Algorithm NHPPA描述如下。

輸入:漁船集合S={s1,s2,…,sm};漁港集合P={p1,p2,…,pn};航行時(shí)間集合T= {t11,t12,…,tij,…tmn},tij(i=1,2,…,m;j=1,2,…,n)表示漁船si(i=1,2,…,m)從其作業(yè)位置到達(dá)漁港pj(j=1,2,…,n)所用的時(shí)間。

輸出:新增的漁港集合NPS。

變量說(shuō)明:SA和SB表示漁船集合,漁船si的主要參數(shù)為類型type和是否進(jìn)港Flag,進(jìn)港標(biāo)志Flag的初值均為false;PA和PB表示漁港集合,漁港pj的主要參數(shù)為容量c和進(jìn)船數(shù)num,進(jìn)船數(shù)num的初值均為0;NS1和NS2分別表示大中型漁船的航行序列集合和小型漁船的航行序列集合,每個(gè)航行ns包括航行時(shí)間t、漁船s、漁港p3個(gè)參數(shù)。

算法描述如下:

(1)Set Navigation Set NS1 and NS2 to empty

(2)index1=index2=1

(3)For each siin S{//按照船型對(duì)航行序列進(jìn)行分類

(4) If si.Type="大型"or si.Type="中型"then{

(5) For each pjin P{

(6) If pj.Type="中心"or pj.Type="一級(jí)" then{

(7) nsindex1.t=tij:nsindex1.p=pj:nsindex1.s=si

(8) NS1=NS1∪{nsindex1}

(9) index1++

(10) }

(11) }

(12) }

(13) Else{

(14) For each pjin P{

(15) nsindex2.t=tij:nsindex2.p=pj:nsindex2.s=si

(16) NS2=NS2∪{nsindex2}

(17) index2++

(18) }

(19) }

(20)}

(21)Sort NS1 and NS2 //按照航行時(shí)間由小到大對(duì)每個(gè)航行序列排序

(22)shipCount=0

(23)For each nsiin NS1{//讓中型船和大型船優(yōu)先進(jìn)港

(24) If nsi.s.flag=false then{

(25) If nsi.p.num＜nsi.p.c then{

(26) nsi.s.flag=true:nsi.p.num++

(27) shipCount++

(28) If shipCount＞=α*m then break//α是漁船進(jìn)港比例系數(shù)

(29) }

(30) }

(31)}

(32)For each nsiin NS2{//讓小型船進(jìn)港

(33) If nsi.s.flag=false then{

(34) If nsi.p.num＜nsi.p.c then{

(35) nsi.s.flag=true:nsi.p.num++

(36) shipCount++

(37) If shipCount＞=α*m then break;// α是漁船進(jìn)港比例系數(shù)

(38) }

(39) }

(40)}

(41)Set New Port Set NPS to empty

(42)For each pjin P{

(43) If pj.num＞=pj.c*β{//β是符合建港的容量系數(shù)

(44) NPS=NPS∪{pj}

(45) }

(46)}

(47)輸出NPS

2.4 算法的改進(jìn)

在進(jìn)行初步的算法設(shè)計(jì)之后,通過(guò)觀察和試驗(yàn)發(fā)現(xiàn),由于中國(guó)東南沿海海岸線較長(zhǎng),考慮航行成本和航行時(shí)間等因素,一般漁船會(huì)到離作業(yè)位置較近的漁港避風(fēng),不會(huì)到遠(yuǎn)離自己的漁港避風(fēng),因此不需要計(jì)算每一條漁船到達(dá)每個(gè)漁港的時(shí)間,為了減少計(jì)算量,縮小搜索空間,將漁船分布區(qū)域和漁港分布區(qū)域劃分為5個(gè)對(duì)應(yīng)的區(qū)域,區(qū)域示意圖如圖1所示。

圖1 漁港及漁船分區(qū)示意圖Fig.1 M ap of fishing port and fishing-boat com part mentation

圖1中每條漁船只能到與自己的區(qū)域?qū)?yīng)的漁港區(qū)及其左右相鄰區(qū)域避風(fēng),如:對(duì)于位于SA3區(qū)的漁船,只需要計(jì)算其到達(dá)PA2、PA3和PA4區(qū)域漁港的航行時(shí)間,而對(duì)于位于SA5區(qū)域的漁船,則只需要計(jì)算其到達(dá)PA4和PA5區(qū)域漁港的航行時(shí)間。

進(jìn)行區(qū)域劃分以及根據(jù)區(qū)域確定漁船的避風(fēng)漁港,可以大大減少漁港規(guī)劃問(wèn)題的時(shí)間和空間開銷,從而提高計(jì)算速度。

3 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

為了檢驗(yàn)算法的效果設(shè)計(jì)一組實(shí)驗(yàn),實(shí)驗(yàn)環(huán)境采用 ThinkPad(Intel I3,CPU 2.13 GHz,RAM 8 GB,64位Windows 7),用Java實(shí)現(xiàn)該算法。實(shí)驗(yàn)中漁船數(shù)據(jù)參照中國(guó)東南沿海實(shí)際擁有的漁船數(shù);漁船位置主要根據(jù)中國(guó)東南沿海漁業(yè)資源分布密度,使?jié)O船在漁場(chǎng)中按密度均勻分布;一級(jí)漁港和中心漁港的位置和容量用中國(guó)東南沿海一級(jí)和中心漁港的實(shí)際數(shù)據(jù);一級(jí)以下漁港沿海岸線均勻分布,另外在中國(guó)東南沿海岸邊選擇了一百多個(gè)天然避風(fēng)條件較好的岙口,作為擬建避風(fēng)型漁港的港址。漁港和漁船區(qū)域參照漁場(chǎng)分布以及各省的海岸線進(jìn)行劃分。

3.2 實(shí)驗(yàn)結(jié)果的評(píng)價(jià)

為了避免偶然因素對(duì)算法運(yùn)行結(jié)果的影響,將算法運(yùn)行5次,用5次運(yùn)行算出的擬建港址交集作為最后的擬建港址集合,用5次的平均運(yùn)算時(shí)間作為算法的運(yùn)行時(shí)間,算法的運(yùn)行時(shí)間為5 min。

算法運(yùn)行前,根據(jù)地理位置的特點(diǎn)選擇一些位置作為候選擬建港址;算法運(yùn)行時(shí),根據(jù)作業(yè)漁船的分布輸出一個(gè)擬建漁港集合。為了評(píng)價(jià)算法的效果,作者利用在浙江省進(jìn)行漁港調(diào)研的機(jī)會(huì),對(duì)計(jì)算結(jié)果中12個(gè)擬建港址進(jìn)行調(diào)研 (受調(diào)研經(jīng)費(fèi)的限制,不能對(duì)所有港址進(jìn)行調(diào)研),了解這12個(gè)漁港與實(shí)際建港需求的符合程度。調(diào)研時(shí),通過(guò)現(xiàn)場(chǎng)考察和與當(dāng)?shù)貪O業(yè)部門領(lǐng)導(dǎo)及漁民座談等形式,了解當(dāng)?shù)乇茱L(fēng)漁港建設(shè)的實(shí)際需求。結(jié)果了解到在多處急需建港的地方,浙江省正在進(jìn)行漁港的改擴(kuò)建,因此,本研究中決定以這12個(gè)擬建港址與實(shí)際改擴(kuò)建漁港的符合程度評(píng)價(jià)模型和算法的效果?？紤]到確定候選擬建漁港時(shí)并不了解實(shí)際的漁港改擴(kuò)建情況,候選擬建漁港港址和實(shí)際改擴(kuò)建漁港港址之間存在一定誤差,而某個(gè)擬建港址周圍一定距離內(nèi)有在建漁港,說(shuō)明該擬建漁港周圍有建港需求,因此,用擬建港址與周邊正在改擴(kuò)建的漁港之間的距離來(lái)描述擬建漁港與在建漁港的符合程度,調(diào)研結(jié)果表明,擬建港址與周邊正在改擴(kuò)建漁港的最近距離分別為 6.5、 7.0、 7.0、 2.8、 0.4、11.0、2.0、5.0、0、20.0、6.5、13.0 km。征求當(dāng)?shù)貪O業(yè)管理部門的意見后,認(rèn)為二者之間距離小于10 km可以認(rèn)為二者相符。據(jù)此,本算法的準(zhǔn)確率達(dá)到75%。

4 結(jié)語(yǔ)

為了減少臺(tái)風(fēng)及強(qiáng)臺(tái)風(fēng)給中國(guó)漁業(yè)生產(chǎn)造成的影響,首次對(duì)避風(fēng)型漁港和避風(fēng)錨地合理布局問(wèn)題進(jìn)行了研究,建立了中國(guó)東南沿海避風(fēng)型漁港規(guī)劃問(wèn)題的數(shù)學(xué)模型,在此基礎(chǔ)上提出了一種優(yōu)先考慮最短回港時(shí)間的啟發(fā)式算法,用中國(guó)東南沿海實(shí)際的漁港及漁船數(shù)據(jù)驗(yàn)證了該模型和算法的有效性,用現(xiàn)場(chǎng)調(diào)研數(shù)據(jù)對(duì)算法的運(yùn)行結(jié)果進(jìn)行了評(píng)估。結(jié)果表明,本研究中建立的模型和算法取得了較好的效果。但是由于計(jì)算結(jié)果存在一定的誤差,因此不能直接應(yīng)用于實(shí)際漁港布局規(guī)劃,下一步的工作需要根據(jù)實(shí)際應(yīng)用背景,綜合考慮休漁期和漁業(yè)資源分布不均等因素,對(duì)模型和算法進(jìn)行修正,進(jìn)一步改進(jìn)模型和算法的效果。

[1] 農(nóng)業(yè)部漁業(yè)局.2010中國(guó)漁業(yè)統(tǒng)計(jì)年鑒[M].北京:中國(guó)農(nóng)業(yè)出版社,2010.

[2] 熊偉清,魏平.二進(jìn)制蟻群進(jìn)化算法[J].自動(dòng)化學(xué)報(bào),2007,33 (3):259-264.

[3] 袁軍良,熊偉清,江寶釧.混合二元蟻群算法求解集裝箱裝載問(wèn)題[J].計(jì)算機(jī)工程與應(yīng)用,2010,46(36):222-225.

[4] 鐘金宏,黃玲.帶外包受限批量模型的啟發(fā)式遺傳算法[J].系統(tǒng)仿真學(xué)報(bào),2011,23(12):2623-2628.

[5] Fred Glover.Tabu Search—Part I[J].ORSA Journal on Computing,1989,1(3):190-206.

[6] Kirkpatrick S,Gelatt Jr C D,VecchiM P.Optimization by simulated annealing[J].Science,1983,220:671-680.

Heuristic algorithm for planning problem of fishing port sheltered from typhoon

YU Hong1,FENG Yan-hong1,LIFang2,SUN Geng1,LUAN Shu-guang2
(1.College of Information Engineering,Dalian Ocean University,Dalian 116023,China;2.College of Marine and Civil Engineering, Dalian Ocean University,Dalian 116023,China)

The rational planning of fishing port sheltered from typhoon plays an important role in reducing fishery loss from typhoon.Themathematic model of fishing port planning in the southeastern coastal region is built.The complexity of themodel is analyzed.Following the principle of“Fishing vessles should shelter from typhoon in the nearest fishing port”,the paper puts forward a heuristic algorithm,which firstly considers the shortest time to return fishing port.The actual data of fishing ports and vessels in the southeast region are utilized in calculation and the survey data are used to envaluate computing result of heuristic algorithm.The result shows that the heuristic algorithm carries accepable accuracy.

fishing port sheltered from typhoon;planning of fishing port;heuristic algorithm

TP311

A

2012-05-28

農(nóng)業(yè)部項(xiàng)目 (農(nóng)財(cái)發(fā) [2012]26號(hào))

于紅 (1968-),女,教授。E-mail:yuhong@dlou.edu.cn

2095-1388(2012)04-0373-04