避风型渔港规划问题的启发式算法研究

于红冯艳红李放孙庚栾曙光

(1.大连海洋大学信息工程学院,辽宁大连116023;2.大连海洋大学海洋与土木工程学院,辽宁大连116023)

避风型渔港规划问题的启发式算法研究

于红1,冯艳红1,李放2,孙庚1,栾曙光2

(1.大连海洋大学信息工程学院,辽宁大连116023;2.大连海洋大学海洋与土木工程学院,辽宁大连116023)

避风型渔港的合理规划对减少台风造成渔业的损失具有重要意义。建立了中国东南沿海避风型渔港规划问题的数学模型,并对该模型的复杂度进行了分析,利用渔船就近避风的原则,提出了一种优先考虑最短回港时间的启发式算法,并用中国东南沿海实际的渔港及渔船数据进行了计算,用调研数据对算法的运行效果进行了评估。试验结果表明,本算法具有较好的准确度。

避风型渔港;渔港规划;启发式算法

台风和强风是影响渔业生产安全的重要因素之一,中国东南沿海是受台风和强风影响最严重的地区,1990—2010年,平均每年约4个台风登陆中国东南沿海,其中1个属于破坏力较强的强台风及超强台风,给国家的渔业生产造成了巨大的损失。为了降低台风和强风带来的损失,渔船需要在台风和强风到来前找到合理的避风场所,目前中国东南五省的渔港或避风锚地可以为45%的渔船提供安全避风场所[1],覆盖面偏低。农业部渔业局在“十二五”渔港建设与发展规划中,将渔港防灾减灾作为渔业可持续发展的重中之重,拟新建、扩建一批避风型渔港和避风锚地,以保证为70%的渔船提供安全避风场所。科学地规划渔港布局,使尽可能多的渔船能够在最短的时间内到达港内避风,最大限度地减少台风和强风给渔业生产带来的损失,是目前亟待解决的问题。

1 问题描述与避风型渔港的规划模型

1.1 避风型渔港规划的主要因素

台风和强风到来前,渔船一般分布在渔场中捕鱼作业,出于安全和经济的原因,在接到台风和强风预报时,渔船会选择离自己最近的渔港避风。避风型渔港的规划问题描述为:有n个位置可以建设渔港 (包括已建渔港和备选港址),总共有m条渔船分布在各个渔场,要从n个可建渔港中选择n′个渔港,使得建设这n′个渔港之后,所有m条渔船中b%(b为常数)的渔船到达建设的n′个渔港中避风,总避风成本最小。

避风型渔港规划要考虑的因素包括:渔港的位置、渔港的容量、渔船的位置、渔船的速度、渔船的自持力等,避风型渔港规划问题的总目标就是能够让尽可能多的渔船以最小的成本在最短的时间内回港避风,即避风渔船的总航行距离或航行时间最短。

1.2 避风型渔港布局的数学模型

设xj(j=1,2,…,n)表示渔港pj(j=1, 2,…,n)是否被选中,yij(i=1,2,…,m;j= 1,2,…,n)表示渔船si(i=1,2,…,m)是否进渔港pj(j=1,2,…,n)避风,tij(i=1,2,…,m;j=1,2,…,n)表示渔船si从其作业位置到达渔港pj所用的时间,渔港pj的容量为cpj,避风型渔港规划问题的目标是避风渔船总航行时间最短,因为每条渔船最终只能进入一个渔港避风,渔港pj只能为cpj条渔船避风。因此,目标函数及约束条件如下:

2 渔港规划的启发式算法

2.1 问题及背景分析

按照问题的描述,本算法是在已知渔船数量、每条渔船位置、每条渔船航速、每条渔船类型、渔港数量 (包括已建和未建)、每个渔港位置、每个渔港类型、每个渔港容量的基础上,根据渔船避风的实际需求,计算在保证70%的渔船避风的情况下,建设哪些渔港成本最小。从问题的实际需求和所建立的数学模型可以看出,避风型渔港合理规划问题属于二级0-1规划问题,渔港选择是一个0-1规划问题,规划的目标函数为所给出的渔港选择方案的渔船进港避风成本最小,而对于任何一种渔港选择方案,其渔船进港避风的成本计算均为一个0 -1背包问题,因此,本研究中建立的模型是一个多级组合优化问题,属于复杂的组合优化问题。其中涉及到两组决策变量:渔港的选择向量X和渔船进港避风矩阵Y,模型的最终目标是求出一组使得整个目标函数值最小的决策变量X;而计算决策变量X的代价需要求解使得该方案的目标函数值最小的决策变量Y。组合优化问题理论上已经被证明属于NP-Hard问题,到目前为止,找不到求解这类问题最优解的多项式时间算法,而解决这类问题最有效的算法是启发式算法 (Heuristic Algorithm)[2-4],比较典型的算法策略包括蚁群算法[2-3]、遗传算法[4]、禁忌搜索算法[5]和模拟退火算法[6]等。为此,本研究中作者利用问题的背景知识,提出了解决该问题的启发式算法。

