基于改进遗传算法的远洋渔船船队调度路径优化

陈成明虞丽娟李加林+曹守启夏俊






DOI:10.13340/j.jsmu.2016.04.001
文章编号:1672-9498(2016)04000106
摘要:为实现远洋渔船船队调度路径优化,提高调度工作效率,减少船队的运营成本,对远洋渔船船队调度路径问题建立数学模型.运用在选择和交叉策略上改进的遗传算法对模型进行求解.仿真结果表明,改进的遗传算法能有效解决传统的遗传算法易陷入早熟收敛的问题.利用该算法能快速生成具体的调度方案,且使运营成本减少,可有效解决远洋渔船船队调度路径问题.
关键词:
远洋渔船船队; 数学模型; 船队调度; 路径优化; 改进遗传算法
中图分类号: U692.4 文献标志码: A
收稿日期: 20160322
修回日期: 20160504
基金项目:
国家远洋渔业工程技术研究中心开放基金(02091305051);上海市科学技术委员会创新行动计划(15DZ1202202)
作者简介:
陈成明(1978—),汉,安徽萧县人,讲师,博士,研究方向为物联网工程、人
因工程,(Email)cmchen@shou.edu.cn
虞丽娟(1963—),汉,浙江义乌人,教授,博导,博士,研究方向为物联网工程、海洋工程、体育工程和高等教育管理,(Email)ljyu@shou.edu.cn
0引言
远洋渔业资源是人类社会的宝贵财富,大力发展远洋渔业,合理开发利用远洋渔业资源,有利于缓解我国人均资源短缺问题,保障优质动物蛋白供给.同时,发展远洋渔业不仅能带动船舶及装备设计制造、水产品冷藏加工和物流等相关产业的发展,而且对建设现代渔业、促进经济社会发展、增加农渔民就业和收入、调剂国内市场水产品供给等也具有重要意义[1].
组建远洋渔船船队会极大地提升我国远洋渔业的国际竞争力,我国很多沿海城市已拥有或正在建设大规模的远洋捕捞船队.经调研发现,目前远洋渔船船队调度大多依靠调度员人工调度,这种调度方式不仅效率低且调度方案缺乏科学性.在当今信息技术快速发展的环境下,如何利用计算机技术实现远洋渔船船队调度路径优化,快速调整资源配置,提高调度工作效率,减少船队运营成本,成为许多远洋渔业企业的重大课题.
目前国内外对船队调度路径问题的研究并不多,对远洋渔船船队调度路径优化问题的研究更是少之又少.对船队调度的研究主要是对商船船队调度优化问题的研究[2].商船多以运输货物为主,受最大载重量限制,出航一次只能运载容量限定的货物.然而,远洋渔船是靠出海捕捞获得渔获物的,因为渔获物可以由补给船带回,所以渔船会在达到或超过规定捕捞任务量时返回.远洋渔业企业捕捞特定鱼种会用专门的船队,比如捕捞金枪鱼要用金枪鱼捕捞船队.大型渔场内有很多捕捞点,这些捕捞点一年中会有几个月的渔汛期,即捕捞带有时间窗约束[34],因此对商船船队调度问题的研究不适用于远洋渔船船队.对路径优化问题的研究主要有旅行商问题(Traveling Salesman Problem,TSP)、车辆路径问题(Vehicle Routing Problem, VRP)等.虽然远洋渔船船队调度路径问题与VRP比较相似,都是按照路径最优原则分配给多目标,但与VRP还是有一定区别的.VRP是送货问题,车辆受最大载重量限制,根据客户需求将定量的货物送出,送完即可返回;远洋渔船船队调度问题是收货问题,是将鱼捕捞到船上储存起来,部分渔获物可以由补给船带回,当渔船捕捞总量达到或超过任务量时返回.解决路径优化问题有很多方法,如遗传算法、蚁群算法、粒子群算法和模拟退火算法[59],遗传算法是其中比较常见的方法.
遗传算法是根据达尔文的进化论提出的类似生物进化过程的算法.作为一种智能全局优化搜索算法,遗传算法拥有简单通用、鲁棒性强、适用于并行处理以及效率高等特点.遗传算法也有缺点,如局部搜索能力差、编码较难、容易出现早熟现象,需要根据具体问题调整选择、交叉和变异策略,例如:刘芳华等[10]利用改进的遗传算法对物流配送路径进行优化,发现采用改进编码方案和选择算子能使遗传算法有更好的收敛性;廖良才等[11]基于混合遗传算法对物流配送车辆调度优化问题进行求解,发现采用遗传算法与节约算法相结合的混合遗传算法能够增强局部搜索能力.在对远洋渔船船队调度路径问题进行分析的基础上,本文采用在选择和交叉策略上改进的遗传算法(采用带精英策略的选择算子和具有自适应能力的交叉算子)来解决早熟收敛问题.
1建立数学模型
1.1问题描述
研究远洋渔船船队调度路径问题的目的是使
船队的路线调度方案
运营成本较小.根据对船队运作具体情况的分析,远洋渔船船队调度路径问题主要有以下特点:
(1)准时性.
渔船如果未能在渔汛期到达捕捞点,若要完成同样的捕捞任务,则需投入更多的成本,因此应将时间窗的惩罚成本加入到目标函数中.
(2)路径最短.
远洋渔船调度要考虑渔船闲置费用、渔船启用成本等,但远洋渔船出海捕鱼最主要的成本是油耗成本.油耗量与航行距离成正比,因此应采用路径优化方法减少船队总的航行距离.
(3)渔船资源利用最大化.
要扩大远洋渔船船队的规模,即要尽可能多地派出渔船出海捕鱼,这是因为渔船不出海作业会产生闲置费、折旧费、维护费等费用,且不会产生任何经济效益.目前,远洋渔业资源较为丰富,虽然渔船出海作业会有启用成本,但捕鱼收益要远大于启用成本和渔船消耗所造成的成本,因此应尽可能多地利用渔船资源.
根据上述特点,可以将远洋渔船船队调度路径问题描述为:某中心港口拥有相同型号、捕捞同一鱼种的渔船船队,渔船被派遣到多个捕捞点(一个捕捞点只派遣一艘渔船)进行捕捞作业,渔船完成捕捞任务量即可返回;根据鱼情信息和往年数据,可估计渔船在某捕捞点的渔获量,每个捕捞点会有渔汛期,渔船应尽量在渔汛期内到达捕捞点.根据以上描述可将问题转化为带时间窗的远洋渔船船队调度路径优化问题,即在满足渔汛期时间窗和渔船任务指标的条件下,确定一套从中心港口到渔场各捕捞点的调度路径方案,最大限度地减少船队的运营成本.
1.2模型假设
(1)船队的渔船为同一型号,比如都是捕捞鱿鱼的或都是捕捞金枪鱼的;
(2)根据鱼情信息和往年数据,确定渔场的捕捞点;
(3)取渔船航行的平均速度为计量速度;
(4)只有一个中心港口,每条航线的开始和结束位置都在这个中心港口;
(5)各航线均在较理想状况下,不考虑天气、风浪等特殊情况.