确定求解该问题的算法,首先要考虑渔船避风的实际运行情况。避风型渔港规划建设的基本原则是在台风来临时尽可能减少台风所带来的损失,让尽可能多的渔船能够进入离自己作业区最近的渔港避风。由于实际运行过程中采用就近避风的原则,因此,在建立避风型渔港规划模型时也模拟台风到来时的实际运行模式,即渔船总是选择离自己最近的渔港避风。

2.2 算法的基本思想

本研究中采用启发式搜索策略进行解空间的搜索。算法的基本思想是:根据渔船和渔港的位置,计算每条渔船到达其自持力范围内每个渔港的时间,按照航行时间 (每个航行时间关联一个渔船和一个渔港)由小到大排序,构成航行序列 (航行时间、渔船、渔港);依次从航行序列中取出渔船和渔港,如果渔船未找到合适的渔港且被选择的渔港有空位,则该船进入该港;否则从航行序列中找下一组渔船和渔港,直到70%的渔船找到避风港;此时查看所有渔港的进船情况,如果备选渔港的进船数超过容量的50%,就认为在该地区周围需要建设避风渔港。

在实际运行过程中,中型船和大型船需要到一级渔港和中心渔港避风,而小型船可以到一级以下的渔港避风。如果完全按照就近避风原则,小型船离港较近,航行时间较短,中型船和大型船离港较远,航行时间较长,小型船将会先到达渔港,进而占满中心渔港和一级渔港,导致最需要进港避风的中型船和大型船无处避风。因此,本算法考虑渔船进港避风的实际情况,在中心渔港和一级渔港的规划过程中优先考虑中型船和大型船,在中型船和大型船均已进港避风的情况下,再允许小型船进入中心渔港和一级渔港避风。

2.3 算法描述

简单的渔港规划启发式算法Algorithm NHPPA描述如下。

输入:渔船集合S={s1,s2,…,sm};渔港集合P={p1,p2,…,pn};航行时间集合T= {t11,t12,…,tij,…tmn},tij(i=1,2,…,m;j=1,2,…,n)表示渔船si(i=1,2,…,m)从其作业位置到达渔港pj(j=1,2,…,n)所用的时间。

输出:新增的渔港集合NPS。

变量说明:SA和SB表示渔船集合,渔船si的主要参数为类型type和是否进港Flag,进港标志Flag的初值均为false;PA和PB表示渔港集合,渔港pj的主要参数为容量c和进船数num,进船数num的初值均为0;NS1和NS2分别表示大中型渔船的航行序列集合和小型渔船的航行序列集合,每个航行ns包括航行时间t、渔船s、渔港p3个参数。

算法描述如下:

(1)Set Navigation Set NS1 and NS2 to empty

(2)index1=index2=1

(3)For each siin S{//按照船型对航行序列进行分类

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

(5) For each pjin P{

(6) If pj.Type="中心"or pj.Type="一级" 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 //按照航行时间由小到大对每个航行序列排序

(22)shipCount=0

(23)For each nsiin NS1{//让中型船和大型船优先进港

(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//α是渔船进港比例系数

(29) }

(30) }

(31)}

(32)For each nsiin NS2{//让小型船进港

(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;// α是渔船进港比例系数

(38) }

(39) }

(40)}

(41)Set New Port Set NPS to empty

(42)For each pjin P{

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

(44) NPS=NPS∪{pj}

(45) }

(46)}

(47)输出NPS

2.4 算法的改进

在进行初步的算法设计之后,通过观察和试验发现,由于中国东南沿海海岸线较长,考虑航行成本和航行时间等因素,一般渔船会到离作业位置较近的渔港避风,不会到远离自己的渔港避风,因此不需要计算每一条渔船到达每个渔港的时间,为了减少计算量,缩小搜索空间,将渔船分布区域和渔港分布区域划分为5个对应的区域,区域示意图如图1所示。

图1 渔港及渔船分区示意图Fig.1 M ap of fishing port and fishing-boat com part mentation

图1中每条渔船只能到与自己的区域对应的渔港区及其左右相邻区域避风,如:对于位于SA3区的渔船,只需要计算其到达PA2、PA3和PA4区域渔港的航行时间,而对于位于SA5区域的渔船,则只需要计算其到达PA4和PA5区域渔港的航行时间。

进行区域划分以及根据区域确定渔船的避风渔港,可以大大减少渔港规划问题的时间和空间开销,从而提高计算速度。

3 实验

3.1 实验设计

为了检验算法的效果设计一组实验,实验环境采用 ThinkPad(Intel I3,CPU 2.13 GHz,RAM 8 GB,64位Windows 7),用Java实现该算法。实验中渔船数据参照中国东南沿海实际拥有的渔船数;渔船位置主要根据中国东南沿海渔业资源分布密度,使渔船在渔场中按密度均匀分布;一级渔港和中心渔港的位置和容量用中国东南沿海一级和中心渔港的实际数据;一级以下渔港沿海岸线均匀分布,另外在中国东南沿海岸边选择了一百多个天然避风条件较好的岙口,作为拟建避风型渔港的港址。渔港和渔船区域参照渔场分布以及各省的海岸线进行划分。

3.2 实验结果的评价

为了避免偶然因素对算法运行结果的影响,将算法运行5次,用5次运行算出的拟建港址交集作为最后的拟建港址集合,用5次的平均运算时间作为算法的运行时间,算法的运行时间为5 min。

算法运行前,根据地理位置的特点选择一些位置作为候选拟建港址;算法运行时,根据作业渔船的分布输出一个拟建渔港集合。为了评价算法的效果,作者利用在浙江省进行渔港调研的机会,对计算结果中12个拟建港址进行调研 (受调研经费的限制,不能对所有港址进行调研),了解这12个渔港与实际建港需求的符合程度。调研时,通过现场考察和与当地渔业部门领导及渔民座谈等形式,了解当地避风渔港建设的实际需求。结果了解到在多处急需建港的地方,浙江省正在进行渔港的改扩建,因此,本研究中决定以这12个拟建港址与实际改扩建渔港的符合程度评价模型和算法的效果。考虑到确定候选拟建渔港时并不了解实际的渔港改扩建情况,候选拟建渔港港址和实际改扩建渔港港址之间存在一定误差,而某个拟建港址周围一定距离内有在建渔港,说明该拟建渔港周围有建港需求,因此,用拟建港址与周边正在改扩建的渔港之间的距离来描述拟建渔港与在建渔港的符合程度,调研结果表明,拟建港址与周边正在改扩建渔港的最近距离分别为 6.5、 7.0、 7.0、 2.8、 0.4、11.0、2.0、5.0、0、20.0、6.5、13.0 km。征求当地渔业管理部门的意见后,认为二者之间距离小于10 km可以认为二者相符。据此,本算法的准确率达到75%。

4 结语

为了减少台风及强台风给中国渔业生产造成的影响,首次对避风型渔港和避风锚地合理布局问题进行了研究,建立了中国东南沿海避风型渔港规划问题的数学模型,在此基础上提出了一种优先考虑最短回港时间的启发式算法,用中国东南沿海实际的渔港及渔船数据验证了该模型和算法的有效性,用现场调研数据对算法的运行结果进行了评估。结果表明,本研究中建立的模型和算法取得了较好的效果。但是由于计算结果存在一定的误差,因此不能直接应用于实际渔港布局规划,下一步的工作需要根据实际应用背景,综合考虑休渔期和渔业资源分布不均等因素,对模型和算法进行修正,进一步改进模型和算法的效果。

[1] 农业部渔业局.2010中国渔业统计年鉴[M].北京:中国农业出版社,2010.

[2] 熊伟清,魏平.二进制蚁群进化算法[J].自动化学报,2007,33 (3):259-264.

[3] 袁军良,熊伟清,江宝钏.混合二元蚁群算法求解集装箱装载问题[J].计算机工程与应用,2010,46(36):222-225.

[4] 钟金宏,黄玲.带外包受限批量模型的启发式遗传算法[J].系统仿真学报,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

农业部项目 (农财发 [2012]26号)

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

2095-1388(2012)04-0373-04